Replacement and Sets of Natural Numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:48:18Z http://mathoverflow.net/feeds/question/42329 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42329/replacement-and-sets-of-natural-numbers Replacement and Sets of Natural Numbers arsmath 2010-10-15T21:19:34Z 2010-10-18T16:11:16Z <p>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.)</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/42329/replacement-and-sets-of-natural-numbers/42364#42364 Answer by Mike Shulman for Replacement and Sets of Natural Numbers Mike Shulman 2010-10-16T05:00:37Z 2010-10-16T06:37:47Z <p>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.</p> <p><em>(Edit: The following is corrected thanks to Andres' comments)</em></p> <p>For instance, I think the answer to Ricky's formulation in the comments is &alpha; = &omega;+1, but again probably not for the reason you expect. Namely, we can prove in ZFC that ZFC-Repl has a <em>countable</em> 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.</p> <p>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.</p> http://mathoverflow.net/questions/42329/replacement-and-sets-of-natural-numbers/42372#42372 Answer by Stefan Geschke for Replacement and Sets of Natural Numbers Stefan Geschke 2010-10-16T08:05:02Z 2010-10-16T08:05:02Z <p>The axiom (scheme) of replacement is in some sense only used to get large sets.<br> 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. </p> <p>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)\}$.)<br> The image of this map, the class of natural numbers, is a set by replacement.</p> <p>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.</p> http://mathoverflow.net/questions/42329/replacement-and-sets-of-natural-numbers/42663#42663 Answer by arsmath for Replacement and Sets of Natural Numbers arsmath 2010-10-18T16:10:45Z 2010-10-18T16:10:45Z <p>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 <a href="http://mathoverflow.net/questions/12370/first-order-definability-transitive-closure-operator/28931#28931" rel="nofollow">this</a> thread. You can't even construct $V_\omega$ without replacement. Section 4.2 of <a href="http://www.science.uva.nl/~seop/archives/sum2010/entries/settheory-alternative/#ZerSetThe" rel="nofollow">this survey</a> 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.</p>