[FOM] Strength of Logical Principles
Dmytro Taranovsky
dmytro at mit.edu
Thu Mar 1 17:22:55 EST 2012
The hierarchy of consistency strengths is best understood through a
hierarchy of key mathematical principles. The principles, listed in
order of increasing strength, are: recursion, unbounded quantification,
impredicativity, cumulative hierarchy, and elementary embeddings.
Recursion allows us to define fast growing functions, such as
exponentiation, and very large integers, much larger than can feasibly
be stored in a computer.
A natural way to go beyond primitive recursion is to use formulas with
unbounded quantification over integers, which easily gives us Peano
Arithmetic.
To go much beyond PA, the easiest way is to use real numbers, using
quantification over all real numbers -- not just those that we
previously defined -- to define new real numbers.
To go beyond just impredicative quantification, we can introduce the set
of all real numbers, the power set operation, and the cumulative
hierarchy of sets.
--- Elementary Embeddings ---
The strength gets higher as one ascends the cumulative hierarchy. We
can assert that it extends far enough by asserting symmetries between
different levels of the hierarchy, which are naturally expressed as
elementary embeddings.
Stating elementary embedding principles in ZF is quite easy. However,
the axiom of choice imposes limits on elementary embeddings -- think of
it as an analogue of existence of non-measurable sets -- so one has to
be careful that the principles are consistent with the axiom of choice.
A very strong principle for ZF is:
There is a set kappa such that every binary relation whose domain
includes kappa as a subset is nontrivially self-embeddable.
(Note: The domain is assumed to be a set. Making the domain exactly
kappa would be too weak since AD implies that every binary relation on
omega_1 is nontrivially self-embeddable (under AD, every subset of
omega_1 is constructible from a real and every real has a sharp).
However, a natural weakening would be to make the domain V_kappa.)
This is inconsistent with the axiom of choice, and finding natural
principles of the same strength in ZFC is an open problem. However, we
can include weaker principles such as
I3: For some lambda, there is a nontrivial elementary embedding
j:V_lambda-->V_lambda.
These do not pose a problem with the axiom of choice -- by starting from
ZF and a slightly stronger principle, one can add a generic
well-ordering of V and get ZFC with the desired principle. Of course,
using something in a consistency principle is different from asserting
its metaphysical existence. However, to make a convincing argument that
I3 is false, one would need a natural reasonable combinatorial principle
that is contradicted by I3, which appears to be lacking.
Is there something beyond the various elementary embedding principles?
We do not know, but the richness of our experience suggests that the
answer is yes.
Sincerely,
Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm
More information about the FOM
mailing list