\documentclass[12pt]{article}

\usepackage{amsmath,amscd,amsbsy,amssymb,latexsym,url}
\usepackage{epsfig,graphicx,subfigure}
\usepackage{enumitem,balance,mathtools}
\usepackage{wrapfig}
\usepackage{tikz} \setlength\oddsidemargin{-0.05in}
\usetikzlibrary{calc} \setlength\evensidemargin{-0.05in}
\setlength\textheight{8.7in} \setlength\topmargin{-0.1in}
\setlength\textwidth{6.3in}
\usepackage{mathrsfs, euscript}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}{Exercise}[section]
%\newtheorem{solution}{section}

\setcounter{section}{1} \numberwithin{equation}{section}
\numberwithin{figure}{section}

\newenvironment{proof}[1][Proof:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Definition:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{solution}[1][Solution:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.4em width0.5em depth0.25em\fi}
\newcommand{\hw}[1]{#1}%includes solutions
\newcommand{\indt}[1]{\begin{list}{\setlength\leftmargin{0.5in}}\item{}#1\end{list}\noindent}
\def\Prob{\text{Prob}}
\def\prob{\text{Prob}}
\begin{document}
\noindent

%========================================================================
\begin{center}
\textbf{\Large{Homework 1}} \vspace{1mm}

Mathematics in Computer Science
%John E. Hopcroft
\end{center}
\begin{enumerate}
\item What are the sets
\begin{enumerate}
\item $\{0^i1|i\in N\}$
%\text{Ans}\{1,01,001,\ldots\}$
\item $S_1=\{101\}\{0^i10^{i+1}1|i\in N\}^*$
\item $S_2=\{1\}\{0^i10^{i+1}1|i\in N\}^*\{0\}^*\{1\}$
\item $S_1\cap S_2$
\end{enumerate}
%
\item Create an exercise that illustrates the notion of closure for a class of sets other than these included in the class.
%
\item Which of the following classes of sets are closed under each
of the following operations: union, intersection, power set
operation? Explain your answer.
\begin{enumerate}
  \item the class of all finite sets
  \item the class of all infinite sets
  \item the class of all sets of even cardinality
  \item the class of all sets of odd cardinality
\end{enumerate}
%
\item Prove that $S=(S\cap T)\cup (S-T)$
%
\item
Write a formula for $|S_1\cup S_2\cup S_3|$ in terms of
 $|S_1|,|S_2|,|S_3|,|S_1\cap S_2|,|S_1\cap S_3|,|S_2\cap
 S_3|,|S_1\cap S_2\cap S_3|$. Prove that your formula is correct.
%
\item Consider the non negative integers
$N=\{0,1,2,\ldots \}$ and define $i\equiv j$ if remainder of i
divided by 5 equals the remainder of $j$ divided by 5.
\begin{enumerate}
  \item Is the relation reflexive, symmetric and transitive?
  \item What are the equivalence classes?
  \item Select the smallest integer in each equivalence class to
  represent the equivalence class.  Let $(i)_{mod}$ be the
  representative for the class containing $i$. Prove the following
  statements.  $(i)_{mod}+(j)_{mod}=(i+j)_{mod}$ and $(i)_{mod} \times
  (j)_{mod} =(i\times j)_{mod}$.
  \item Which are valid statements?
  \begin{enumerate}
  \item $(5)_{mod}=(10)_{mod}$
  \item $(6)_{mod}=(7)_{mod}$
  \end{enumerate}
  \item Write out the addition and multiplication
  tables for the representative elements of the equivalence classes so
  that $(i)_{mod}+(j)_{mod}=(i+j)_{mod}$ and $(i)_{mod} \times (j)_{mod}
  =(i \times j)_{mod}$
  \item How can one add negative numbers to this system?  That is,
  replace $N$ by $Z$.
\end{enumerate}
%
\item List three groups besides $(Z,+)$.
%
\item  Consider the set of all two by two matrices of
real numbers and the operation of multiplication given by
\[
\left(\begin{array}{cc} a&b\\c&d
\end{array}\right)
\left(\begin{array}{cc} e&f\\g&h
\end{array}\right)=
\left(\begin{array}{cc} ae+bg&af+bh\\ce+dg&cf+dh
\end{array}\right)
\]
Does the set of $2\times 2$ matrices whose elements are real numbers
form a group under multiplication?  Is it commutative?
%
\item Prove that $S^*=\bigcup\limits_{i=0}^\infty S^i$ is the smallest set
containing $S\cup \{\epsilon\}$ and closed under concatenation.
\end{enumerate}
%========================================================================
\end{document}
