Exercises for Week 2

Due Tuesday, January 22
  1. Given sets $A$ and $B$, prove that the Cartesian product $A \times B$ defined as $\{(x,y) :x \in A \mathbin{\And} y \in B\}$ exists as a set, without using the Power Set Axiom. Hint: Use replacement. First prove that $A \times \{y\}$ exists for every $y \in B$.
  2. Let $S$ denote the successor function given by $S(x) = x \cup \{x\}$. Given a set $A$, prove that the class $\{S(x) : x \in A\}$ exists as a set, without using replacement. Hint: consider $\{y \in B : y = S(x) \text{ for some }x\in A\}$ for a sufficiently large set $B$.
  3. Show that the successor function $S$ is injective (one-to-one). Hint: given the value of $x\cup \{x\}$ we want to figure out what $x$ was. Does $x \cup \{x\}$ have a unique $\in$-minimal element, or a unique $\in$-maximal element?
  4. Show that if $x$ is transitive then so is $S(x)$.