[FOM] Re: AC and strongly inaccessible cardinals

Robert M. Solovay solovay at Math.Berkeley.EDU
Sat Mar 29 02:57:57 EDT 2008


This letter is in response to two letters ([Trybulec1] and
[Trybulec2]) of Professor Trybulec to the Mizar mailing list. These
letters discuss two papers ([Tarski1] and [Tarski2]) of Alfred
Tarski. (Precise cites to the two Trybulec letters and to the papers
of Tarski appear in the references at the end of this letter.) Since
the discussion of the points raised in these letters originated on the
FOM mailing list, and the topics seem of interest to that list, I am
also ccing my letter to the FOM mailing list.

Let me begin by summarizing the points of Professor Trybulec's letter
with which I disagree:

1) ZF + "there are arbitrarily large universes" implies the Axiom of
    Choice.

2) ZF + "there are arbitrarily large inaccessible cardinals" implies
    the axiom of choice.

    Actually the situation with 2) is somewhat delicate. With the
    "correct" definition of "strongly inaccessible cardinal" this claim
    is definitely wrong. However, with the definition of strongly
    inaccessible cardinal" used in Mizar, it is true that the existence
    of a proper class of strongly inaccessible casrdinals entails the
    axiom of choice. The proof, however, does not go via Tarski's
    work. It makes essential use of the Axiom of Foundation which plays
    no essential role in Tarski's work.

    3) The proofs of Urban (in the Mizar article CARD_LAR (cf. THEOREM
       37) are relevant to this topic.

    Unfortunately for the topic under discussion, the whole treatment
    of cardinals in Mizar relies on the axiom of choice. In particular,
    the proof of the cited theorem makes essential use of the axiom of
    choice.

    (Professor Trybulec's suggestion that this theorem might be
    relevant was put forth tentatively. I just want to record that it
    is definitely *not* relevant.)

    DEFINITIONS

    First, work in ZFC, Then we can identify cardinals with initial
    ordinals. (An initial ordinal is an ordinal which is not equipotent
    with any smaller ordinal.)

    A cardinal kappa is **strongly inaccessible** if:
    1) It is uncountable;
    2) It is regular;
    3) For every cardinal lambda < kappa, the power set of lambda has
    cardinal less than kappa.

    I remark that this definittion (which is standard) is not the one
    used in the Mizar Mathematical Library (MML). They replace 1) by
   1') It is infinite.

    Now two definitions which are provably equivalent in ZFC might not
    be provably equivalent in the weaker theory ZF. The paper [Blass]
    shows that this indeed happens with the notion of "inaccessible
    cardinal". The paper [Blass] considers four different variants of
    the notion (and proves by constructing suitable models that they
    all difer. Two of them are relevant for our present purposes.

    Work in ZF:

    A cardinal (initial ordinal) kappa is **i-inaccessible** if:
    1) It is uncountable;
    2) It is regular;
    3) If lambda is an initial ordinal less than kappa, then the power
    set of lambda is well-orderable, and equipotent with some ordinal
    less than kappa.


    Notice that clause 3) of this definition has a lot of choice
    smuggled in. For example, it is immediately clear (in ZF) that if
    there is an i-strongly inaccessible cardinal, then the reals are
    well-ordered. (Take lambda = aleph_0.)

    The second notion is that of **v-inaccessible cardinal**. Following
    [Blass] we give two variantions of the definition. (We refer to
    [Blass] for the proof that they are equivalent.)

    The two variations start the same way. To be v-inaccessible, kappa
    must be an initial ordinal.

    In the first variation of the definition, kappa is v-strongly
    inaccessible iff V_kappa (the collection of sets of rank less than
    kappa) is a model of "second-order ZF). (Basically, in the two
    schemes of ZF ("replacement" and "selection") there is one instance
    of the scheme for every subset of V_kappa.)

    Here is the second definition of v-inaccessible:

    An initial ordinal, kappa,  is v-inaccessible if it is:

    1) Uncountable;

    2) Regular;

    3) Whenever alpha is less than kappa, there is no function which
       maps V_alpha (the set of sets of rank less than alpha) onto kappa.

    Next we recall the definition of a Grothendieck universe. Good
    references for this concept are [G1] and [G2].

    A Grothendieck universe is a set U such that:
    1) U is transitive;
    2) If x, y are in U, so is {x,y};
    3) If x is in U, the power set of x, P(x), is in U;
    4) If x is in U, union(x) is in U;
    5) If A is a subset of U, I is a member of U, and there is a
    surjective map of I onto A, then A is in U.

    The terminology of a "Tarski class" comes from Mizar (Cf. CLASSES1:
    def 2). The concept is implicit in Tarski's Axiom A which we will
    discuss in a moment.

    U is a Tarski class iff:
    1) If A is in U and B is a subset of A, then B is in U;
    2) If A is in U, then P(A) is in U;
    3) If A is a subset of U, and A is not equipotent with U,  then A
    is in U.

    Tarsi proves in [Tarski2] that every Tarski class is
    well-orderable. The proof can be carried out in Zermelo set theory
    without use of the axioms of foundation or choice.

    There are trivial examples of the notion of "Grothendieck universe"
    and "Tarski class". For example, the empty set is an example of
    both of these concepts. So is the collection V_omega of all
    hereditarily finite sets. We say that a Grothendieck universe or
    Tarski class is non-trivial if it has an infinite member.

    There are close connections between the various concepts we have
    introduced. (The following assertions are all provable in ZF.) If
    kappa is a v-inaccessible cardinal, then V_kappa is a non-trivial
    Grothendieck universe. Conversely, if U is a non-trivial
    Grothendieck universe, then the set of ordinals in U is a
    v-inaccessible cardinal. Every i-inaccesible cardinal is
    v-inaccessible. But the converse does not hold (as is shown in
    [Blass] Theorem 17.) If U is a non-trivial Tarski class, then the
    set of ordinals in U is i-inaccessible. Let I be the proposition
    that there is a strongly inaccessible cardinal. We will sketch
    presently the proof that if ZFC + I is consistent, then there is a
    model of ZF in which there is an i-inaccessible, kappa, such that
    V_kappa is not a Tarski class.

    Neither of the notions of non-trivial Grothendieck universe or
    non-trivial Tarski class implies the other. It is easy to construct
    examples of Tarski classes (whose set of ordinals is strongly
    inaccessible) that are not transitive. (The construction needs a
    strongly inaccessible cardinal as input, of course.) And our
    Example I (below) will give a non-trivial Grothendieck universe
    which is not well-orderable and hence not a Tarski class.

    TARSKI-GROTHENDIECK SET THEORY

    Here are three axiomitizations of the same theory (= set of
    theorems):

    1) ZFC + "For every ordinal lambda, there is a strongly inaccessible
       cardinal kappa with kappa > lambda."

    2) ZFC + "Every set x is a member of a Grothendieck universe U".

    3) ZFC + "Every set xis a member of some Tarski class".

    Tarski's axiom A is the assertion that every set x is a member os
    some Tarski class. (The term "Tarski class" is not used by Tarski.)
    Tarski remarks that in the presence of axiom A many of the axioms
    of ZFC become redundent. Indeed, we can get the same theory with
    the following axioms:

    Extensionality, Foundation, Null Set, Pair Set, Replacement, Union,
    and Axiom A.

    AXIOM A AND THE AXIOM of CHOICE

    What Tarski proves (cf. Corollary 7 of [Tarski2]) is the
    following. (The proof can easily be formalized in Zermelo set
    theory without use of the axioms of choice or foundation.)

    Let X be a set. Let S be { Y | Y is a subset of X of cardinality
    less than X}, Then if S is equipotent with X, then X is
    well-orderable.

    For the application to Axiom A, we can get by with the following
    weaker result:

    Let X be a set. Suppose that every subset Y of X is either a member
    of X or equipotent with X. Then X is well-orderable.

    As Trybulec remarks, this weaker result has a somewhat easier
    proof. I first sketch the proof in ZF and then remark how the proof
    can be compressed into Zermelo set theory without the axiom of
    Foundation.

    Let X be as above. Let W be the set of all z such that:

    1) z is an ordinal;

    2) z is a subset of X;

    3) z is not equipotent with X.

    Clearly, W is an initial segment of the ordinals and hence an
    ordinal. By our hypothesis on X, W is a subset of X. If W is not
    equipotent with X, then W is a member of W (which contradicts
    Foundation).

    So W *is* equipotent with X and hence X is well-orderable.

    To carry out this proof without the use of the axioms of
    Replacement and Foundation (though with the axiom of Separation) we
    proceed as follows. We define an ordinal as a transitive set which
    is well-ordered by epsilon. Since we don't have the axiom of
    replacement, we can't prove that every well-ordered set is
    isomorphic to an ordinal. But our argument never used that. To
    deduce a contradiction from "W is a member of W" we proceed as
    follows: Since epsilon well-orders W, for every member x of W we
     have not (x epsilon x). So if W in W, this remark applies to W and
    W is not a member of W. Contradiction!


    FIRST EXAMPLE:

    We give a model of ZF + "Every set is a member of  Grothendieck
    universe" + "The reals are not well-orderable". Our example is a
    slight variant of the model used in [Blass] to prove their Theorem
    17.

    Start with a transitive countable model M of ZFC + V = L + "There
    are arbitrarily large inaccessible cardinals". Force to adjoin a
    single generic subset of omega , x, to M, getting M[x].

    It is well-known that we can find a model N such that M \subset N
    \subset M[x] and the reals of N are not well-orderd. (One way to do
    this is as follows. For i in omega, let x_i be the set of j such
    that 2^i3^j is in x. Let b = {x_i: i in omega}. Then take N to be
    the smallest transitive model of ZF which contains b and all the
    ordinals of M.

    It is easy to verify that if kappa is inaccessible in M, then
    V_kappa (as computed in N) is a Grothendieck universe. The details
    can be found in [Blass] in the proof of their Theorem 17.

    Note that in this model, if kappa is v-inaccessible in M, then it is
    so in M[x] as well and hence also in N.

    ARBITRAILY LARGE i-INACCESSIBLES

    We next wish to explain why ZF + "There are arbitraily large
    i-inaccessibles" proves the axiom of choice.

    The key result is the following which is established during the
    proof of Theorem 11 of [Blass]:

    Let kappa be i-inaccessible. Let alpha be an ordinal less than
    kappa. Then V_alpha is well-orderable.

    From this it follows immediately that if there are arbitraily large
    i-inaccessibles then every V_alpha is well-orderable. Hence (using
    the Axiom of Foundation) every set is well-orderable and AC
    follows.

    WHY v-INACCESSIBLE IS THE RIGHT FORMULATION OF "STRONGLY
    INACCESSIBLE" IN tHE ABSENCE OF ChOICE

    1) The concept of i-inaccessilbe has a lot of choice built
       in. Cf. That if kappa is i-inaccessible, then for every alpha
       less than kappa, V_alpha is well-orderable.

    2) In the absence of choice, the connection between universes and
       inaccessibles is preserved if we use v-inaccessibles but not if
       we use i-inaccessibles.

    3) If M is a transitive class model of ZFC and N is a transitive
       inner model of ZF with N \subset M, then if kappa is
       inaccessible in M, kappa is v-inaccessilbe in N (but as Example
       1 shows) need not be i-inaccessible.

    EXAMPLE 2

    This is a model of all the axioms of ZF (except the axiom of
    Foundation) in which the axiom of choice fails but there are
    arbitraily large i-inaccessilbe cardinals.

    Basically the model is a variant of the simplest Fraenkel-Mostowski
    model where one adjoins a set of individials which is an amorphous
    set without a well-ordering. In order to have extensionality our
    individuals will be sets x such that x = {x}. (Of course,
    foundation must fail.)

The starting model M from which we do this variant of the FM
construction will be a model of ZFC + V = L + "There are arbitraily
large inaccessible cardinals". The  well-founded sets of the resulting
FM model are just our starting model M. In particular, the
inaccessible cardinals in our original model remain i-inaccessible in
our final model.

This example is important since it shows that the reason that a proper
class of i-inaccessibles yields choice has nothing to do with Tarski's
results. For, as noted previously, Tarski's proofs make no essential
use of the Axiom of Foundation.

     EXAMPLE 3

     The following theorem is proved in the Mizar Mathematical Library.

theorem :: CARD_LAR:37
   M is strongly_inaccessible implies Rank M is being_Tarski-Class;

   The question is raised whether this proof needs the axiom of
   choice. We shall sketch an example which shows that it must.

   Later, we shall point out the precise place in the Mizar proof where
   the axiom of choice is used.

   We start with a model M of ZFC + V = L + "There is precisely one
   inaccessible cardinal, kappa."

   We do an Easton style forcing adjoining for each infinite regular
   cardinal lambda < kappa lambda^+ generic subsets of lambda. (Here
   lambda^+ is the least cardinal greater than lambda.) Call the
   resulting model M_1. M_1 is a model of ZFC + GCH and kappa remains
   inaccessible in M_1.

   Our desired model, N will be an inner model of M_1. Before
   describing it we need to establish some notation. Let A(lamda, eta)
   be the eta^th generic subset of lambda adjoined in our forcing
   extension. (So A(lambda,eta) is defined for lambda an infinite
   regular cardinal less than kappa and eta < lambda^+.)

   Let X be the set of infinite regular cardinals less than kappa.

   For lambda in X, let B(lambda) = {A(lambda, eta) | eta < lambda^+}.
   So B is a function with domain X.

   Let W be the set V_kappa, as computed in M_1.

   We can now describe the model N. It is the smallest inner model (of
   ZF) of M_1 containing all the ordinals of M_1, as well as the sets W
   and B.

   Here are some properties of N:

        1) In N, kappa is i-inaccessible.

        (This follows easily from the facts that kappa is inaccessible
        in M_1 and that W is an element of N.)

        2) In N, there is no choice function h with domain X such that
           h(lambda) is a member of B(lambda) for all lambda in X.

 	  This is proved by a standard symmetry argument using the
 	  group of automorphisms of the forcing conditions used to
 	  obtain M_1 from M.

        3) In N, V_kappa = W.

 	  (This is clear.)

        4) In N, V_kappa is not well-orderable

 	  This follows immediately from 2).

        5) In N, V_kappa is not a Tarski class.

           This is immediate from 4) since every Tarski class is
           well-orderable.

