17

Gödel’s second incompleteness theorem requires neither exponentiation nor “impredicative concepts”. The systems Nelson works in are fragments of arithmetic interpretable on definable cuts in $Q$; one such fragment is the bounded arithmetic $I\Delta_0+\Omega_1$ (this appears to be what Nelson calls $Q_4$ in the Predicative arithmetic book). The theory $I\...


16

Christian Schulz (a grad student at Urbana) and Philipp Hieronymi have recently shown that $(\mathbb{Z},+,<,2^{\mathbb{N}},3^{\mathbb{N}})$ is undecidable. And I believe they prove this for $(\mathbb{Z},+,<,m^{\mathbb{N}},n^{\mathbb{N}})$ for $m,n \in \mathbb{N}$ with $\log_m n$ irrational. The paper isn't out yet but the result has been presented in ...


15

According to Harvey Friedman, the following theorem is provable in PA but not HA: Every polynomial $P:\mathbb{Z}^n \to \mathbb{Z}^m$ with integer coefficients assumes a value closest to the origin. That is, there is a value which is at least as close to the origin, in the Euclidean distance, than any other value. This is unprovable in HA even when $m=1$....


13

There are several notable papers, starting with a key paper of Angus Macintyre (Ramsey quantifiers in arithmetic, Model theory of algebra and arithmetic, Lecture Notes in Math., 834, Springer, 1980), which explore natural extensions of Peano Arithmetic formulated in "well-behaved" logics extending first order logic. The most well-known of these ...


12

The answer to the question is in the positive. Let $(\cal{N}^*,\textrm{Tr*})$ be a rather classless elementary extension of $(\cal{N},\textrm{Tr})$, where $\cal{N}$ is a model of PA, and $\textrm{Tr}$ is a full truth predicate on $\cal{N}$, e.g., let $\cal{N}$ be the standard model of PA, and $\textrm{Tr}$ be the usual Tarskian truth predicate on $\cal{N}$. ...


11

(EDIT: I have substantially rewritten this answer in light of what I have learned from Emil Jeřábek and from reading some of the relevant references more carefully.) As Emil Jeřábek has said, the short answer to your second question is yes, but there are some caveats to note. First of all, it is perhaps not immediately obvious even how to state Gödel’s ...


10

This argument has a couple of iffy points, but I believe it does work. In this paper, Shelah introduced a logic $\mathcal{L}(Q_{\mathrm{Brch}})$ which is fully compact, has the property that any countable theory with infinite models has models of every uncountable cardinality, and is strictly stronger than FOL for countable models. That paper is pretty awful ...


9

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 ...


9

Since no one else is biting, I'll answer, and thanks to comments I now this is accurate: $I\Delta_0$ can prove several basic theorems: Every square equals 0 or 1 mod 4 No prime has a rational square root The only solutions to $x^3+y^3=z^3$ or $x^4+y^4=z^4$ are trivial Every $x$ is divisible by a prime $p$ with $p \le x$ (The standard proofs can be ...


9

In addition to the answers above, it is worth mentioning that the existential fragment of Presburger arithmetic can actually be extended by a full divisibility predicate while retaining decidability [1]. Satisfiability in the resulting fragment is in NEXP, the lower bound being NP [2]. Also, it is possible to define a family of formulas $\Phi_n(x,m)$ such ...


8

This is a great question! Let me give a meager partial answer, for the case where we are talking about nonstandard models of true arithmetic. Theorem. No nonstandard model of true arithmetic arises as the quotient of a structure $\langle N,+,\cdot\rangle$ by an equivalence relation $\approx$, if $+$ is computable and $\approx$ is co-c.e. Indeed, there is ...


7

$\mathsf{TA}_{\exp}$ does have recursive nonstandard models. In fact, even the considerably stronger theory $\mathrm{Th}(\mathbb N,+,2^x)$ (Presburger arithmetic with exponentiation) has recursive nonstandard models. This follows from results of Semënov, elaborated in this paper by Point: the theory is decidable (with an explicitly given axiom set), and it ...


6

Gurevich and Shelah showed in The monadic theory and the “next world” that the monadic theory of the real line (or even just the Cantor Discontinuum) can compute - the $V^B$ theory of second order arithmetic, - the $V^B$ theory of third order arithmetic if CH holds (or if the union of $<\!c$ meager sets is meager), where $B$ is the Boolean algebra of ...


6

The statement asserting that every number is a counting number is $\forall n\ C(n)$, and this is definitely independent of PA, if PA is understood to include induction only in the usual language of arithmetic, without the predicate $C$. To see this, we can simply observe that the statement is true in the standard model of arithmetic, but in any non-standard ...


5

