Some Cardinal Arithmetic

Some time ago, Asaf Karagila wrote wonderful post wherein he shows that, even without assuming the axiom of choice one can always find four cardinals \(\mathfrak{p} \lt \mathfrak{q}\) and \(\mathfrak{r} \lt \mathfrak{s}\) such that \(\mathfrak{p}^{\mathfrak{r}} = \mathfrak{q}^{\mathfrak{s}}.\) In the comments, Harvey Friedman asks:

Your theorem is an example of an existential sentence about cardinals in the language with only \(\lt \) and exponentiation. Can you determine which sentences in that language are provable in ZF? More generally, expand the set of sentences about cardinals considered, obviously to include addition and multiplication, and perhaps alternating quantifiers.

After Peter Krautzberger’s tiny blogging challenge, I decided to spend 30 minutes thinking and writing about this…

… 

 

Paris-Harrington and Typing

I just read an interesting paper by Thomas Forster: The Paris–Harrington Theorem in an NF context [1]. This paper is a progress report on the status of the Paris–Harrington Theorem in Quine’s New Foundations (NF). Forster shows that the Paris–Harrington Theorem is at least consistent with NF, but leaves open the question whether it is provable in NF. Recall that the Paris–Harrington Theorem is a variation on Ramsey’s Theorem, where the homogeneous set $x$ is required to be relatively large: $\min(x) < |x|$. This result is not provable in Peano Arithmetic (PA). In fact, it is logically equivalent to $\Sigma_1$-reflection for PA.

The main issue with the Paris–Harrington Theorem in NF is that the notion of relative largeness is ill-typed. In addition to Forster, Harvey Friedman had also observed this [2]:

In ‘relatively large’, an integer is used both as an element of a finite set and as a cardinality (of that same set).

This is a serious problem in NF where cardinal numbers are defined as equivalence classes of equinumerous sets. Thus, the relative largeness condition $\min(x) < |x|$ entails a direct comparison between an element of the finite set $x$ and the cardinal number $|x|$ to which $x$ belongs. Needless to say that this is difficult to formulate in a stratified manner, as required for set comprehension in NF. Forster manages to work around this, but the winding road has so many twists that he only manages to get a consistency result rather than an actual proof.

While Forster does not directly discuss the issue of the strength of the Paris–Harrington Theorem in the paper, he does raise an interesting question whether the added strength of the theorem has any link to this failure of typing. I used to believe that while the naturalness of the Paris–Harrington Theorem could honestly be questioned, there was one real advantage of this example over the non-provable statements of Gödel and Rosser in that the Paris–Harrington Theorem did not appear to directly depend on self-reference. This observation by Forster and Friedman casts some serious doubts on this…

  • Is the notion of relative largeness really self-referential?
  • Is the fact that relative largeness is ill-typed the key to the strength of the Paris–Harrington Theorem?

References

[1] T. E. Forster, “The Paris-Harrington theorem in an NF context,” in One hundred years of axiomatic set theory, Acad.-Bruylant, Louvain-la-Neuve, 2010, vol. 17, pp. 97-109.
[Bibtex]
@incollection{Forster10,
AUTHOR = {Forster, Thomas Edward},
TITLE = {The {P}aris-{H}arrington theorem in an {NF} context},
BOOKTITLE = {One hundred years of axiomatic set theory},
SERIES = {Cahiers Centre Logique},
VOLUME = {17},
PAGES = {97--109},
PUBLISHER = {Acad.-Bruylant, Louvain-la-Neuve},
YEAR = {2010},
MRCLASS = {03E70 (03E35)},
MRNUMBER = {2796910},
}
[2] H. Friedman, [FOM] PA incompleteness, 2007.
[Bibtex]
@misc{Friedman07,
AUTHOR = {Friedman, Harvey},
TITLE = {{[FOM]} {PA} incompleteness},
HOWPUBLISHED = {FOM},
NOTE = {\url{http://www.cs.nyu.edu/pipermail/fom/2007-October/012046.html}},
YEAR = {2007},
URL = {http://www.cs.nyu.edu/pipermail/fom/2007-October/012046.html},
}