% Math 320 hw4
%
\documentclass{article}
\pagestyle{empty}
\usepackage[textheight=10in]{geometry}
\usepackage{mathtools, nccmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{verbatim}
% hyperref should be (nearly) the last package loaded
\usepackage{hyperref}
\usepackage{xparse}
%This very cool macro comes from
%http://tex.stackexchange.com/questions/209863/how-to-add-mathematical-notation-of-a-set
%
% \set{ stuff ; something }
% expands to
% { stuff | something }
%
\DeclarePairedDelimiterX{\set}[1]{\{}{\}}{\setargs{#1}}
\NewDocumentCommand{\setargs}{>{\SplitArgument{1}{;}}m}
{\setargsaux#1}
\NewDocumentCommand{\setargsaux}{mm}
{\IfNoValueTF{#2}{#1} {#1\,\delimsize|\,\mathopen{}#2}}%{#1\:;\:#2}
\newtheorem{theorem}{Theorem}
\newcommand{\coursehome}
{http://www.cs.umb.edu/~eb/320}
\title{Discrete Mathematics \\
Homework 4
}
\author{Jiho Choi}
%\date{September 1, 2014}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
%create (mod n) macro
\newcommand{\mm}[1]{%
\ensuremath{(\text{mod } #1)}}
\begin{document}
\maketitle
\noindent
Due: December 2, 2014

\section*{Exercises}
\begin{enumerate}
\item Is forming the cartesion product of two sets a commutative
operation?
Let $S$ and $T$ be sets. Investigate when/whether
%
\begin{equation*}
S \times T = T \times S .
\end{equation*}
Start this problem by working a few small examples! When you
understand what’s going on, write your answer as a theorem like this:
\begin{theorem}
$S \times T = T \times S$ if and only if [something] or [something else].
\end{theorem}
\begin{proof}
Suppose $S \times T = T \times S$. Then \ldots so something or
something else is true.
Conversely, suppose neither something nor something else is true. Then
\ldots so
$S \times T \not = T \times S$.


Suppose that a set S = {1,2} and another set T = {3,4}. Then,
the Cartesian product $S \times T$ = {{1,3},{1,4},{2,3},{2,4}}, but 
$T \times S$ = {{3,1},{3,2},{4,1},{4,2}}. So, Cartesian product is
not commutative for this case. Let's see another example. 
Suppose that a set S = {1,2} and another set T ={1,2}.
Then, $S \times T$ = {{1,1},{1,2},{2,1},{2,2}}, and $T \times S$ =
{{1,1},{1,2},{2,1},{2,2}}. So, Cartesian product is commutative 
for this case. \\

In general, $S \times T = T \times S$ if and only if $S = T$.

Suppose $S \times T = T \times S$. Let $x \in S$ and $y \in T$.
Then, $(x,y) \in S \times T$ and $(x,y) \in T \times S$ by hypothesis.
So, $x \in S$ and $y \in T \rightarrow x \in T$ and $y \in S$.   
Therefore, if $S \times T = ST \times S$, then $S = T$.\\

Conversely, suppose that $S \neq T$. Let $x \in S$ and $y \in T$. 
Then $(x,y) \in S \times T$ and $(y,x) \in T \times S$. However, 
$(y,x) \notin S \times T$ since y is not necessarily an element in
$S$. Therefore, if $S \neq T$, then $S \times T \neq T \times S$.\\

Consequently, $S \times T = T \times S if and only if S = T$.

\end{proof}
\item The algebra of symmetric differences.
We’ll use $A \oplus B$ for the symmetric difference of subsets $A$ and
$B$ of a universe $U$.\begin{itemize}
\item Show that $\oplus$ is associative.

Suppose that sets $A = 10101, B = 11001, and C = 00110$. Here, each of them
is binary expression. In each digit, 1 means the presence of some 
element in each set and 0 means the absence of some element.
Since $A \oplus B = (A - B) \cup (B - A)$, $A \oplus B = 00100 \cup 01000
= 01100$.\\ 

$(A \oplus B) \oplus C$ = $01100 \oplus 00110 = 01000 \cup 00010 = 01010$.
$A \oplus (B \oplus C)$= $10101 \oplus 11111 = 00000 \cup 01010 = 01010$.
Thus, $(A \oplus B) \oplus C = A \oplus (B \oplus C)$.
So, $\oplus$ is associative.


\item Find a subset $I \subseteq U$ such that for every $A$ we have $A
\oplus I = A$.

Suppose $p \in A \oplus I$. Then, p is either an element of A or I,
but not both. $A \oplus I = (A - I) \cup (I-A)$.\\

First case, if $p \in A$, then $p \in (A - I)$, but not in $(I - A)$.
To be $A \oplus I = A$, (A - I) has to be equal to A. 
Therefore, $I$ has to be an empty set.\\    

Second case, if $p \in I$, then $p \in (I -A)$, but not in $(A - I)$.
To be $A \oplus I = A$, $p \in A$, but p is also an element of $(I - A)$.
In this case, $I = \phi$ is the only possibility which holds the given
condition.\\

Thus, $I = \phi$ is the answer. 


\item For each $A$, find a $B$ such that $A \oplus B = I$.

$A \oplus B$ = $(A - B) \cup (B - A)$. To be $A \oplus B = I$,
$A$ has to be equal to B since $I$ is an empty set. So, the answer
is $A = B$.  

\item True or false:
%
\begin{equation*}
\text{If } A \oplus B = A \oplus C \text{ then } B = C.
\end{equation*}

\begin{proof}
$A \oplus A = \phi$. So, $(A \oplus A) \oplus A = A$.
Also, $(A \oplus A) \oplus B = A \oplus (A \oplus B) = B$
and $A \oplus (A \oplus C) = C$. Therefore, if $A \oplus B = A \oplus C$
,then B has to be equal to C.   

\end{proof}
\end{itemize}


\item A binary relation on a set may be reflexive, symmetric or
transitive. Call those properties $R$, $S$, and $T$ for short. There are
eight possible truth value combinations for those properties. For each
of the eight, find an example. (So, for example, one of your answers
should exhibit a binary relation that satisfies $R$ and $\sim S$ and
$\sim T$.)
Please find elegant examples -- the best are either everyday situations
where the properties are obviously what you claim they are, or
binary relations built on the smallest possible finite set that will
do the job. You can use answers to previous problems when they work here.

1. $R$ and $S$ and $T$\\

This is equivalence relation. The relation $\star$ in the next question
$(a,b) \star (c,d) \Leftrightarrow ad = bc$ is an example of equivalence 
relation.\\

2. $R$ and $S$ and $\sim T$\\

If we go to South Station in Boston, there exists a bus from Boston to NYC
and a bus from NYC to Philadelphia, but there is no direct bus from Boston to 
Philadelphia. So, this relation is not transitive. There exists a bus from Boston
to NYC and NYC to Boston as well. So, this relation is symmetric. If I took the bus
from Boston to NYC, but got off before departure for some reason, this can be sort
of reflexive relation.\\

3. $R$ and $\sim S$ and $T$\\

If we have a pair of numbers, $R \times S$, with R = {1,2,3} and S = {1,2,3}, 
and a relation {{1,1}, {1,3},{3,2},{1,2},{2,2},{3,3}},
then this relation is reflexive and transitive, but not symmetric.\\

4. $R$ and $\sim S$ and $\sim T$\\

If we have a pair of numbers, $R \times S$, with R = {1,2,3} and S = {1,2,3}, 
and a relation {{1,1},{2,2}, {3,3},{1,2},{2,3}}, then this relation is
reflexive, but neither symmetric nor transitive.\\

5. $\sim R$ and $S$ and $T$\\

If we have a pair of numbers, $R \times S$, with R = {1,2,3} and S = {1,2,3}, 
and a relation {{1,1},{1,2},{2,1},{1,3},{3,1}}, then this relation is 
not reflexive, but both symmetric and transitive.\\

6. $\sim R$ and $S$ and $\sim T$\\

If we have a pair of numbers, $R \times S$, with R = {1,2,3} and S = {1,2,3}, 
and a relation {{1,2},{2,1},{2,3},{3,2}}, then this relation is
neither reflexive nor transitive, but is symmetric.\\

7. $\sim R$ and $\sim S$ and $T$\\

If we have a pair of numbers, $R \times S$, with R = {1,2,3} and S = {1,2,3}, 
and a relation {{1,3},{3,2},{2,3},{1,2},{3,3}}, then this relation is
neither reflexive nor symmetric, but is transitive.\\

8. $\sim R$ and $\sim S$ and $\sim T$\\

If we have a pair of numbers, $R \times S$, with R = {1,2,3} and S = {1,2,3}, 
and a relation {{1,2},{2,3},{3,1}}, then this relation is not reflexive, symmetric,
and transitive.\\

\item Let $\star$ be the relation on $\ZZ \times \ZZ$ defined by
%
\begin{equation*}
(a,b) \star (c,d) \iff ad = bc .
\end{equation*}
\begin{enumerate}
\item Describe all the pairs $(a,b)$ such that $(a,b) \star (4,6)$.

If $(a,b) \star (4,6)$, then $6a = 4b$, so $3a = 2b$. Therefore,
\[
(a,b) = \set[\big] {k \in \ZZ ; (2k, 3k)}
\]

\item Show that $\star$ is an equivalence relation.

First, $(a,b) \star (a,b) \Leftrightarrow ab = ba$.
This is true because integers are commutative with respect to multiplication.
So, the relation $\star$ is reflexive.\\

Second, if $(a,b) \star (c,d) \Leftrightarrow ad = bc$, then 
$ (c,d) \star (a,b) \Leftrightarrow cb = da$. 
This is also true for the same reason above. 
So, the relation $\star$ is symmetric.\\

Third, if $(a,b) \star (c,d)$, and $(c,d) \star (e,f)$, then 
$(a,b) \star (e,f)$. This is also true because if $ad = bc$ and $cf = de$
,then $af = be$. We can show this by multiplying two equations term by term.
$ad*cf = bc*de$, so $adcf = bcde$. If we cancel out $cd$ both term, then we
get $af = be$. So, the relation $\star$ is transitive.\\

Thus, $\star$ is an equivalence relation.  

\item Prove: given $(a,b)$ with $b \neq 0$ there is a unique pair $(m,n)$
equivalent to $(a,b)$ for which $\gcd(m,n) = 1$. (Hint, if needed:
think about the previous part of the problem.)

If b is not equal to 0, then there exists a unique pair (m,n), which 
m and n are relatively prime. In the first part of this problem, 
$a$ can be any multiples of 2 and $b$ can be any multiples of 3.
In this case, $(m,n) = (2,3)$. This is because the ratio between $a$
and $b$ is always consistent, so if we eliminate their common factors,
we can get two numbers $m$ and $n$ which are relatively prime.   

\item What happens to the previous claim when $b = 0$?

Suppose that we have $(a,0) \star (c,d)$. Then, we get the equation
$ad = 0$. If $a = 0$, then $c$ and $d$ can be any integers, and if $d = 0$,
then $a$ can be any integers. Thus, we cannot determine a unique pair (m,n)
if $b = 0$.

\item Show that there is a bijection between $\QQ$ (the rational
numbers) and the partition corresponding to $\star$.

If we allow division for the equation $ad = bc$, we get $\frac{a}{b} = \frac{c}{d}$
with $b$ and $d$ are not equal to zero. Rational numbers are expressed as the
quotient of two integers with denominator is not equal to zero.
We can make a partition based on two integers $m$ and $n$ which are relatively prime.
For example, if $(m,n) = (1,2)$, then the partition for $(1,2)$ can be 
$\frac{1}{2}, \frac{2}{4}, \frac{3}{6}, \ldots$. The numerators are multiples of 
$1$, and the denominators are multiples of $2$ in this case. Therefore, if we
choose two numbers $m$ and $n$ which are relatively prime, we can construct
the whole list of rational numbers by making their partitions.\\

So, there is a bijection between $\\QQ$ and the partition corresponding to $\star$.



\end{enumerate}\item For each of the following sets, provide an argument showing that
it’s countable, or that it’s not.
\begin{enumerate}
\item The set of all partitions of $\NN$.

The cardinality of the power set of $\NN$ is not countable. Partitions 
split the power set of natural numbers into a disjoint union of subsets.
The power set of a finite set has $2^{n}$ elements. After I looked over
Wikipedia, the Bell numbers, which we use to count the number of partitions,
are growing much faster than the $n^{th}$ power of two. So, I think that 
the cardinality of the set of all partitions of $\NN$ is greater than
the cardinality of the power set of natural numbers. So, I would conclude 
that the set of all partitions of $\NN$ is uncountable.


\item The set of all partitions of $\NN$ into a finite number of
blocks.



\item The set of all partitions of $\NN$ for which each block is finite.



\end{enumerate}
\item Counting computer programs
Each of these questions can be answered in a sentence or two if you
really understand the work we did in class on counting infinities.
\begin{enumerate}
\item Show that there are only countably many finite strings of (ascii)
characters.


\item Show that in any particular programming language there are only
finitely many computer programs that accept an integer as input and
produce a boolean value as output.




\item Show that there are uncountably many functions from $\ZZ$ to
$\set{T,F}$.



\item Show that for any particular computer language there are
functions from $\ZZ$ to $\set{T,F}$ that can’t be implemented by a
program in that language.



\item If you have a language and a function that can’t be computed
using that language you can create a new and better language to
compute it. If you do that over and over again will you have a
language that computes all functions?




\end{enumerate}
\end{enumerate}
\newpage
\verbatiminput{\jobname}
\end{document}