Your second question has been properly answered by Emil Jerabek, I would say. Reading some of the comments, I feel I should write the following about your first question: From talking to Ed Nelson and to people who knew him well, I can say that Ed Nelson has for a long time been firmly convinced that the exponential function somehow leads to inconsistency (...


5

Q1 Theorem1. Let $M$ be a countable nonstandard model of $PA$, let $r,c,a\in M\setminus\mathbb{N}$, $M\models r,c\leq a$, and suppose $M\models Con_{{\bf I}\Sigma_r}$. Then there exists a model $K$ of $PA$ such that $a\in K$ and $M|_a=K|_a$, $M|_{2^a}\subseteq K$, $K\models\exists d<2^{a^c}Pr_{{\bf I}\Sigma_r}(d,\ulcorner\bot\urcorner)$, $K\models Con_{...


5

(The final two sections are translated modulo tweaks...) I do not know the answer to your question, but I can try to translate (part of) this paper. There are some terms that are unfamiliar to me (e.g., "infinite internal sets" as remarked in a comment) so I will indicate where I am quite confused by using brackets. I am making this community wiki as I am ...


5

The current version of the question is flawed: the proposed categoricity principle is in fact classically false. Roughly speaking, any "interesting" theory of the appropriate type is going to have lots of non-isomorphic countable $\omega$-models. (For massive overkill let $M,N$ be countable elementary submodels of $V_{\omega_{17}}$ with $M\in N$ ...


5

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known). Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and ...


5

I believe you don't need this, but assume that there is a strongly inaccessible cardinal $\kappa$. Fix a first-order completion $T$ of $\mathsf{PA}$ and let $\mathcal{M}$ be a saturated model of $T$ of cardinality $\kappa$. I will show that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable cuts. Claim. For any $\Sigma^1_1(a)$ formula $\varphi(x,a)$,...


4

The following paper by my supervisor Andreas Weiermann studies the principle PH$_f$ you mention: A. Weiermann, A classification of rapidly growing Ramsey functions Proc. Amer. Math. Soc. 132 (2004), no. 2, 553–561. There are many follow-up papers with plenty of variations by Andreas and his collaborators. As to your question, any answer here depends greatly ...


4

I interpret this question as asking, what is the first ordinal $\alpha$ such that there is some lost melody (in the sense of Hamkins-Lewis Theorem 4.9) in $L_\alpha$. The answer is $\alpha=\Sigma+1$ (or $\Sigma+\omega$ if you really insist on it being limit). Indeed, the argument in Theorem 4.9 of the paper produces a lost melody inside $L_{\beta+1}$, where $...


4

This question is based on a misunderstanding of the situation already in $\mathsf{PA}$: equality is representable in $\mathsf{PA}$ only for terms, or at the very least relatively simple formulas. To see this consider, given an arbitrary sentence $\varphi$, the formula (modulo obvious abbreviations) $$\psi(x)\equiv(x=0\wedge\varphi)\vee(x=1\wedge\neg\varphi).$...


4

The only way I can make sense of the result of the abstract is as follows: Let $M$ be any nonstandard model of PA (Peano arithmetic), then it is well-known (and first demonstrated by Feferman in [this 1964 paper][1], using an arithmetical adaptation of Cohen forcing), one can build an infinite family $\cal{S}$ of subsets of $M$ such that the structure $(...


3

Yes, that does seem to be what the paper is claiming. The author seems to be an expert, so there seems to be little reason to doubt the question is open. :)


3

In fact all true arithmetical sentences have weak classical realizers. Namely, a true arithmetical sentence $\psi$ $$\forall x_1\exists y_1 \ldots \forall x_n\exists y_n \theta(x_1,\ldots,x_n,y_1,\ldots,y_n)$$ is weakly realized by $(e_1,\ldots,e_n)$, where $\Phi_{e_i}^{\vec{g}}(y_1,\ldots,y_{i-1})$ performs an unbounded search for a tuple $(y_i,\ldots,y_n)$ ...


2

$T$ is inconsistent. The argument below is due to Robert Solovay (it is attributed to a letter from Solovay to Nelson in Visser’s Peano Basso and Peano Corto, see Lemma 3.7). Let $2^x_n$ denote the iterated exponential function $2^x_0=x$, $2^x_{n+1}=2^{2^x_n}$. It is well known that the graph of $2^x_n$ has a well-behaved $\Delta_0$ definition in $I\Delta_0$....


1

There are many structures which have decidable theories, and these theories are necessarily consistent and complete. For instance: The theory of any given finite structure Primitive recursive arithmetic The theory of $(\mathbb R, +, \cdot, <, x \mapsto e^x)$ The theory of algebraically-closed commutative fields of characteristic zero The theory of the ...


1

A third try, with thanks to Emil Jerabek for correcting the previous two: The following $\mathcal{M}=(S,0,',<,\exp)$ is a recursive non-standard model for the language, and I conjecture that it is a model for the theory: The sequence $(a,b,c;k)$ is intended to represent \begin{align} &a + \exp(b+\exp(c+\omega) &\text{ if }k=0 \\ &a + \exp(b+\...


1

This is not an answer, but it's too long for a comment. You can optimize away the distinction between filled and unfilled cuts as follows. Define a cut to be a pair of subsets $A$ and $B$ such that: $A$ is lower rounded: $x \in A \iff \exists y \in A \,.\, x < y$ $B$ is upper rounded: $y \in B \iff \exists x \in B \,.\, x < y$ $A$ and $B$ are disjoint ...


Only top voted, non community-wiki answers of a minimum length are eligible