DELVING INTO THE MIZAR MML

 	In this last section I want to nail down two points. Example 3
 	shows that the proof of Theorem 37 of CARD_LAR must make
 	essential use of the axiom of choice. I want to track down
 	where this usage occurs.

 	Second, I want to unpack the definition of strongly
 	inaccessible in Mizar and show it amounts to "i-inaccessible or
 	equal to aleph_0".

 	Let's turn to the first task. The proof of CARD_LAR:37 appeals
 	to CARD_LAR:36 in the justification of the proof of claim A4.

 	In the proof of CARD_LAR:36 appeal is made to CARD_3:62 in the
 	proof of claim  A9.

 	In the proof of CARD_3:62 appeal is made to WELLORD2:26 in the
 	proof of claim A6.

 	But WELLORD2:26 simply asserts that every set can be
 	well-ordered which is well known to be an equivalent of the
 	axiom of choice.

 	Finally, here are the cites for the Mizar definition of
 	"strongly inaccessible cardinal".

 	The definition of "cardinal" and of "the cardinal of a set X"
 	are give in the article CARD_1 and are thoroughly based on the
 	axiom of choice. A cardinal is defined as an ordinal which is
 	not equipotent with any smaller ordinal. The cardinal of a set
 	X is defined as the least ordinal equipotent with X. (That
 	there is an ordinal equipotent with any set X, requires the
 	well-ordering theorem or euivalently, the axiom of choice.)

 	Cardinal exponetiation (the notation is exp(M,N)) is defined in
 	the familiar way in CARD_2 as the cardinal number of the set
 	of functions which map N to M.

 	The definition of "strongly inaccessible cardinal" is given in
 	the article CARD_FIL. First an inaccessible cardinal is
 	defined as an infinite cardinal which is regular and a limit
 	cardinal. (The definition of "limit cardinal" is tweaked so
 	that aleph_0 is a limit cardinal.

 	The definition of strongly inaccessible cardinal kappa is an
 	inaccessible cardinal such that for any cardinal N < kappa, we
 	have exp(2, N) < kappa. As I said, this is almost the
 	defintion of an i-inaccessible cardinal. However, the
 	definitions are tweaked so that a strongly inaccessible
 	cardinal (in the sense of Mizar) is either aleph_0 or an
 	i-inaccessible cardinal.




   REFERENCES

Before giving the list of references, I need to explain how I will
indicate abbreviated URLs. The problem I am trying to get around is
that some web addresses (notably aol.com) reject any letters that
contain urls from shurl.net.

I use the notation [7Su] to denote the URL obtained from the following
string:
#http#:#//#shurl#.#net#/#7Su#
by deleting every occurrence of the hash character (#).
Of course, similar unpacking will get the url associated to
e. g. [7Sv].

[Blass]
Andreas Blass, Ioanna M. Dimitriou, Benedikt L\"{o}we
Inaccessible Cardinals without the Axiom of Choice
Fundamenta Mathematicae, vol. 194(2007), pp. 179-189.
This paper appears on the web at the URL
http://dare.uva.nl/document/25381
OR
[6QG]

[G1]
This is the Wikipedia article on Grothendieck universes:
http://en.wikipedia.org/wiki/Grothendieck_universe
OR
[6QF]

[G2]
This is some notes of N. Bourbaki on Grothendieck universes in an
appendix (Appendix II) to SGA 4 Expose I.
http://modular.fas.harvard.edu/sga/sga/4-1/4-1t_185.html
OR
[8w8]

[Tarski1]
  Alfred Tarski
Ueber unerreichbare Kardinalzahlen,
Fundamenta Mathematicae, vol.30 (1938), pp.68-89.
This paper appears on the web at the URL
http://matwbn.icm.edu.pl/ksiazki/fm/fm30/fm30113.pdf
OR
[7Wd]

[Tarski2]
Alfred Tarski
On Well-ordered Subsets of any Set,
Fundamenta Mathematicae, vol.32 (1939), pp.176-183
http://matwbn.icm.edu.pl/ksiazki/fm/fm32/fm32115.pdf
OR
[7We]

[Trybulec1]
Posting January 12, 2008 04:35 of Andrzej Trybulec to Mizar-Forum
http://permalink.gmane.org/gmane.comp.mathematics.mizar/825
OR
[7Wm]

[Trybulec2]
Posting January 12, 2008 05:00 of Andrzej Trybulec to Mizar-Forum
http://permalink.gmane.org/gmane.comp.mathematics.mizar/826
OR
[7Wo]

[Urban]
Posting January 12, 2008 09:17 of Josef Urban to Mizar-Forum
http://permalink.gmane.org/gmane.comp.mathematics.mizar/827
OR
[7Wq]




More information about the FOM mailing list