[FOM] the notion of "effectively complete"

[Dmytro Taranovsky]

The short answer to the question is that
- Z_2 + PD is effectively complete in the sense that it has few (if any) 
incompleteness in the basic theory of real numbers and projective sets.
- PA is already effectively complete.
- "effectively complete" does not preclude incompleteness for 
exceptional natural statements, and there are natural arithmetic 
statements independent of ZFC.

Given the central importance to foundations of mathematics, I will also 
give a much longer explanation.

To start, consider:
1. Presburger arithmetic for natural numbers under addition.
2. Peano arithmetic (PA) for the first order theory of natural numbers.
3. ZFC for the first order set theory.

(1) is complete.  (3) has obvious basic incompleteness (such as the 
Continuum Hypothesis (CH)).  (2) is incomplete, but (while it exists) 
natural incompleteness is hard to come by, so it is "effectively complete".

Every consistent c.e. theory that includes basic arithmetic is 
incomplete, but a recurring theme is that once appropriate basic 
principles are axiomatized, it resembles a complete theory as far as 
mathematical practice is concerned.  This extends to second order 
arithmetic (and beyond), and I conjecture to set theory, though even at 
third order arithmetic, we understand too little. The required strength 
grows as the level of expressiveness (or descriptive complexity) increases:
- EFA (Exponential Function Arithmetic) suffices for many Pi-0-1 statements.
- PA is the minimal effectively complete theory of first order arithmetic.
- Existence of zero sharp leads to an effectively complete theory for 
the constructible universe L (including its large cardinals).
- Z_2 + PD (second order arithmetic with projective determinacy) is the 
minimal effectively complete theory of second order arithmetic.

In general, "effectively complete" is vague.  For example, how many 
traces of zero sharp (which is not itself in L) must be present to 
effectively complete the basic large cardinal structure of L?  Also, Z_2 
+ V=L is arguably the minimal effectively complete theory for 
constructible real numbers, but it does not prove Borel determinacy.  
However, just like every increasing infinite sequence of natural numbers 
has the same limit (infinity), we can have unambiguous closure points 
for "effectively complete", hence the above statements about PA and 
Z_2+PD being minimal effectively complete (among sound theories).

Effective completeness is related to our methods for proving 
incompleteness: Effective completeness corresponds to closure under 
appropriate basic constructs, and absence of closure creates an 
opportunity for changing things.  For weak theories of arithmetic, 
incompleteness can be manifested through existence of definable cuts, 
and non-existence of such cuts is equivalent to PA.  One may encounter 
PA incompleteness in specialized areas (and one can argue that the 
choice of words "effectively complete" is misleading), but basic 
principles such as induction are all provable.

In set theory, incompleteness is mostly shown through forcing, but the 
connection with "effectively complete" has subtle aspects.  For example, 
in ZFC (plus infinitely many strong cardinals) after collapse of a limit 
of strong cardinals to omega, second order arithmetic is absolute under 
further forcing, but PD need not hold. One can view this as achieving 
closure at a lower expressiveness level than intended for second order 
arithmetic, with forcing unable to create new structure to raise the 
expressiveness.  However, with projective determinacy in every generic 
extension of V, we get absoluteness without needing such collapse, and 
PD is compatible with V=K (the core model).  Also, absoluteness of L(R) 
is equivalent to determinacy in L(R) holding in all generic extensions of V.

Going further, a measurable Woodin cardinal (or its traces in third 
order arithmetic) plus CH might be effectively complete for Sigma^2_1 
statements and slightly beyond that, but the implications of the theory 
(including iterability) have not yet been worked out, though the 
conditional Sigma^2_1 generic absoluteness and other factors make the 
theory promising.  However, while I believe CH is true, its status 
continues to be hotly debated.  Beyond that, see my FOM posting "On the 
Nature of Reals" 
https://cs.nyu.edu/pipermail/fom/2016-October/020147.html for thoughts 
about much higher descriptive complexity levels.

Natural Incompleteness

While effective completeness resembles completeness, the resemblance has 
its limits.  Not only do the large cardinals (presumably) exist in the 
infinite realm, but constructions resembling them can be carried out 
with finite numbers.  Ignoring their ontological status and interaction 
with other axioms, large cardinal axioms correspond to simple patterns 
that can be instantiated in many ways.  In my paper "Finitistic 
Properties of High Complexity" https://arxiv.org/abs/1707.05772 , I 
develop connections between infinite and finite but sufficiently large, 
including a connection between projective determinacy and finite games 
(with the possibility of both players losing raising the question of 
determinacy).

A good example of reinterpreting large cardinal axioms is in Harvey 
Friedman's FOM posting "23:Q-Systems and Proof Theoretic Ordinals" 
https://cs.nyu.edu/pipermail/fom/1998-November/002432.html and in his 
other work.  His recent paper "Tangible Mathematical Incompleteness of 
ZFC" gives natural arithmetic statements independent of ZFC.  As an 
astute observer will note, there the use of relations, order invariance, 
and stability resembles the stationary reflection principle.  Stable 
emulators correspond to fragments of models of n-subtle cardinals, and 
failure of maximality corresponds to inconsistency, though perhaps 
Harvey Friedman can explain it more precisely.

Sincerely,
Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm