\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{utf8}

\topic{Cardinality, Equivalence, Order, Induction}
\homework{6}

\begin{document}
\maketitle

\begin{exercises}
\item
Prove that if $X$ is an infinite set, then $|\mathbb{N}| \leq |X|$.

\item
Let $X$ be an arbitrary set.
\begin{enumerate}
\item Prove that ``$|A| = |B|$'' is an equivalence relation on the subsets of $X$. (You don't need to prove that any of the functions you propose are bijections, though of course they should be.)
\item Let $[A]$ denote the equivalence class of $A$ under this relation (that is, the set of all subsets of $X$ with the same cardinality as $A$). Define $[A] \preceq [B]$ if and only if $|A| \leq |B|$.
\begin{enumerate}
\item Prove that $\preceq$ is well-defined. That is, for any $A' \in [A], B' \in [B]$, we have $|A'| \leq |B'|$ if and only if $|A| \leq |B|$.

\item Prove that ``$[A] \preceq [B]$'' is a partial order on the equivalence classes. (You may use the Cantor-Schr\"oder-Bernstein Theorem without proof.)
\end{enumerate}

\end{enumerate}

({\bf Thought for the Homework} (not for points, we won't grade your answer): Is ``$[A] \preceq [B]$'' a total order?)

\item A {\em group} consists of a set $X$ and a binary operation $\circ$ with the following four properties:
\begin{itemize}
\item {\bf Closure:} For all $a, b \in X$, it is the case that $a \circ b \in X$
\item {\bf Associativity:} For all $a, b, c \in X$, it is the case that $(a \circ b) \circ c = a \circ (b \circ c)$
\item {\bf Existence of Identity:} There is some element $e \in X$ such that $e \circ a = a \circ e = a$ for all $a \in X$.
\item {\bf Existence of Inverse:} For every $a \in X$, there is some $b \in X$ such that \mbox{$a \circ b = b \circ a = e$}.
\end{itemize}

Let $A$ be any set and define a {\em permutation} of $A$ as a bijection from $A$ to itself. Let $G$ be a set of permutations of $A$ (not necessarily the set of {\em all} permutations) that forms a group under the operation of function composition. Define the relation $\sim$ on $A$ as:
\[
x \sim y \textrm{ if and only if there is some } g \in G \textrm{ such that } y = g(x)
\]
Prove that $\sim$ is an equivalence relation.

({\bf Hint:} While $G$ must by definition have an identity element and inverse elements, we don't know at the outset that these are the identity function and (two-sided) inverse functions respectively. Start by proving that the identity element of the group must be the identity function $id : x \mapsto x$. For this particular problem, you don't {\em have} to prove that the group inverse of $g \in G$ is the two-sided inverse function $g^{-1}$, although that's one way to approach the problem. It's quite easy to prove this once you've handled the identity element.)

\item
Let $n \in \mathbb{N}$ be any natural number, and $x \in \mathbb{R}$ be any non-zero real number. We will ``prove'' by strong induction on $n$ that $x^n$ always equals 1. It is clear that $x^0 = 1$, so the base case is true. Now assume the result holds for all $k$ up to and including $n$. Then
\[
x^{n + 1} ~=~ \frac{x^n \cdot x^n}{x^{n - 1}} ~=~ \frac{1 \cdot 1}{1} ~=~ 1
\]
Hence proved by induction.

Explain, in one (short) sentence, the error in this proof.

\item Prove the following identities by induction on $n$. You may use any result proved in class without proof.
\begin{enumerate}
\item $\left(1 - \frac{1}{4}\right)\left(1 - \frac{1}{9}\right) \dots \left(1 - \frac{1}{n^2}\right) = \frac{n + 1}{2n}$
\item $1^3 + 2^3 + 3^3 + \dots + n^3 = (1 + 2 + 3 + \dots + n)^2$
\end{enumerate}

\item $2n$ spectators stand around the perimeter of a soccer field. (Assume each spectator is right on the touchline, no one is standing behind someone else.) $n$ spectators support the Away team, and the remaining $n$ support the Home team. A journalist starts at some point on the perimeter and goes clockwise all the way round the field, keeping track of how many fans of each team she has seen so far. Prove {\bf \em by induction}: she can always pick a point to start so that at every stage of her roundtrip, she has seen at least as many Home fans as Away fans.

\end{exercises}

\end{document}
