Skolem proved the need for the axiom schema of Replacement by, in essence, showing that $V_{ω+ω}$ is a model of Zermelo's set theory Z (the smallest "natural" model) and, hence, that the existence of the set $\{ω, ℘(ω), ℘(℘(ω)), ...\}$ is independent of Z (where ω is understood to be the usual von Neumann ordinal). Now, Skolem's independence proof depends on the fact that $ω$ is already of infinite rank and, hence, that the above set will be unbounded in $V_{ω+ω}$. But now let ZU be Z + Urelements and an axiom asserting that the urelements form a set A, and consider the set $A^\ast = \{A, ℘(A), ℘(℘(A)), ...\}$. The members of $A^\ast$ are all of finite rank, so Skolem's proof doesn't seem to apply here — $A^\ast$ will exist in $V'_{\omega+1}$, where $V'_{\omega+\omega}$ is the cumulative hierarchy up to $\omega+\omega$ starting with $A$ (which I assume is the smallest natural model of ZU with $V'_0 = A$). Nonetheless, it seems to me (= Not A Set Theorist) that proving in general that $A^*$ exists should require Replacement as well. But I don't see how to show this. If A is assumed to be finite, we can show that $A^\ast$ exists without Replacement by coding all the hereditarily finite sets in $V'_\omega$ as finite ordinals and relying on the fact that inductively defined functions from ω into ω are all legit in ZU (in particular the function $n \mapsto V'_n$). Such a coding is obviously out of the question if A is infinite. I reckon the proof, if there is a proof, that the existence of $A^\ast$ is independent of ZU would involve constructing an inner model of ZU in which $A^\ast$, or whatever is playing its role, is missing from the $\omega+1^\text{th}$ level, but figuring out how to do that is a bit beyond my abilities. Any help appreciated.
2 Answers
If you start with the elements in $V_{\omega+1}$ and a nonempty set $A$ of urelements, and then simply close under pairing, unions and power sets, you get a model of Zermelo + urelements, but where $A^*$ doesn't exist, even when $A$ is finite, since it doesn't appear after any finitely many applications of pairing, unions and power set (despite your remarks about coding). So you don't avoid the problem by considering urelements. You still need replacement to prove $A^*$ exists, even when $A$ is finite.
-
$\begingroup$ Yes, it seems we posted the same construction at the same time. I had wanted to emphasize that the construction works even when $A$ is finite, which is contrary to the OPs remarks. $\endgroup$ Commented Feb 2, 2017 at 3:57
-
$\begingroup$ This is great, thank you! But I'm now confused as to why my coding trick wouldn't work for A finite. Am I wrong that Z can prove the recursion theorem for functions on ω? My fuzzy recollection is that, for any inductively defined function f : ω ⟶ ω, you can prove the existence of all the finite "approximations" of f (i.e., f up to some n) in Z and then extract the set of them from ℘(ωxω) by Separation and weld them together via Union to get f. Where am I going off the rails here? $\endgroup$ Commented Feb 2, 2017 at 4:23
-
$\begingroup$ Never mind, I think I was confused about my coding idea. $\endgroup$ Commented Feb 2, 2017 at 4:37
-
2$\begingroup$ The issue is that you need replacement to undertake the decoding. $\endgroup$ Commented Feb 2, 2017 at 12:00
Your intuition is right. We can modify Skolem's argument as follows:
Let $W_0=V_\omega\cup A$, and let $W_{n+1}=\mathcal{P}(W_n)\cup W_n$ for $n\in\omega$. Finally, let $W=\bigcup_{n\in\omega}W_n$. Then $W\models ZU$, but $A^*\not\in W$.
Note that this is really the same as Skolem's argument: $V_{\omega+\omega}$ should be thought of as "The $V_\omega$-operator done to $V_\omega$," and similarly we're here looking at "The $V_\omega$-operator done to $V_\omega\cup A$."
