Skip to main content
deleted 3 characters in body
Source Link
Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105

As in the question, I will use $\mathsf{NFU}$ for "bare" $\mathsf{NFU}$, i.e., the result of weakening the extensionality axiom in Quine's $\mathsf{NF}$ so as to allow urelements. Let $\mathsf{NFU}^{-\infty}$ be $\mathsf{NFU} \cup \{\lnot \mathsf{Infinity} \}$, where $\mathsf{Infinity}$ is the axiom of infinity.

In 2002, Solovay proved the following results. The proofs were disseminated among some NFU enthusiasts, but alas, they remain unpublished. In what follows $\mathsf{Exp}$ is the statement asserting the totality of the exponential function, and $\mathsf{SupExp}$ is the statement asserting the totality of the superexponential function (also known as tetration), i.e., the "stack of twos" function, $f(n)$, where $f(0) = 1$ and $f(n+1) = 2^{f(n)}$.

Theorem. (1) $\mathrm{I}\Delta_{0} + \mathsf{SupExp} \vdash\mathsf{Con}(\mathsf{NFU}^{-\infty}) \leftrightarrow\mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(2) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \vdash \mathsf{Con} (\mathsf{NFU}^{-\infty})\rightarrow \mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(3) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \nvdash \mathsf{Con} (\mathrm{I}\Delta_{0} + \mathsf{Exp})\rightarrow\mathsf{Con} (\mathsf{NFU}^{-\infty})$.

Suspected Answer to Question 1. Based on the above theorem (part 1), the proof theoretic ordinal of $\mathsf{NFU}^{-\infty}$ is likely to be the same as the proof theoretic ordinal of $\mathrm{I}\Delta_{0} + \mathsf{SupExp}$$\mathrm{I}\Delta_{0} + \mathsf{Exp}$, i.e., is $\omega^4$$\omega^3$, if one were to follow the procedure given by Taranovsky to this question.

Answer to Question 2 Solovay's proof of the above theorem makes it clear that $\mathsf{NFU}^{-\infty}$ interprets $\mathrm{I}\Delta_{0} + \mathsf{Exp}$, but not vice versa; thus the interpretability relation between $\mathsf{NFU}^{-\infty}$ and $\mathrm{I}\Delta_{0} + \mathsf{Exp}$ is similar to the interpretability relation between $\mathsf{ACA}_0$ and $\mathsf{PA}$.

As in the question, I will use $\mathsf{NFU}$ for "bare" $\mathsf{NFU}$, i.e., the result of weakening the extensionality axiom in Quine's $\mathsf{NF}$ so as to allow urelements. Let $\mathsf{NFU}^{-\infty}$ be $\mathsf{NFU} \cup \{\lnot \mathsf{Infinity} \}$, where $\mathsf{Infinity}$ is the axiom of infinity.

In 2002, Solovay proved the following results. The proofs were disseminated among some NFU enthusiasts, but alas, they remain unpublished. In what follows $\mathsf{Exp}$ is the statement asserting the totality of the exponential function, and $\mathsf{SupExp}$ is the statement asserting the totality of the superexponential function (also known as tetration), i.e., the "stack of twos" function, $f(n)$, where $f(0) = 1$ and $f(n+1) = 2^{f(n)}$.

Theorem. (1) $\mathrm{I}\Delta_{0} + \mathsf{SupExp} \vdash\mathsf{Con}(\mathsf{NFU}^{-\infty}) \leftrightarrow\mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(2) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \vdash \mathsf{Con} (\mathsf{NFU}^{-\infty})\rightarrow \mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(3) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \nvdash \mathsf{Con} (\mathrm{I}\Delta_{0} + \mathsf{Exp})\rightarrow\mathsf{Con} (\mathsf{NFU}^{-\infty})$.

Suspected Answer to Question 1. Based on the above theorem (part 1), the proof theoretic ordinal of $\mathsf{NFU}^{-\infty}$ is likely to be the same as the proof theoretic ordinal of $\mathrm{I}\Delta_{0} + \mathsf{SupExp}$, i.e., is $\omega^4$, if one were to follow the procedure given by Taranovsky to this question.

Answer to Question 2 Solovay's proof of the above theorem makes it clear that $\mathsf{NFU}^{-\infty}$ interprets $\mathrm{I}\Delta_{0} + \mathsf{Exp}$, but not vice versa; thus the interpretability relation between $\mathsf{NFU}^{-\infty}$ and $\mathrm{I}\Delta_{0} + \mathsf{Exp}$ is similar to the interpretability relation between $\mathsf{ACA}_0$ and $\mathsf{PA}$.

