Exercises for Week 8

If you haven't turned it in yet, please try to turn it in by Saturday so that I can grade it by Monday. You can e-mail it to me or (if you're in the vicinity) put it under the door to my office.

1. Let $E$ be a well-founded and set-like relation on a class $P$. Let $G : V \to V$. Show that there is a unique function $F: P \to V$ such that for all $x \in P$ we have $$F(x) = G(F \restriction \{y \in P : y \mathbin{E} x\}).$$
2. Let $T$ be a theory (a collection of sentences) and let $A$ be a sentence. Show that at least one of the theories $T + A$ and $T + \neg A$ is consistent relative to $T$. (Do not use any notions from model theory such as satisfaction or the completeness theorem. You should be able to prove this using only some basic informal reasoning about proofs.)
3. 1. For each of the notions "$z = \{x,y\}$", "$z = \bigcup y$", and "$z$ is inductive" find a $\Delta_0$ formula that expresses it. (The word "expresses" here is slightly vague, but that's okay: the point of this part is just to make it easy to prove the next part using $\Delta_0$-absoluteness.)
   2. Work in $\mathsf{ZF} - \text{Foundation}$. Show that the axioms of Pairing, Union, and Infinity hold in the class $\text{WF}$, defined as $\bigcup_{\alpha\in \text{Ord}} V_\alpha$ where $V_0 = \emptyset$, $V_{\alpha+1} = \mathcal{P}(V_\alpha)$, and $V_\lambda = \bigcup_{\alpha \lt \lambda}$ for $\lambda$ a limit ordinal.
4. For each of the axioms Pairing, Union, and Infinity, find a transitive class in which the axiom does not hold. (It's okay if some of the other axioms fail in your class too.)

   Remark: This argument shows that none of these axioms is logically equivalent to a $\Delta_0$ formula. In fact, because Extensionality holds in every transitive class, this argument shows the stronger statement that none of these axioms is equivalent modulo the axiom of extensionality to a $\Delta_0$ formula.