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

answered Dec 13 '20 at 7:25

Emil Jeřábek

37.5k44 gold badges119119 silver badges177177 bronze badges

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

answered Dec 1 '18 at 20:12

Timothy Chow

61.3k1919 gold badges278278 silver badges462462 bronze badges

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

answered Dec 13 '20 at 6:08

Timothy Chow

61.3k1919 gold badges278278 silver badges462462 bronze badges

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

answered Oct 14 '15 at 20:02

Joel David Hamkins

193k3333 gold badges594594 silver badges10431043 bronze badges

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

answered Aug 1 '18 at 17:14

Emil Jeřábek

37.5k44 gold badges119119 silver badges177177 bronze badges

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

answered Mar 10 '21 at 17:37

Dmytro Taranovsky

4,06111 gold badge1212 silver badges3131 bronze badges

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

answered Dec 13 '16 at 13:20

Joel David Hamkins

193k3333 gold badges594594 silver badges10431043 bronze badges

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

answered Oct 15 '21 at 19:54

Noah Schweber

25.5k44 gold badges7777 silver badges228228 bronze badges

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

answered Mar 13 '14 at 1:47

Bjørn Kjos-Hanssen

23.4k33 gold badges4848 silver badges108108 bronze badges

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

answered Mar 31 '21 at 11:35

Emil Jeřábek

37.5k44 gold badges119119 silver badges177177 bronze badges

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

#### Related Tags

theories-of-arithmetic × 247lo.logic × 194

model-theory × 54

set-theory × 51

proof-theory × 29

computability-theory × 28

reverse-math × 20

nt.number-theory × 18

reference-request × 17

foundations × 12

mathematical-philosophy × 10

ordinal-analysis × 10

ultrafinitism × 10

metamathematics × 9

computational-complexity × 7

ac.commutative-algebra × 6

decidability × 6

induction × 6

forcing × 5

ordinal-numbers × 5

nonstandard-analysis × 5

bounded-arithmetic × 5

prime-numbers × 4

constructive-mathematics × 4

soft-question × 3