[FOM] the notion of "effectively complete"
Dmytro Taranovsky
dmytro at mit.edu
Mon Sep 24 22:02:28 EDT 2018
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
More information about the FOM
mailing list