# Simplest set that requires Replacement but cannot be achieved using Power-Set

I'm looking for a simple example to the use of the Replacement axiom to conclude that a certain class is a set. The simplest examples I think of can be proven also using the Power-Set Axiom, e.g the set $\{\{x\}\mid x\in A\}$ for some set $A$, and $A/E$ for an equivalence relation $E$ on a set $A$.

The first example which seem to really require Replacement, while Power-set is not enough, is e.g. $\{\varnothing,\{\varnothing\},\{\{\varnothing\}\}...\}$, but it seems that to prove this I must use a theorem on definition by recursions.

A similar example appears in this question but it seems that the proof is essentially going over the proof of the recursion theorem in the very specific case appearing there.

Is there a simpler example which doesn't require such a theorem?

(I don't need a proof that Replacement is necessary while Power-set is not enough.)

• I'm a bit confused - your second-to-last line suggests you want an example with a simpler proof, but your last sentence suggests you don't care about the proof? Commented Apr 14, 2018 at 16:03
• I want a simple proof using replacement that some class is a set, one that e.g. doesn't even invoke the recursion theorem. I want that the use of replacement can't be replaced by a use of power-set, but I don't need a simple proof of this fact. Commented Apr 14, 2018 at 16:08
• Since the recursion theorem is equivalent to replacement, I think you will never be able to find a perfectly satisfying example, then. Commented Apr 14, 2018 at 16:12
• Oh, I did not know/remember that! Commented Apr 14, 2018 at 16:14
• Existence of $\{\{x\}:x\in A\}$ is provable in ZF minus Power, minus Foundation, minus Infinity: The Pairing Axiom and Extensionality imply that $\{x\}$ exists uniquely whenever whenever $x$ exists. And $\forall A\;\forall x\in A \;\exists!y \;(y=\{x\})$ is an instance of a "Replacement" condition. So $\forall A\;\exists B\;\forall x\in A \;(\{x\}\in B)$. By Comprehension, $\forall A \;\forall B\;\exists C=\{b\in B: \exists x\in A (b=\{x\}\}.$ Commented Apr 18, 2018 at 20:00

The class of countable ordinals constitutes such an example.

Consider the following formula:

Let $\varphi(x, y)$ be the formula "EITHER $x$ is a linear ordering with domain $\subseteq\omega$, $y$ is an ordinal, and there is an order-preserving bijection between $x$ and $y$, OR $x$ is a linear ordering with domain $\subseteq\omega$, $y=0$, and there is no ordinal with an order-preserving bijection to $x$."

Now we let $A$ be the class of ordinals $y$ such that for some linear ordering $x$ with domain $\subseteq \omega$ there is an order-presreving bijection from $x$ to $y$.

• Using replacement, $A$ is a set: apply replacement to the formula $\varphi$ with the "starting set" being the set $S$ of linear orderings with domain $\subseteq\omega$.

• Without replacement, we cannot show that $A$ is a set: in $V_{\omega+\omega}$ we have $A=Ord$.

NOTE: This is an example of a more general recipe: given an attempt to build an object $\mathfrak{O}$ by recursion, we can define the class $\mathcal{C}$ of "partial approximations" which actually exist. If $\mathfrak{O}$ represents a failure of replacement, $\mathcal{C}$ will not be a set. Conversely, the approach above lets us show that $\mathcal{C}$ is a set without doing any recursion: we basically consider the map sending a "stage" in the recursion to the corresponding partial object if it exists and to $0$ (or some other fixed set) otherwise. So this represents a uniform way to eliminate the use of recursion. However, ultimately this is exactly the proof of the recursion theorem so in general situations this won't be satisfying to you. This reflects the fact that replacement is in fact equivalent to recursion, so in a precise sense you can never find a perfectly satisfying example.

• Sorry, this was not my intention, see my reply to your comment above. Commented Apr 14, 2018 at 16:13
• @UrYa'ar I've added an example you may find preferable. Commented Apr 14, 2018 at 16:16
• @UrYa'ar Does the new example feel more in line with what you're looking for? Commented Apr 14, 2018 at 20:48
• Thanks! I like this example, but I'm looking for something even simpler, that doesn't even require one to know what is a well order or an ordinal. An example that can be given almost immediately after phrasing the axioms. Since as you say recursion is inevitable, then the example I mentioned in the question or the ones Asaf seem simplest in that sense. Commented Apr 15, 2018 at 5:43
• Although I agree that once you have the notions of well order and ordinal your example is simpler. Commented Apr 15, 2018 at 5:45

I'd say that $V_\omega$ is the simplest. If you want something slightly less on the nose, $\mathcal P^\omega(\Bbb N)$.

Both can be easily described to students without fussing all that much about ordinals.

• I also thought about these before Noah's answer, and discarded them since they need recursion, but since recursion is essentially inevitable, I need to see which one can be most easily defined using a formula stating the existence of approximations. Commented Apr 14, 2018 at 17:55
• Both are equally simple. You can show them for one, and ask them to prove home for the other. Because $V_\omega$ is $\mathcal P^\omega(\varnothing)$. Commented Apr 14, 2018 at 17:57
• Yes indeed. Now I'm trying to formulate the proof for $\{\varnothing,\{\varnothing\},\{\{\varnothing\}\}...\}$ which is also essentially the same. And even "simpler" in some sense. Commented Apr 14, 2018 at 17:58
• Hmm. I'm not sure. I should be more or less all the same. Commented Apr 14, 2018 at 18:02
• Well yea the proof would be the same. The only sense it's "simpler" is that it uses weaker notions than power set. Commented Apr 14, 2018 at 20:01

Since by Noah Schweber's answer, the recursion theorem can't really be avoided, I give an explicit definition which I hope is simplest, in the sense that it doesn't require notions such as well-order or ordinal, and doesn't use the full recursion theorem, but essentially follows it's proof in a very specific case. So it can be given after one learns the axioms and what are functions. This also incorporates Asaf Karagila's answer.

Given some function $G:A\to A$ and $a\in A$ (e.g. $G(x)=\{x\}$ or $G(x)=\mathcal{P}(x)$) define $\varphi(x,y)$ to be the formula: $$x\in\mathbb{N}\land\exists f \Big[f\,\mathrm{is\,a\,function\,}\land Dom\left(f\right)=\left\{ n\in\mathbb{N}\mid n\leq x\right\} \land y=f\left(x\right)\land \\ \land f\left(0\right)=a\land\forall z\in\mathbb{N}\left(z<x\to f\left(z+1\right)=G( f\left(z\right)\ \right)\Big]$$ Then one has to prove that for every $n\in\mathbb{N}$ there is a unique such $f$, so that $F=\{<x,y>\mid \varphi(x,y)\}$ is a well-defined function satisfying $F(n)=G^n(a)$, so applying replacement gives the set $\{G^n(a)\mid n\in \mathbb{N}\}$, which may e.g. be $\{\varnothing,\{\varnothing\},\{\{\varnothing\}\}...\}$.