9
$\begingroup$

I have been working on this problem for several hours, and my understanding just isn't there. Here's what I've gathered:

Using downward Lowenheim-Skolem theorem, we know that any consistent set of sentences has a countable model, and for the sake of this problem we are assuming that ZF is indeed consistent.

The axiom of foundation in ZF seems to eliminate the possibility that there is a non-well-founded model, because it says that there is no infinitely descending membership sequence.

I believe I may need to employ compactness in the approach. Not sure what I need to proceed. TIA

$\endgroup$

4 Answers 4

11
$\begingroup$

Add constant symbols $c_0,c_1,c_2,\dots,c_n,\dots$ to the language of set theory. Let $\sf T$ be the theory obtained by adding sentences $c_1\in c_0,c_2\in c_1,\dots,c_{n+1}\in c_n,\dots$ to the $\sf{ZF}$ axioms. If $\sf{ZF}$ is consistent, then every finite subset of $\sf T$ is consistent, and so $\sf T$ is consistent by the compactness theorem. Any model of $\sf T$ is a non-well-founded model of $\sf{ZF}$.

The fact that the axiom of foundation holds in the model does not mean that there is no infinite descending $\in$-sequence of elements of the model, it just means that such an infinite sequence can not itself be an element of the model. The model "thinks" it is well-founded (so to speak), but viewed from outside it is not well-founded. Of course the $\in$ relation of the model is not real set-membership (at least if we assume that infinite descending $\in$-sequences do not exist in "the real world").

$\endgroup$
6
  • 1
    $\begingroup$ I just had a wonderful realization about ill founded models and infinite sequences. The model might know them but think they are finite. $\endgroup$
    – Asaf Karagila
    Feb 15, 2015 at 8:53
  • 1
    $\begingroup$ @AsafKaragila don't understand. If $a_0,a_1,a_2,\dots$ are elements of a model of ZF, and if $\dots a_2\in a_1\in a_0$, then surely the set $A=\{a_0,a_1,a_2,\dots\}$ can't be in the model, as it would witness the failure of the axiom of foundation. Am I wrong? What do you mean? $\endgroup$
    – bof
    Feb 15, 2015 at 9:28
  • 1
    $\begingroup$ If $M$ thinks that $x$ is an integer, then $M$ knows about a decreasing sequence indexed by $x$. Now simply take any non-standard integer, in a model where such things exist, and remember that that sequence is in fact infinite (externally speaking). $\endgroup$
    – Asaf Karagila
    Feb 15, 2015 at 9:32
  • 2
    $\begingroup$ @AsafKaragila Sure. But that's not what I would call a decreasing sequence, seeing as it has a last element. It has a genuine decreasing sequence hidden inside, but the model doesn't know about that. It's no surprise that the decreasing sequence is a subset of a set the model knows about. In the compactness construction we could add the sentences $c_n\in\omega$, so the decreasing sequence is in what the model thinks is $\omega$. $\endgroup$
    – bof
    Feb 15, 2015 at 9:51
  • 1
    $\begingroup$ It's food for thought all right. For a moment you had me worried that I'd made a misstatement in my answer. Of course I was just thinking of $\omega$-sequences. $\endgroup$
    – bof
    Feb 15, 2015 at 10:19
6
$\begingroup$

Of course that we need to assume that $\sf ZFC$ is consistent for these arguments, since if there are no models of $\sf ZFC$, then all the models are well-founded.

The usual answer is given by compactness, as bof writes in a very good answer. Here is a different argument, which relies on absoluteness and incompleteness (or well-foundedness, the last remark) instead.


The idea is that if $(M,\in)$ is a well-founded (and without loss of generality, transitive) model of $\sf ZFC$, then $V$ and $M$ agree on arithmetic statements, in particular they agree on what are the rules of first-order logic, the axioms $\sf ZFC$ have, and whether or not these axioms are consistent. Since $V$ is aware of $M$ being a model of $\sf ZFC$, it means that every well-founded model of $\sf ZFC$ must also agree that $\sf ZFC$ is consistent and has a model.

But by the incompleteness theorem we know that $\sf ZFC$ cannot possibly prove that it is consistent, so there must be a model $(N,E)$ which thinks that $\sf ZFC$ is inconsistent, and by the above it cannot be well-founded.