As in the question, I will use $\mathsf{NFU}$ for "bare" $\mathsf{NFU}$, i.e., the result of weakening the extensionality axiom in Quine's $\mathsf{NF}$ so as to allow urelements. Let $\mathsf{NFU}^{-\infty}$ be $\mathsf{NFU} \cup \{\lnot \mathsf{Infinity} \}$, where $\mathsf{Infinity}$ is the axiom of infinity.

In 2002, Solovay proved the following results. The proofs were disseminated among some NFU enthusiasts, but alas, they remain unpublished. In what follows $\mathsf{Exp}$ is the statement asserting the totality of the exponential function, and $\mathsf{SupExp}$ is the statement asserting the totality of the superexponential function (also known as tetration), i.e., the "stack of twos" function, $f(n)$, where $f(0) = 1$ and $f(n+1) = 2^{f(n)}$.

Theorem. (1) $\mathrm{I}\Delta_{0} + \mathsf{SupExp} \vdash\mathsf{Con}(\mathsf{NFU}^{-\infty}) \leftrightarrow\mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(2) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \vdash \mathsf{Con} (\mathsf{NFU}^{-\infty})\rightarrow \mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(3) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \nvdash \mathsf{Con} (\mathrm{I}\Delta_{0} + \mathsf{Exp})\rightarrow\mathsf{Con} (\mathsf{NFU}^{-\infty})$.

Suspected Answer to Question 1. Based on the above theorem (part 1), the proof theoretic ordinal of $\mathsf{NFU}^{-\infty}$ is likely to be the same as the proof theoretic ordinal of $\mathrm{I}\Delta_{0} + \mathsf{Exp}$, i.e., is $\omega^3$, if one were to follow the procedure given by Taranovsky to this question.

Answer to Question 2 Solovay's proof of the above theorem makes it clear that $\mathsf{NFU}^{-\infty}$ interprets $\mathrm{I}\Delta_{0} + \mathsf{Exp}$, but not vice versa; thus the interpretability relation between $\mathsf{NFU}^{-\infty}$ and $\mathrm{I}\Delta_{0} + \mathsf{Exp}$ is similar to the interpretability relation between $\mathsf{ACA}_0$ and $\mathsf{PA}$.

Source Link
Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105

As in the question, I will use $\mathsf{NFU}$ for "bare" $\mathsf{NFU}$, i.e., the result of weakening the extensionality axiom in Quine's $\mathsf{NF}$ so as to allow urelements. Let $\mathsf{NFU}^{-\infty}$ be $\mathsf{NFU} \cup \{\lnot \mathsf{Infinity} \}$, where $\mathsf{Infinity}$ is the axiom of infinity.

In 2002, Solovay proved the following results. The proofs were disseminated among some NFU enthusiasts, but alas, they remain unpublished. In what follows $\mathsf{Exp}$ is the statement asserting the totality of the exponential function, and $\mathsf{SupExp}$ is the statement asserting the totality of the superexponential function (also known as tetration), i.e., the "stack of twos" function, $f(n)$, where $f(0) = 1$ and $f(n+1) = 2^{f(n)}$.

Theorem. (1) $\mathrm{I}\Delta_{0} + \mathsf{SupExp} \vdash\mathsf{Con}(\mathsf{NFU}^{-\infty}) \leftrightarrow\mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(2) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \vdash \mathsf{Con} (\mathsf{NFU}^{-\infty})\rightarrow \mathsf{Con}(\mathrm{I}\Delta_{0} + \mathsf{Exp})$.

(3) $\mathrm{I}\Delta_{0} + \mathsf{Exp} \nvdash \mathsf{Con} (\mathrm{I}\Delta_{0} + \mathsf{Exp})\rightarrow\mathsf{Con} (\mathsf{NFU}^{-\infty})$.

Suspected Answer to Question 1. Based on the above theorem (part 1), the proof theoretic ordinal of $\mathsf{NFU}^{-\infty}$ is likely to be the same as the proof theoretic ordinal of $\mathrm{I}\Delta_{0} + \mathsf{SupExp}$, i.e., is $\omega^4$, if one were to follow the procedure given by Taranovsky to this question.

Answer to Question 2 Solovay's proof of the above theorem makes it clear that $\mathsf{NFU}^{-\infty}$ interprets $\mathrm{I}\Delta_{0} + \mathsf{Exp}$, but not vice versa; thus the interpretability relation between $\mathsf{NFU}^{-\infty}$ and $\mathrm{I}\Delta_{0} + \mathsf{Exp}$ is similar to the interpretability relation between $\mathsf{ACA}_0$ and $\mathsf{PA}$.