[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