Caveats.

  1. When we talk about $\sf ZFC$ being consistent as an arithmetic statement, we mean that there is a recursively definable predicate on the natural numbers which encodes the axioms of $\sf ZFC$. So when I say that $V$ and $M$ agree on what is first-order logic and what are the axioms of $\sf ZFC$, I mean that they interpret that predicate in the same way.

    Of course, the model which thinks that $\sf ZFC$ is inconsistent will have non-standard integers, which means that he will think that $\sf ZFC$ is a larger theory and includes more axioms than it really has and the logic will have more inference rules and longer proofs, which is where the contradiction comes from.

  2. The absoluteness argument shows that in fact if $N$ is non-well founded but still agrees on what $\omega$ might be (this is called an $\omega$-model), then $N$ still agrees on what is $\sf ZFC$ and whether or not it is consistent.

    So the existence of $\omega$-models is itself stronger than just the existence of models of $\sf ZFC$. But it is weaker than the existence of transitive models, since those can be non-well founded.

  3. You can get the model $N$ using well-foundedness instead. Order the transitive models of $\sf ZFC$ by $\in$, since it's a non-empty class (otherwise all models are non-well founded; or there are no models at all) it has a minimal element, $M$. But now $M$ agrees that $\sf ZFC$ is consistent, so there is some $(N,E)\in M$ such that $M\models(N,E)\text{ is a model of }\sf ZFC$. Now we know the fact that the satisfaction relation is absolute between transitive models, $(N,E)$ is a model of $\sf ZFC$. But since $M$ was a minimal transitive model, $N$ cannot be transitive.

$\endgroup$
3
  • $\begingroup$ !Asaf: this question has come up before, I think, It is not clear to me whether the source of the coded inconsistency in a model of $\lnot \text{Con}(ZFC)$ is new instances of the axiom schemes in ZFC, or new instances of the inference rules. If we look at a finitely axiomatized theory like NBG, it would have to be the latter - so plausibly, it could also be that way in models of ZFC. $\endgroup$ Feb 22, 2015 at 15:57
  • $\begingroup$ Carl, you mean in the part about "agreeing about the axioms" should be also "agreeing about first-order logic", right? (You also can just omit the ! and @ completely, then the system doesn't delete the name.) $\endgroup$
    – Asaf Karagila
    Feb 22, 2015 at 16:00
  • $\begingroup$ It's a good point, I'll fix it when I'm at a proper keyboard. Thanks! $\endgroup$
    – Asaf Karagila
    Feb 22, 2015 at 16:17
3
$\begingroup$

This is really the compactness argument, but disguised as an ultrapower instead.

Let $U$ be any ultrafilter on $\omega$ extending the cofinite filter (a.k.a. the Fréchet filter), let $(M, \epsilon)$ be any model of ZFC, and let $(M^U, \epsilon^U)$ be the ultrapower of $(M, \epsilon)$ with respect to $U$. For each $n \in \omega$, let $n^M$ be the corresponding element of $M$. Define the following sequences $x_n : \omega \to M$: $$x_n (i) = \begin{cases} 0 & i < n \\ (i - n)^M & i \ge n \end{cases}$$ By construction, if $m < n$, then $[x_n] \mathrel{\epsilon^U} [x_m]$, because the set of $i$ such that $x_n (i) \mathrel{\epsilon} x_m (i)$ is cofinite. Thus, we have an infinite descending sequence $$\cdots \mathrel{\epsilon^U} [x_2] \mathrel{\epsilon^U} [x_1] \mathrel{\epsilon^U} [x_0]$$ and in particular $\epsilon^U$ is not well founded.

Of course, $(M^U, \epsilon^U)$ is also a model of ZFC, because it is elementarily equivalent to $(M, \epsilon)$. In particular, $(M^U, \epsilon^U)$ believes itself to be well founded, so that must imply there is no element $[y]$ of $M^U$ such that $[x] \mathrel{\epsilon^U} [y]$ if and only if $[x] = [x_n]$ for some $n \in \omega$. This highlights the subtle difference between sets inside the model and sets outside the model.

$\endgroup$
3
$\begingroup$

You can get this directly from the incompleteness theorem, without compactness. Let $M$ be a model of $\text{ZFC} + \lnot\text{Con}(\text{ZFC})$.

Then:

1) $\omega^M$ is a model of Peano arithmetic, because ZFC proves that $\omega$ satisfies each axioms of Peano arithmetic.

2) $\omega^M$ is not the standard model of Peano arithmetic, because $\omega^M$ satisfies $\lnot\text{Con}(\text{ZFC})$, and the standard model does not.

3) $\omega^M$ is not well founded, because no nonstandard model of Peano arithmetic is well founded. If $x$ is a nonstandard element, then in particular it is a successor, and it follows that there is an infinite decreasing sequence of predecessors beginning at $x$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .