% 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{Ethan Bolker}
%\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: ???

This homework covers problems in an area loosely called ``sets and
functions''. You can read about it in B\&W at
\url{http://cseweb.ucsd.edu/~gill/BWLectSite/Resources/C1U4SF.pdf}.

I will add to this homework from time to time.

See the source code for some cool \verb+\set+ macros to construct
these sets in \LaTeX: 

\[
D = \set{x \in \NN ; 1\leq x\leq 100} 
\]

The delimiters adjust to the size of the contents in the * version:
\[
E = \set*{x \in \QQ ; -\frac{1}{2}\leq x \leq \frac{1}{2}}
\]

You also can have a manual adjustment with an optional argument to \verb+\set+:
\[
E = \set[\big]{x \in \QQ ; -\mfrac{1}{2}\leq x \leq \mfrac{1}{2}}
\]

And you can define sets as simple lists:
\[\text{Unit fractions}= \set*{\mfrac{1}{1}, \mfrac{1}{2},\mfrac{1}{3}, \dots } 
\]


\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$. 
\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.
\item Find a subset $I \subseteq U$ such that for every $A$ we have $A
  \oplus I = A$.
\item For each $A$, find a $B$ such that $A \oplus B = I$.
\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.
\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}

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

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

\item Show that $\star$ is not an equivalence relation, but is an
  equivalence relation if you consider only the ordered pairs in which
  the second coordinate is not $0$.

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

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

\item Show that there is a bijection betwee $\QQ$ (the rational
  numbers) and the partition   corresponding to $\star$ when the
  second coordinate is not zero.

\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$.
\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.
\footnote{I just made up this example. I don't know the answer yet.}
\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.

If you can't show this, say so. Then assume it's true and do the rest
of the problem.

\item Show that in any particular programming language there are only
  countably 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}

\item (Optional, but I'd love to see it.)

Read the fictional treatment of Hilbert's Hotel at
\url{http://www.c3.lanl.gov/mega-math/workbk/infinity/inhotel.html}.

Then rewrite the ending so that the narrator's scheme for housing the
people on the infinitely many infinite busses succeeds (as it will). Then
have the fire caused in some interesting way by the failure (discussed
in class) of any scheme that claims to accomodate all the committees
of guests.

Try to copy the author's style. 
\end{enumerate}
\newpage

\verbatiminput{\jobname}

\end{document}




