
% Math 320 hw3
%
\documentclass{article}
\pagestyle{empty}
\usepackage[textheight=10in]{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{hyperref}
\newtheorem{theorem}{Theorem}
\newcommand{\coursehome}
{http://www.cs.umb.edu/~eb/320}
\title{Discrete Mathematics \\
Homework 4
}
\author{Ethan Bolker}
%\date{September 1, 2014}
\newcommand{\ZZ}{\mathbb{Z}}
%create (mod n) macro
\newcommand{\mm}[1]{%
\ensuremath{(\text{mod } #1)}}

\begin{document}
\maketitle
\noindent

Due: ???

This homework covers p
\section*{Exercises}

\begin{enumerate}

\item Is forming the Cartesian product of two sets a commutative operation?

% I corrected the spelling of "Cartesian".

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$. 
\end{proof}

Recall that $S \times T$ is itself a set, whose elements consist of all the ordered pairs $(a,b)$ where $a\in S$ and $b \in T$.

Let's try a few examples.

Let $S=\{1,2\} $ and let $T=\{1,2,3\}.$  

Then $S \times T = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)\} $ and 

$T \times S = \{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\}$. 

 $(1,3),(2,3) \in S \times T, \; \notin T \times S$ and 
 
 $(3,1),(3,2) \in T \times S, \; \notin S \times T$ so 
 
 $S \times T \ne T \times S.$
 
 In spite of the cross products not being equal, they do share something in common. $|S \times T| = |T \times S| = |S| \times |T| = |T| \times |S| = 6,$ since multiplication of natural numbers \emph{is} commutative.
 
 $S \times T \;\cap \; T \times S = \{(1,1),(1,2),(2,1),(2,2)\} \ne S \times T$ or $T \times S$, so for that reason also $S \times T \ne T \times S.$  
 
 Don't forget that the order elements are listed in a set is irrelevant,  $S=\{1,2\}=\{2,1\}$.  However, the following elements are not equal: $(1,2)\ne (2,1).$

From that example, you should see that when $|S| \ne |T|, $ then $S \times T \ne T \times S.$

Does $S \times T = T \times S$ when $|S| = |T|$?

Let $S=\{0,1\}$ and $T=\{a,b\}.$  So $|S|= |T| = 2.$  Then 

$S \times T = \{(0,a),(0,b),(1,a),(1,b)\}$ and 

$T \times S = \{(a,o),(b,0),(a,1),(b,1)\}$, so $S \times T \ne T \times S.$ 

But if we let $a=0$ and $b=1$, then $T = \{0,1\} = S$ so 

$S \times T = \{(0,0),(0,1),(1,0),(1,1)\} = T \times S = S \times S = T \times T.$

We've seen that $\emptyset $ has interesting and sometimes non-intuitive properties, so we should investigate when either $S$ or $T = \emptyset,$ does $S \times T = T \times S?$ 

Let $T = \emptyset.$  Does $S \times \emptyset = \emptyset \times S?$  $S \times T$ are all the ordered pairs $(a,b)$ where $a \in S$ and $b \in T$, except there is no $b \in \emptyset$ so $S \times \emptyset$ consists of all $a \in S$, namely $S$ itself.  This argument also holds for $\emptyset \times S = S.$

This gives us enough information to state and prove the theorem.

% I don't know how to make this also into Theorem 1.

\begin{theorem}
$S \times T = T \times S$ if and only if 1) $S = T$, or 2) if $S$ or $T = \emptyset.$

\begin{proof}

In 1), if we let the statement $"S \times T = T \times S" = A $ and the statement $"S=T" = B,$ then we want to show that $A \to B$ and $B \to A.$  First we show $B \to A.$

Trivially, if $S = T$ then $S \times T = T \times S.$

Now we have to prove $A \to B$.  It's a fact of logic that if the statement "If $A$ then $B$ is true", then the statement "if not $B$, then not $A$" is also true.  This is called the \emph{contrapositive} of the original statement.  If a statement is true, then so is its contrapositive.  We'll prove $A \to B$ by proving $ \neg B \to \neg A$, where $\neg A$ is "not $A$."

If $S \ne T,$

Case 1\footnote{We could probably do this in one step, but breaking it down into two cases will make it easier to understand.}: $|S| \ne |T|.$

Let a typical element of $S \times T$ be $(s,t),$
 and $(t,s)$ for $T \times S.$
 
In $S \times T,\; s$ will have $|S|$ choices and $t$ will have $|T|$ choices, while the opposite will be true for $T \times S$, so $S \times T \ne T \times S.$

Case 2: $|S| = |T|.$

Since $S \ne T$, there is at least one $x \in S, \; \notin T$ (and at least one $y \in T, \; \notin S$).

