# Replacement and Sets of Natural Numbers

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?

-
I think you should be more clear on what you mean by "construct", so that you don't allow [x is empty and Borel determinacy holds]. –  Ricky Demer Oct 15 '10 at 22:37
This seems like a nice question, but it’s a very tricky one to formulate precisely! When you ask if replacement is required to construct a certain set, you can't (at least, not naïvely) mean “an actual set in a particular model”, since either that model believes replacement or it doesn't. On the other hand, if we instead mean “some formula defining a set”, we run into the issue Ricky points out. –  Peter LeFanu Lumsdaine Oct 15 '10 at 23:24
Here's what I think is a very good formalization of arsmath's questions. What is the least ordinal alpha such that there exists a set M such that M is a transitive model of ZFC-replacement and V_alpha is not a subset of M? What about L_alpha instead? –  Ricky Demer Oct 16 '10 at 0:58
Thanks. I know these kinds of questions turn on the precise formulation, but I have trouble formulating them clearly. What I'm after is just a sense of the additional expressive power of set theory with replacement versus without. Ricky's formulation probably captures what I have in mind. –  arsmath Oct 16 '10 at 1:54
Perhaps I'm misunderstanding the convention used in this, but why is the union iterated over the value of $i$ ranging from $0$ to $\inf$, while the terms for the union to be performed on contain only $P$, $n$, and $N$ combined as $P^n N$? Shouldn't $i$ be involved in the term somehow? –  sleepless in beantown Oct 16 '10 at 11:09

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.

-
Where could I find the version of Lowenheim-Skolem that gives if ZFC-replacement is consistent then there is a countable transitive model of ZFC-replacement? –  Ricky Demer Oct 16 '10 at 5:11
"If ZFC-replacement is consistent then there is a countable transitive model of ZFC-replacement". This is false: Any transitive model (in fact, any $\omega$-model) is correct about arithmetic statements, so the second incompleteness theorem prevents this from happening. –  Andres Caicedo Oct 16 '10 at 5:22
Andres, how do you get that from the second incompleteness theorem? –  Ricky Demer Oct 16 '10 at 5:37
@Ricky, ordinary Lowenheim-Skolem gives you a countable model, and since ZFC-replacement includes the axiom of foundation, Mostowski collapse implies that any model is isomorphic to a transitive one. –  Mike Shulman Oct 16 '10 at 6:05
Ricky: If $T$ is consistent, $Con(T)$ is a true arithmetic statement and therefore holds in any $\omega$-model $M$ of any decent theory. If $M$ also happens to be a model of $T$, then $M$ is a model of $T+Con(T)$, and therefore $Con(T+Con(T))$ is true. But then the existence of $M$ is not provable in $T+Con(T)$ if $T$ is strong enough, or else, letting $S=T+Con(T)$, we have that $S$ proves $Con(S)$, against Gödel's 2nd incompleteness. "Strong enough" may be taken to mean that $T$ proves the completeness theorem and interprets PA. Both of these requirements hold for ZFC-replacement. –  Andres Caicedo Oct 16 '10 at 6:09

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.

-
In a certain sense you are of course right, but this is what I have in mind. Suppose you have a predicate with one free variable P(x), but with bound variables that quantify over large sets. You could use that predicate to define a subset of the integers by using separation, but in some sense you used replacement "behind the scenes". It seems to me that you could use that to prove the existence of sets that you couldn't ordinarily talk about. I know that's terribly fuzzy... –  arsmath Oct 16 '10 at 16:53

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.

-