Replacement and Sets of Natural Numbers - MathOverflow

Replacement and Sets of Natural Numbers

2010-10-15T21:19:34Z

It's clear that the axiom of replacement can be used to construct very large sets, such as $$ \bigcup_{i=0}^\infty P^i N, $$ where $N$ is the natural numbers. I assume that it can be used to construct sets much lower in the Zermelo hierarchy, such as sets of natural numbers, but I don't know of an example. Is there an easy example? (Just to be clear, I mean an example that requires the use of replacement, not just one where you could use replacement if you wanted to.)

I would guess you can cook up an example using Borel determinacy, since that involves games of length $\omega$, but it would be great if there was an even more direct example.

Also, I'd be curious to know for any such examples at what stage they first come along in the constructible universe. $\omega + 1$? The first Church-Kleene ordinal? Some other ordinal I've never heard of?

Answer by Mike Shulman for Replacement and Sets of Natural Numbers

2010-10-16T05:00:37Z

This probably isn't what you are looking for, but one can write down an explicit Diophantine equation for which ZFC proves that it has a solution, but ZFC minus replacement does not (assuming it is consistent). Namely, use Godel encoding and the solution of Hilbert's 10th problem to write down a Diophantine equation whose only solutions encode proofs of the consistency of "ZFC minus replacement." One wants a "naturally occurring" example instead, but it's hard to say what that means.

(Edit: The following is corrected thanks to Andres' comments)

For instance, I think the answer to Ricky's formulation in the comments is α = ω+1, but again probably not for the reason you expect. Namely, we can prove in ZFC that ZFC-Repl has a countable transitive model. To do this we start from an arbitrary transitive model (such as $V_{\omega+\omega}$) and apply the downward Lowenheim-Skolem theorem to find a countable submodel. This countable submodel may no longer be transitive, but it is still well-founded, so by Mostowski's collapsing lemma it is isomorphic to an (also countable) transitive model.

Since ZFC-Repl has a countable transitive model, $V_{\omega+1}$ (being uncountable) cannot be a subset of all such transitive models. But $V_\omega$ is the set of hereditarily finite sets, which I think have to be in any transitive model since each of them can be uniquely characterized by a formula.

Answer by Stefan Geschke for Replacement and Sets of Natural Numbers

2010-10-16T08:05:02Z

The axiom (scheme) of replacement is in some sense only used to get large sets.
Namely, if you already have a set $X$, then every subclass of $X$ is a set by separation. Replacement guarantees that certain large objects are sets.

Now, in the case of natural numbers one sometimes states the axiom of infinite by saying that there is a set $y$ which is closed under the operation $x\mapsto x\cup\{x\}$. We can assume that there is a single element $a$ of $y$ such that $y$ is the minimal set which contains $a$ and is closed under $x\mapsto x\cup\{x\}$. Now we can define a map $f$ from $y$ to the ordinals by recursion in the natural way. (Mapping $a$ to $0$ and $x\cup\{x\}$ to $f(x)\cup\{f(x)\}$.)
The image of this map, the class of natural numbers, is a set by replacement.

But now, by the previous remark, every subclass of $\mathbb N$ is a set by replacement. Of course, we could also phrase the axiom of infinite in a more direct way.

Answer by arsmath for Replacement and Sets of Natural Numbers

2010-10-18T16:10:45Z

Poking around, I came across an incredibly easy example of a small set that require replacement: the transitive closure of a set. It's mentioned in this thread. You can't even construct $V_\omega$ without replacement. Section 4.2 of this survey suggests that you can recover all of these usages of replacement by adding the assertion that every set belongs to a $V_\alpha$ which is itself a set.