[FOM] Strength of Logical Principles

[Dmytro Taranovsky]

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