[FOM] On AE...EA...A

Harvey Friedman friedman at math.ohio-state.edu
Wed Apr 2 22:50:43 EST 2003


The complexity class

AE...EA...A

of sentences in primitive notation (epsilon,=), is very wild.

In particular, every sentence of the form

A...AE...EA...A(phi)

where phi is a formula with epsilon bounded quantifiers,

can be effectively converted to an equivalent sentence of the form

AE...EA...A

in epsilon,=. Furthermore, the conversion is provably correct in ZFC.

This means that the set of true sentences of the form AE...EA...A in 
epsilon,= is of very high degree, and there are plenty of instances 
which are undecided in ZFC.

In my paper Three Quantifiers on 
http://www.mathpreprints.com/math/Preprint/show/

I show that every sentence with three quantifiers (not blocks) in 
epsilon,=, is decided in a weak fragment of ZF without power set.

The above shows that this does not hold for three blocks of quantifiers.





More information about the FOM mailing list