Classes that cannot be shown to be proper without replacement

Question

The class $Grp$ of groups (where a group is defined to be a pair $(G,\circ)$, which is encoded as $\{\{G\}, \{G,\circ\}\}$) can't be a set: if it would be a set, then $\bigcup \bigcup Grp$ would be a set. But $\bigcup\bigcup Grp$ already contains all sets, since each set occurs as an element of the carrier set of some group: if $A$ is a set, consider the group $(\{A\}, \circ)$ with $A\circ A=A$.

So using the axiom of union we reduced the question whether $Grp$ is a proper classes to the fact that the class $V$ of all sets is not a proper class (which follows from comprehension and Russell's trick).

I can imagine another proof strategy with which one can prove that a class $C$ is proper, using the axiom of replacement:

1. Construct a surjection $C\to V$.
2. Use replacement to conclude that $V$ is a set.
3. Again, since $V$ is proper, conclude that $C$ is proper.

Question: What would be an example of a class $C$ (occuring in practice) that cannot be shown to a proper class without replacement? (But which can be shown to be a proper class using replacement, e.g. with the above proof idea.)

If you want a precise question, then consider the formal systems NBG or MK.

Answer 1

I have a stupid answer for you. Consider the proposition $P :\equiv$ "ZFC without Replacement is consistent", encoded into ZFC. Note that ZFC proves $P$, while ZFC without replacement does not prove $P$ (at least assuming ZFC without replacement is consistent).

Then consider the class $\{x | P\}$. Then ZFC shows this class is proper, but ZFC without replacement does not.

A less stupid example follows. We work in ZF without replacement.

Consider the sets $T_n$ for $n \in \mathbb{N}$, defined recursively by

$$T_0 = \mathbb{N}$$ $$T_{n + 1} = P(T_n)$$

Then consider the class $T = \bigcup\limits_{n \in \mathbb{N}} T_n$

We see that $(T, \in_T)$ is a model of ZF without replacement, where $\in_T = \{(x, y) \in T^2 | x \in y\}$.

Clearly, $\mathbb{N} \in T_1 \subseteq T$. So the axiom of infinity is satisfied.

And $\emptyset = 0 \in \mathbb{N} = T_0 \subseteq T$. So the axiom of the empty set is also satisfied.

Now note that since $T_0$ is transitive and the powerset of any transitive set is transitive, we see that $T_n$ is transitive for all $n$. Therefore, the sequence $\{T_n\}_{n \in \mathbb{N}}$ is increasing in that $T_n \subseteq T_{n + 1}$ for all $n$.

Thus, we see that $T$ itself is transitive, since if $y \in x \in T_i$ then $y \in T_i$. Because $T$ is transitive, it satisfies the axiom of extensionality. We also see that if $y \subseteq x \in T_i$, then $y \subseteq x \subseteq T_i$ and hence $y \in T_{i + 1}$. Thus, any subset of an element of $T$ is also an element of $T$. This implies that $T$ satisfies the axiom scheme of separation.

If $x \in T_n$, $y \in T_m$, then $x, y \in T_{\max(n, m)}$. Then $\{x, y\} \subseteq T_{\max(n, m)}$, so $\{x, y\} \in T_{\max(n, m) + 1}$. Thus, $T$ satisfies pairing.

If $x \in T_i$ then $\cup x \subseteq T_i$ since $T_i$ is transitive, so $\cup x \in T_{i + 1}$. Therefore, $T$ satisfies union.

If $x \in T_i$ and $y \subseteq x$, then $y \in T_{i + 1}$. So $P(x) \subseteq T_{i + 1}$, and hence $P(x) \in T_{i + 2}$. So $T$ satisfies powerset.

Since $\in$ is well-founded, any restriction of $\in$ is also well-founded. So $T$ satisfies the axiom of foundation.

Finally, if choice is true, then $T$ models choice. For given any collection $F \in T$ of non-empty sets, we can take a choice function $f : F \to \cup F$ such that $\forall x \in F (f(x) \in x)$. Then $f \in P(F \times \cup F) \in T$, so $f \in T$.

Now note that $T$ also models $V = T$. Precisely, $V = T$ can be stated as: for all $x$, there exists some $n \in \mathbb{N}$ and there is a function $f$ with domain $\{m \in \mathbb{N} | m \leq n\}$ such that $f(0) = \mathbb{N}$ and for all $i < n$, $f(i + 1) = P(f(i))$ and such that $x \in f(n)$. Relativizing all quantifiers to $T$, we see that the statement holds in $T$.

Thus, we see that ZF(C) without replacement is relatively consistent with ZF(C) without replacement plus $V = T$.

Now if we assume $V = T$, then clearly $T^c = \emptyset$ is not a proper class. So it is relatively consistent with ZFC minus replacement that $T^c$ is a set.

But clearly, in ZF, we see that $T$ is a set. We can construct it explicitly by replacement. Therefore, $T^c$ must be a proper class.

Note that all kinds of interesting things fail in ZF minus replacement plus $V = T$. For example, all ordinals are countable. In fact, assuming $V = T$, we have $Ord = \mathbb{N} \cup \{\omega + n \mid n \in \mathbb{N}\}$. Even constructing the ordinal $\omega + \omega$ proves to be impossible. This is because for all $n$, $\omega + n \subseteq T_n$ but $\omega + n \notin T_n$. This provides another example: the class of uncountable ordinals is empty under $V = T$, but is a proper class under replacement.

Of course, there are well-orderings which are uncountable. For example, one can take $W$ to be the set of all well-orderings on subsets of $\mathbb{N}$, quotiented by order isomorphism. Then $W$ itself is a well-order, and it cannot be a countable one. Thus, not all well-orderings are isomorphic to an ordinal.