Models of ZF satisfy per definition the Axiom of Regularity (also known as Axiom of Foundation): "Every non-empty set contains an element disjoint from it."
To the best of my knowledge, from this one can prove the following theorem: "There does not exist a sequence $(x_n)_{n \in \omega}$ such that $x_{n+1} \in x_n$ for all $n \in \omega$."
I am currently working through the book "Model Theory" by Chang and Keisler. Now I am stuck at exercise 2.1.7. which states: "Show that every model of ZF is elementary equivalent to a model $(A,E)$ which has an infinite sequence $…Ex_2Ex_1Ex_0$."
Now I am confused because I think this is a contradiction: On the one hand $(A,E)$ is elementary equivalent to the original model, in particular we should have $(A,E) \models$ ZF. But on the other hand it does not satisfy the theorem I stated above. Where is my mistake? How can one solve this exercise?
Thank you very much in advance!
Edit: I managed to solve the exercise in the following way: Let $(M,\varepsilon)$ be a model of ZF. Consider the language $\mathcal{L} = \{\in\}$ of set theory and the new language $\mathcal{L}' = \mathcal{L} \cup \{c_i\mid i \in \omega\}$, where the $c_i$ ($i \in \omega$) are distinct constant symbols. We look at a theory of $\mathcal{L}'$:
$\Sigma = $ ZF $ \cup$ $\{\sigma_n \mid n \in \omega\}$, where $\sigma_n$ is the sentence $c_{n+1} \in c_n$ for $n \in \omega$.
If we can show that $\Sigma$ has a model, we are done. By the compactness theorem it suffices to prove this for every finite subtheory $\Sigma'$ of $\Sigma$. But in $\Sigma'$ only finitely many $\sigma_n$ and therefore only finitely many constant symbols $c_0,…,c_m$ appear. If we now set the natural number $i$ as the interpretation of $c_i$ in $(M,\varepsilon)$ for every $i \in \{0,…,m\}$, we have a model $(M,\varepsilon,0,1,…,m)$ of $\Sigma'$.
But still I am confused about how this is compatible with the above theorem.
Best Answer
First I think the solution you provided is correct and this is usually the way such exercises are proven.
Then about your confusion it is a phenomenon that often appears when working in model theory. In short, the solution is that $\omega$ is not the same in the model $M$ of $ZF$ than in the model $M'$ of $\Sigma$ whose existence you just proved. Thus, even if there is an "infinite sequence of inclusions" indexed by $\omega$, the index set $\omega$ is the one from $M$ and not from $M'$.
Edit: It has been mentioned in the comments that another phenomenon can also happen: I said above that the set denoted by $\omega$ can change; it can also be the case that the set $\omega$ remains the same but you don't have enough functions in your model, and in that case you would not be able to define in $M'$ the mapping $n\mapsto c_n$.
It is maybe easier to see why the apparent contradiction is not a real contradiction by looking at (a model for) non-standard integers. If you choose a non-standard number $N$ in this model, this number has a predecessor $N-1$, and it is easy to verify that $N-1$ is itself non-standard. You can then continue the same process "indefinitely" and you will always get a new non-standard integer, which in particular is not $0$. If you take for $\omega$ the set from your standard model then you will indeed be able to construct a decreasing sequence indexed by this $\omega$, but if you take the correct $\omega$ (i.e. the one from your non-standard model) you won't be able to define your sequence past the index $N$.