MAT511 homework,         due Dec. 3, 2003

1. Recall that in class (and in the handout copied from Eves; alternatively, a similar discussion can be found at http://www.shu.edu/projects/reals/logic/numbers.html ), we considered the equivalence relation on ${\mathbb{N}}\times{\mathbb{N}}$ given by $(a,b) \sim (c,d)$ whenever $a + d = b+c$. We said that the set of equivalence classes corresponded to the integers ${\mathbb{Z}}$, where the each natural number $n$ corresponds to equivalence class with elements of the form $(x+n,x)$ while negative integers correspond to classes of the form $(x,x+n)$.

   Show that the relation $\preceq$ given by $(a,b) \preceq (c,d) \Leftrightarrow a+d \le b+c$ defines a total order on the equivalence classes, which corresponds to the usual notion of order on ${\mathbb{Z}}$. (Recall that a total order is a partial order in which all elements are comparable.)

2. If $(a,b)$ and $(c,d)$ are representatives of two equivalence classes as above, we can define multiplication as $(a,b)\cdot(c,d) = (ad+bc,ac+bd)$. Remember that these are equivalence classes, so the statement $(2,1)\cdot(2,1) = (4,5)$ means $1\cdot 1 = 1$.

   Using this definition, show that if $n$ and $m$ are negative integers, $n\cdot m$ is a positive integer.

3. We discussed how each real numbers corresponds to a Dedekind cut, or an infinite decimal that doesn't end in all 9s. Let ${\mathcal D}$ be the set of all real numbers greater than 0 and less than 1 which don't use the digits 1, 3, 5, 7, or 9 in their decimal expansion. Show that ${\mathcal D}$ is an uncountable set.

4. Let ${\mathcal F}$ be the set of all functions from ${\mathbb{N}}$ to $\left\{{0,1}\right\}$. What is the cardinality of ${\mathcal F}$? Hint: You might find it conceptually easier to first think about the set ${\mathcal F_{10}}$ of all functions from ${\mathbb{N}}$ to $\left\{{0, 1, 2, \ldots, 9}\right\}$; ${\mathcal F}$ and ${\mathcal F_{10}}$ have the same cardinality.