[FOM] RE: 195:The axiom of choice
Marcin Mostowski
Marcin.Mostowski at mail.uw.edu.pl
Wed Nov 5 10:55:32 EST 2003
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
More information about the FOM
mailing list