16
$\begingroup$

Godel proved the consistency of the axiom of choice with the axioms of $\sf ZF$ by showing that given any model of $\sf ZF$, there is a definable class which satisfies $\sf ZFC$.

The proof uses a lot of the power of $\sf ZF$, in particular it uses transfinite recursion which is equivalent to the axiom schema of replacement. And also the fact that we can talk about the ordinals as objects in the universe by looking at the von Neumann ordinals.

Let $\sf Z$ denote Zermelo set theory, which is obtained by removing replacement and foundation from $\sf ZF$ and adding the separation schema instead. This is a strictly weaker theory than $\sf ZF$. We know that if $\delta>\omega$ is a limit ordinal, then $V_\delta\models\sf Z$ (and in fact more, since it also satisfies foundation).

One interesting difference is that while $\sf Z+AC$ is sufficient to prove that every set can be well-ordered, it cannot prove that every set is equipotent with a von Neumann ordinal. Since, for example in $V_{\omega+\omega}$ there are only countably many von Neumann ordinals, all of which are countable, but there are uncountable sets (and one can arrange that there are uncountably many different cardinals amongst them).

Is there an inner model construction, internal to $\sf Z$, which acts like $L$ in proving the consistency of $\sf Z$ with additional axioms? If not, how about an external construction? Will the answer change if we add back the axiom of foundation?

Improve this question
$\endgroup$
4
  • $\begingroup$ I wasn't quite sure how to tag this; some inner model tag might be related, but I'm not 100% sure about that. $\endgroup$
    – Asaf Karagila ♦
    Oct 25, 2014 at 4:14
  • 1
    $\begingroup$ An addendum to Ali's answer: Mathias doesn't need von Neumann ordinals, because you can use well-orderings instead. I don't think you even need to worry about getting isomorphism classes of well-orderings (which won't be sets, and without Foundation you don't have Scott's trick to reduce them to sets). Define an $L$-like hierarchy along each well-ordering, and call a set constructible if it appears in some such hierarchy. $\endgroup$
    – Andreas Blass
    Oct 25, 2014 at 15:06
  • 1
    $\begingroup$ As a matter of notation, I think Z is often used to mean ZF minus replacement, so it would include foundation (even though that wasn't in Zermelo's original axiomatization). $\endgroup$
    – Andreas Blass
    Oct 25, 2014 at 15:08
  • $\begingroup$ @Andreas: I think that most of my encounters with the notation $\sf Z$ was without foundation; although it seems commonplace that foundation is included. And the lack of this axiom, and consequently Scott's trick for ordinals, is exactly what had me questioning; but your solution is a neat circumvention of that. $\endgroup$
    – Asaf Karagila ♦
    Oct 25, 2014 at 15:21

1 Answer 1

Reset to default
21
$\begingroup$

This answer is based on Adrian Mathias' majestic paper The Strength of MacLane Set Theory (published in the Annals of Pure and Applied Logic, 2001).

Let $\sf{M}$ be the system of set theory whose axioms consist of Extensionality, Null Set, Pairing, Union, Set Difference ($x\setminus y$ exists), Power set, $\Delta_0$-Seperation, Foundation, Transitive Containment (every set is a subset of a transitive set), and Infinity.

It has long been known that Zermelo set theory plus Foundation does not prove Transitive Containment (as shown by Schröder and Jensen, and Boffa).

According to Mathias (see the paragraph before Theorem 1 in the introduction), Gödel's original construction of L can be implemented within $\sf{M}$ to yield the following theorem that can be proved within Primitive Recursive Arithmetic. But the proof, according to Mathias, is quite cumbersome. To my knowledge the full proof of this theorem has not appeared in print.

Theorem. If $\sf{M}$ is consistent, then so is $\sf{M}$ + KP (Kripke-Platek set theory) + $\Sigma_1$-Seperation + $V=L$.

In his paper, Mathias provides the proof of a slightly weaker result, where the hypothesis of the consistency of $\sf{M}$ is strengthened to the consistency of $\sf{M}$ augmented with the axiom H (introduced in section 2 of his paper).

Let me also remark that the usual construction of L that one sees in set theory texts, on the other hand, can be smoothly carried out in KP + Infinity.

Addendum. See also Avshalom's comment below, which includes an outline (provided by Mathias) of how certain results in Mathias' paper can be used to demonstrate Con(Z) => Con(Z + AC),

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Wonderful. Thanks. I think that "majestic" is a good fit for describing this paper. $\endgroup$
    – Asaf Karagila ♦
    Oct 25, 2014 at 15:26
  • 6
    $\begingroup$ Mathias' own commentary on his paper is available on his website: dpmms.cam.ac.uk/~ardm/whatsnew.pdf. He also observed (in correspondence) that in 2012 Philip Welch asked him if one can prove Con(Z) => Con(Z + C). He duly confirmed by noting that: "If C means choice, then yes, but it is rather laborious. Step one is as you say, use thm 2.46 of "The strength of MacLane" to move to a strengthening of Z in which you can define L. Then to pull Sigma_k separation inside L you need a fine structural lemma: the hard work is Proposition 5.29, then you can get Theorems 5.27 and 5.33." $\endgroup$
    – Avshalom
    Oct 26, 2014 at 11:21
  • 1
    $\begingroup$ @Avshalom: thanks for the pointer to Mathias' commentary, and for sharing Mathias' enlightening answer to Welch's query. I have updated my answer in light of your comment. $\endgroup$
    – Ali Enayat
    Oct 27, 2014 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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