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

Question

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.)

Answer 1

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.

Answer 2

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.

Answer 3

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\}\}...\}$.