[FOM] RE: 195:The axiom of choice

[Marcin Mostowski]

I do not understand your examples.

In the first case of GBN, you propose the following equivalent of AC:

(\exists A)(\forall x)[(\exists y)(y\in x) implies (\exists y)(y\in x
and y
\in A)].

This is easily provable without AC e.g. by taking A=V, where V is the
full
class.

The second example in ZF:

(\forall x)(\exists y)(\forall z)[(z\in x and (\exists w)[w\in z])
implies (\exists w)(w\in z and w\in y)].

Again it is provable in ZF without AC by choosing y=x.

In general, what is essential in AC, this is possibility of choosing a
unique element from each set.

E.g. the following is equivalent to AC:

\forall R (\forall x \exists y R(x,y) implies
\exists F \subseteq R (\forall x \exists y F(x,y) and
  \forall x \forall y,y' 
    (R(x,y) and R(x,y') implies y=y') ).

This has more than 6 quantifiers but has quantifier depth 4, and it
seems
to be optimal.

Marcin Mostowski





> Hervey asks about equivalents of the axiom of choice with fewer than 6
> quantifiers.  I would like to point out that in the GBN theory of
classes,
> (one version of) the axiom of global choice has 4 quantifiers:
> 
> (GC)  There is a class whose intersection with every nonempty set is
> nonempty.
> 
> The formalized version of (GC) is as follows:
> 
> (\exists A)(\forall x)[(\exists y)(y\in x) implies (\exists y)(y\in x
and y
> \in A)].
> 
> Now, if we relativize this to ZF so that we get a comparable statement
of
> the axiom of choice, we get
> 
> (AC) To every set x there corresponds a set whose interesections with
the
> nonempty members of x are nonempty.
> 
> This formalizes in the language of ZF as follows:
> 
> (\forall x)(\exists y)(\forall z)[(z\in x and (\exists w)[w\in z])
> implies (\exists w)(w\in z and w\in y)].
> 
> If I have made no mistakes, then it seems this is a statement of AC
with 5
> quantifiers.
> 
> 
> 
> Dr. Matt Insall
> Associate Professor of Mathematics
> Department of Mathematics and Statistics
> University of Missouri - Rolla
> Rolla MO 65409-0020
> 
> insall at umr.edu
> montez at fidnet.com
> (573)341-4901
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom