\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{7: Set Theory}{Due Friday, Week 4}

Do \textbf{three} of the \textbf{six} problems below!

\begin{enumerate}
\item In class, someone asked if it was possible for a set $A$ to contain itself: in other words, if $A \in A$ is possible given our rules for sets!  

Surprisingly, it turns out that our existing axioms are not strong enough to stop this from happening.  However, the idea of a set containing itself is kind of bothersome, so mathematicians decided to create the following axiom:
\begin{axiom}
(Axiom of Foundation) Every nonempty set contains an element that is disjoint from the original set.  In symbols:
\begin{align*}
\forall A, \left( (A \neq \emptyset) \Rightarrow ( \exists x (x \in A) \wedge (x \cap A = \emptyset)) \right)
\end{align*}
\end{axiom}
Suppose you have this axiom, along with the other axioms we've created thus far (empty set, pairing, union, power set, comprehension, infinity.)  Prove that it is impossible for $A \in A$ to hold for any set $A$.
\item A related impossible object is an infinite sequence of nested sets, defined as follows: we call $A$ an \textbf{infinite sequence of descending sets} if for any $x \in A$, there is some other $y \in A$ such that $x \in y$.  The idea is that if such a set existed, we could build an infinite\footnote{Side note: the LaTeX command for the backwards ``$\in$,'' ``$\ni$,'' is ``\textbackslash ni.''  This is adorable.} chain 
\begin{align*}
x_1 \ni x_2 \ni x_3 \ni x_4 \ni \ldots
\end{align*}
by repeatedly picking for each set $x_i$ the next set $x_{i+1}$ such that it's in $A$ and contained by $x_i$.  

This seems awful, right?  Show that such a set cannot exist, if you have the above axiom of foundation along with all of our other axioms.
\item We constructed the natural numbers as follows:
\begin{itemize}
\item Take any inductive set $S$ (one must exist, by the axiom of infinity.)
\item Using power set, form the collection of all subsets of this inductive set, $\mathcal{P}(S)$.
\item Using comprehension, form the subset $T$ of $\mathcal{P}(S)$, consisting of all of the subsets of $S$ that are inductive.
\item Again using comprehension, take the intersection of all of the elements of $T$.
\item Call this set $\mathbb{N}_S$.
\end{itemize}

In class, we claimed that this set didn't really care about $S$, in the following sense: for any two inductive sets $R,S$, we proved that $\mathbb{N}_R = \mathbb{N}_S$.  As part of this proof, we looked at the intersection $C = \mathbb{N}_R \cap \mathbb{N}_S$ of these two sets, and claimed that this intersection was inductive --- however, we left the proof of this claim for the homework!

Prove this here: for any two inductive sets $S, T$, show that $C = \mathbb{N}_R \cap \mathbb{N}_S$ is an inductive set.  (Hint: as with all problems involving definitions, show that $C$ satisfies the definition of being an inductive set.)

\item Suppose that $a, b$ are members of the natural numbers $\mathbb{N}$ as defined via sets in class thus far -- that is, think of elements of $\mathbb{N}$ as sets, i.e.\ $0 = \emptyset, 1 = \{\emptyset\}, 2 = \{\emptyset, \{\emptyset\}\}$, \ldots.  Also suppose that $b \in a$.  Prove that $a$ is not a subset of $b$: in symbols, $a \not\subseteq b$.

\item Assume that $\mathcal{P}(A) = \mathcal{P}(B)$.  Prove that $A = B$.

\item Given any set $A$, we can always form by the union axiom the set
\begin{align*}
\bigcup A := \bigcup_{A' \in A} A'.
\end{align*}
Suppose that $A, B$ are elements of $\mathbb{N}$ such that $A = S(B)$, where $S$ is the successor function $S(B) = B \cup \{B\}$.  Prove\footnote{In this sense, $\bigcup$ ``undoes'' successor; if the successor function is like $+1$ on the natural numbers, then $\bigcup$ is like $-1$.} that the set $\bigcup A$ is equal to the set $B$.  

(Hint: form the collection $X = \{B \in \mathbb{N} ~|~ \bigcup S(B) = B\}$, using our axioms.  If you can show this is an inductive set, what can you conclude?)
\end{enumerate}
\end{document}