Today, in my class of set theory, my professor said that replacement axiom doesn't true in the structure $(\omega, \in)$. However, I think that he was wrong and here is my proof.

First the axiom form that I use is the following: Let $\phi(x,y,A,w_1,\dots,w_n)$ be a formula in the language of set theory where $x,y,A,w_1,\dots,w_n$ are parameters. So, replacement axiom says: $$ \forall A,w_1,\dots,w_n(\forall x\in A\exists! y\phi\rightarrow\exists Y\forall x\in A\exists y\in Y\phi). $$

Now, let $\phi$ a formula as above and take $A,w_1,\dots,w_n\in \omega$. Also, suppose that $\forall x\in A\exists!\phi$. As $A$ is a natural number, $A=\{0,1,\dots,A-1\}$. Now, define $y_k\in\omega$ as the unique element such that $\phi(k,y_k,w_1,\dots,w_n)$ where $k\in A$.

If we take $Y=\max\{y_1,\dots,y_{A-1}\}+1$, then $\forall x\in A\exists y\in Y\phi$. So, the axiom holds.

Is there some mistake in my argument?

  • $\begingroup$ An important lesson that axioms that are equivalent under “the rest of ZF” often aren’t equivalent under weaker systems. (I’m guessing you are looking at Kunen who uses weaker forms of most of the axioms... a surprising number are true in the ordinals, but crucially, separation is not.) $\endgroup$ – spaceisdarkgreen Feb 9 at 1:00
  • $\begingroup$ @spaceisdarkgreen yes, I'm using Kunen's book "set theory". But this awake in me a question. Which are the usual axiom in the practice? $\endgroup$ – Gödel Feb 9 at 1:05
  • 2
    $\begingroup$ (Actually Kunen has a problem on this, Chapter 4 problem 1, assuming you're using his older book.) For instance, his axiom of pairing will say for any $x$ and $y,$ there is a $z$ such that $\{x,y\}\subseteq z.$ Rather than the usual phrasing that for any $x,y,$ the set $\{x,y\}$ exists. This pattern is true for most of his axioms, including replacement. See the wikipedia page on replacement for the "usual" version, along with some words on the relationship between replacement and collection. $\endgroup$ – spaceisdarkgreen Feb 9 at 1:07
  • $\begingroup$ Come to think of it, with the Kunen definition of replacement, replacement holds in this model. It's comprehension that fails. I'll edit my answer to note this. $\endgroup$ – Robert Shore Feb 9 at 4:08

The professor is correct. Let $t=\{0, 1, 2\} (= 3 \in \omega)$ and let $\phi(x, y)\text{ be } y=x \cup \{x\}.$ Then $\{1, 2, 3\} \notin \omega$ (although $\{1, 2, 3\} \subset \omega$), so replacing each element of $3$ with its image under $\phi$ results in something that is not a member of your universe.

As @spaceisdarkgreen points out, this argument assumes the usual definition of Replacement. In Kunen's weaker definition, though, the axiom scheme merely states that there is a set containing (rather than consisting of exactly) the "replacement" elements. With this definition, Replacement holds (though Comprehension fails) in $(\omega, \in)$.

To see this, note that every member of $\omega$ is finite, so the "replacement" elements will also constitute a finite subset of $\omega$, which therefore has a largest element $N$. Then $N+1$ is a "witness" demonstrating this instance of Replacement.


The axiom that you called "replacement" in the question is true in $(\omega\in)$, but its usual name is "collection", not "replacement". The axiom usually called "replacement" is false in $(\omega,\in)$, as shown in Robert Shore's answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.