Due: October 6th, 2017

## Math 142A Assignment 1

Answers to these problems are now available here. The $\LaTeX$ file used to produce them is here.

1. #### The Tower of Hanoi

The Tower of Hanoi is a puzzle invented by Édouard Lucas in 1883. It consists of three pegs and several wooden discs of various sizes with holes cut in their centres so that they may be placed over the pegs. At the beginning of the puzzle, all of the discs are stacked on the leftmost peg, in order of decreasing size so that the smallest disc is at the top. The goal of the puzzle is to move all of the discs to the rightmost peg. However, only one disc may be moved at a time, and no disc may be placed on top of a disc which is smaller than it.

Prove that an optimal solution to a Tower of Hanoi with $n$ discs requires $2^n-1$ moves; that is, prove that no solution may use fewer moves, and that it is possible to solve it with this number of moves.

2. Let $S \subseteq \mathbb{R}$ be a subset of the real numbers. An element $a \in S$ is said to be a maximum of $S$ if it is an upper bound for $S$.

1. Prove that if $a\in S$ is a maximum of $S$, then $a = \sup S$.
2. Give an example of a non-empty set which is bounded above but has no maximum element.
3. Show that every non-empty finite set has a maximum element.
3. Determine whether each of the following statements is true or false, and provide a brief justification of your answer:
1. The empty set $\emptyset$ is bounded above by $5$.
2. Every element of the empty set $\emptyset$ is positive.
3. Every element of the empty set $\emptyset$ is negative.
4. If $S$ denotes the set $S := \{x \in \mathbb{R} | x^{-1} \in \mathbb{N}\}$ and $\alpha := \inf S$, then $\alpha > 0$.
5. Every real number is the least upper bound of some set of rational numbers.
6. For any real number $c$, the interval $\left(c - \frac{1}{4}, c + \frac{1}{4}\right)$ contains a rational number of the form $\frac{a}{3}$ with $a \in \mathbb{Z}$.
1. Show that there is a one-to-one and onto function from the integers $\mathbb{Z}$ to the natural numbers $\mathbb{N}$.
2. Show that there is a one-to-one function from the set of ordered pairs $\mathbb{N}^2 := \{(a, b) | a \in \mathbb{N}, b \in \mathbb{N}\}$ to the natural numbers $\mathbb{N}$. (Hint: you may use the fact that every natural number may be expressed as a product of prime numbers in a unique way; so, for example, if $2^s = 2^t$ then $s = t$.)
3. Show that there is a one-to-one function from the positive rational numbers $\mathbb{Q}_+ := \{\frac{a}{b} \in \mathbb{R} | a, b \in \mathbb{N}\}$ to the natural numbers $\mathbb{N}$. (Hint: you may use the previous part of this problem, and the fact that any positive rational number has a unique expression of the form $\frac{a}{b}$ where $a, b \in \mathbb{N}$ have no common factor.)

It turns out that there is no one-to-one function from the positive real numbers to the natural numbers. This fact was first demonstrated by Georg Cantor in the late 1800's. For more details, look up the Cantor diagonal argument.

4. Suppose that $f : A \to B$, and $Y \subset B$. We define the preimage of $Y$ to be the set $f^{-1}(Y) := \{x \in A | f(x) \in Y\}$. Likewise, recall that for $X \subset A$, the image of $X$ is the set $f(X) := \{f(x) \in B | x \in X\}$.
1. Show that for any $X \subset A$, $X \subseteq f^{-1}\left(f(X)\right)$.
2. Show that $f$ is one to one if and only if for every subset $X \subset A$, we have $f^{-1}\left(f(X)\right) = X$.
3. Show that $f$ is onto if and only if for every subset $Y \subset B$, we have $f\left(f^{-1}(Y)\right) = Y$.