The element $(x,t) \in S \times T$ but $\notin T \times S$ (and the element $(s,y) \in T \times S$ but $ \notin S \times T$), so $S \times T \ne T \times S.$

We've already proved 2), because earlier we showed that $S \times \emptyset = \emptyset \times S$.

Therefore, $S \times T = T \times S$ if and only if $S = T,$ or if $S$ or $T = \emptyset.$

\end{proof}
\end{theorem}

When $|S| = |T| = 2$ we equated the elements in $T$ with $S$ to make the sets equal.  But we can do this for any pair of sets having the same number of elements, $|S| = |T| = n.$  We don't even have to go as far as setting elements in one set equal to the other set, but can just set up a correspondence between the two sets, which we know is called a bijection.  As we saw with infinite sets, if we can find a bijection between two sets, then they're then same size.  When mathematicians study sets of unknown size, if they can find a bijection between those sets and those whose size is known, then they'll know size of the original set. When we find this bijection, we call the sets \emph{isomorphic}, $S \cong T.$  Like 'congruent' this is another kind of 'equals', which is also an equivalence relation.

$A \cong A.$ \quad Reflexive

If $A \cong B$, then $B \cong A.$ \quad Symmetric

If $A \cong B$ and $B \cong C$, then $A \cong C.$ \quad Transitive

An isomorphism is an equivalence of structure between two sets.  Comparing sizes of sets through bijections is useful when that's all you're looking for, but isomorphisms get more interesting when the structure between the two sets is more complicated.  One way we can do this is by introducing binary operations on each set and still show they have a correspondence.

For example, let $A = \{0,1,2,3,4\}$ and let $B=\{0,2,4,6,8\}$.  Let the operation in $A$ be 'addition mod 5' and let the operation in $B$ be 'addition mod 10'.  You should see that the element $x \in A$ corresponds to the element $2x \in B$ even under addition.

%I couldn't figure out how to set up their addition tables.

If you go on to take Abstract Algebra (Math 360), you will find isomorphisms between more complicated mathematical objects.


\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.

Recall that $A \oplus B = (A \cup B) - (A \cap B).$  In other words,
all elements that are in $A$ or $B$ exclusively, but not in both.
Also, $A \oplus B = B \oplus A$, so $\oplus$ is commutative. 

To show that $\oplus$ is associative, we need to show that $(A \oplus
B) \oplus C = A \oplus (B \oplus C).$ 

As stated, $A \oplus B $ is everything in $A$ xor $B$.  If we then
apply $\oplus $ from that set to $C$, we will have the set of elements
that are exclusively in $A, B$ and $C$, but not in any of their
intersections.  This set is symmetric, which implies that $\oplus$ is
independent of grouping.  $B \oplus C$ is all the elements exclusively
in $B$ xor $C$.  When applied to $A$, again we get the set of elements
that are exclusively in $A, B$ and $C$, but not in any of their
intersections. 

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

Since $A \oplus B$ = $A \cup B - A \cap B$, letting $B = I$ we need tolpl find $I \subseteq U$ such that $A \oplus I$ = $A \cup I - A \cap I = A.$  If $A \cap I \ne \emptyset,$ then $A \oplus I \ne A$.  Therefore $A \cap I = \emptyset.$  However, if $I \ne \emptyset$, then $A \oplus I = A \cup I \ne A.$  Therefore, $I = \emptyset.$  Since $\oplus$ is commutative, then also $I \oplus A = A.$

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

Since $\oplus$ subtracts everything in common between two sets, if $A \oplus B = \emptyset,$ then $B=A$.

In the language of abstract algebra, $\emptyset$ is the identity under $\oplus$, and the inverse of each $A$ under $\oplus$ is also $A$.  In other words, $A$ is its own inverse.  $A^{-1} = A.$  $A$ is any set, so under $\oplus$, \emph{every} set is its own inverse.

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

Just saying ``true'' (or ``false'') isn't an answer. You must explain why.

$A \oplus B$ is a set that consists of two disjoint subsets, those elements that are just in $A$, call that $\bar{A}$ and those elements just in $B$, $\bar{B}.$  Since $\bar{A} \cap \bar{B} = \emptyset, \bar{A} \cup \bar{B} = \bar{A} + \bar{B}.$  If $\bar{A} + \bar{B} = \bar{A} + \bar{C},$ then $\bar{B} = \bar{C}$.  If everything that's exclusively in $B$ is also everything that's exclusively in $C$, then $B = C$.

\end{itemize}

Hints:
\begin{itemize}
\item If you have taken or are taking abstract algebra lots of this
  should look familiar.

\item Thinking about how $\oplus$ works with the bit vector
  representation of subsets might save you a lot of thinking and
  writing.
\end{itemize}

\end{enumerate}

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