Are there any well-known statements independent of NF? And also, are there prerequisites suggesting that NF in any way, to one extent or another, are not covered by the incompleteness theorem?
5
-
4$\begingroup$ NF interprets $Q$, and as such it is subject to Gödel’s first and second incompleteness theorems. $\endgroup$– Emil JeřábekCommented May 19, 2020 at 18:09
-
1$\begingroup$ @EmilJeřábek Interpreting $Q$ is not enough for the second incompleteness theorem, is it? $\endgroup$– Noah SchweberCommented May 19, 2020 at 19:26
-
3$\begingroup$ @NoahSchweber Yes, it is enough. See Pudlák, Cuts, consistency statement and interpretations, JSL 50 (1985), 423–441. See also Visser, Can we make the second incompleteness theorem coordinate free?. $\endgroup$– Emil JeřábekCommented May 20, 2020 at 5:59
-
$\begingroup$ @EmilJeřábek, NoahSchweber, I think since we are speaking about a set theory, its more relevant to refer to the result that if any set theory can interpret Adjunctive set theory (i.e. Empty set + Adjunction) then it would be subject to Godel's incompleteness theorems!!! And of course NF satisfies those. [Note: adjunction is the axiom: $\forall x \forall y \exists z \forall m (m \in z \iff m \in x \lor m=y)$] $\endgroup$– Zuhair Al-JoharCommented May 22, 2020 at 18:48
-
3$\begingroup$ @ZuhairAl-Johar Yes, the adjunctive set theory is mutually interpretable with $Q$. However, the result about $Q$ is more fundamental. In particular, the second incompleteness theorem refers to $\mathrm{Con}_T$, which is an arithmetical formula: it says that no consistent r.e. theory $T$ can interpret $Q+\mathrm{Con}_T$ (more precisely, $Q+\mathrm{Con}_\tau$ for any $\Sigma_1$ formula $\tau$ that defines an axiom set for $T$ in $\mathbb N$). You cannot even formulate this properly for the adjunctive set theory without first fixing a specific interpretation of $Q$ inside the theory. $\endgroup$– Emil JeřábekCommented May 23, 2020 at 8:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If NF is consistent, then yes Con(NF) would be one of these statements that are independent of NF. NF can interpret finite order arithmetic, so by that it would be subject to Godel incompleteness theorems. If Randall Holmes's proof of Con(NF) is correct, then NF is slightly stronger than finite order arithmetic, this means that all strong axioms of infinity are independent of it.
OF course as regards NFU (which is equi-interpretable with SF (the theory with the single schema of stratified comprehension)) the matter is settled, its incomplete for the same reasons, it's not even complete for stratified statements of its language since it cannot prove infinity. Actually even known consistent weakening of NF to only three types "NF3" or to only using predicative formulas "NFP" (or mildly impredicative ones "NFI") are also incomplete! With known independent results [see here]
answered May 19, 2020 at 23:18