Questions tagged [peano-arithmetic]

Peano arithmetic (or Peano axioms) is a set of axioms for the natural numbers proposed by Giuseppe Peano in 1889.

Filter by
Sorted by
Tagged with
2
votes
2answers
219 views

Is there any reasonable non-regular Gödel numbering of the language of arithmetic?

Let $\mathcal{L}$ be the language of arithmetic given as follows: $x::= {\sf v} \mid x'$ $t ::= x \mid 0 \mid {\sf S}t \mid (t+t) \mid (t\times t)$ $A ::= \bot \mid \top \mid t=t \mid \neg A \mid (A \...
49
votes
1answer
2k views

In the two-person Killing the Hydra game, what is the winning strategy?

My question is which player has a winning strategy in the two-player version of the Killing the Hydra game? In their amazing paper, Kirby, Laurie; Paris, Jeff, Accessible independence results for ...
7
votes
1answer
297 views

Natural $\Pi_1$ sentence independent of PA

Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of ...
2
votes
0answers
89 views

Definability in countable nonstandard models of Peano arithmetic

I know that every element of $\mathbb{N}$ is definable the standard model of Peano Arithmetic. Does there exist a countable non-standard model of PA where the same is true?
10
votes
2answers
676 views

Could Kronecker accept a proof of Goodstein's theorem?

A famous result of Goodstein asserts that the Goodstein sequence of integers terminates. For a precise statement and a short proof, see https://en.wikipedia.org/wiki/Goodstein%27s_theorem. A well ...
6
votes
2answers
330 views

Interpreting proper elementarily equivalent end extensions?

Is there a tuple of parameter-free formulas $\Phi$ and a nonstandard $M\models PA$ such that $\Phi^M\models PA$, the induced $M$-definable initial segment embedding $j_\Phi^M:M\rightarrow\Phi^M$ is ...
1
vote
2answers
210 views

The “higher topology” of countable Scott sets

Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
3
votes
0answers
180 views

What does second order set theory give us that is new?

There is a natural analogy between the theories PA and ZFC. See the linked question by Gro-Tsen here. Peano arithmetic (PA) is a first order approximation to the natural numbers. As is well known, ...
8
votes
1answer
487 views

Gentzen's result on PA

The Wikipedia states that Gentzen proved that "in modern terms, the proof-theoretic ordinal of PA is $\varepsilon_0$." Further down, the article defines what the "proof theoretic ordinal" of a theory ...
6
votes
0answers
209 views

What is proof-theoretic ordinal of weak first-order arithmetic?

According to Wikipedia(https://en.wikipedia.org/wiki/Ordinal_analysis) and nlab(https://ncatlab.org/nlab/show/ordinal+analysis), a proof-theoretic ordinal of $\mathsf{PRA}$ is $\omega^\omega$. ...
3
votes
1answer
132 views

Models of arithmetical theory R + induction in which successor is not injective

Consider the arithmetical theory sometimes denoted by $\mathsf{R}$. The non-logical vocabulary of $\mathsf{R}$ consists of '$0$', '$S$', '$+$' and '$\times$'. The axioms of this theory are all true ...
1
vote
1answer
182 views

Interpreting PA2 in second-order logic + existence of infinitely many objects

I've heard that if you assume the existence of (Dedekind) infinitely many objects, you can derive -- in second-order logic, given suitable definitions -- the (second-order) Peano axioms for arithmetic....
1
vote
3answers
745 views

Regarding Gentzen's note regarding 'Godel-points' (i.e., “Where is the Godel-point hiding?”)

Consider the following note written by Gerhard Gentzen in early 1932, on the onset of his work on a consistency proof for arithmetic: The axioms of arithmetic are obviously correct, and the ...
2
votes
1answer
147 views

Is second-order logic *with standard semantics* necessary to categorically characterise the natural number structure?

Is second-order logic with standard semantics necessary to categorically characterise the natural number structure? One can prove that any two models of Dedekind-Peano arithmetic are isomorphic (...
1
vote
0answers
93 views

Induction on open formulas vs. Induction on $\Pi_1$ formulas

There are infinitely many extension to Robinson's $Q$ arithmetic many of which are defined by adding an axiom schema of induction for particular set of formulas. I am confused about the theory $\text{...
1
vote
1answer
304 views

What does “can almost be proven in PA” mean regarding Theorem 2 of Timothy Chow's expository article, “The Consistency of Arithmetic”?

In his expository article, "The Consistency of Arithmetic" (MSN), Prof. Chow has the following theorems: Theorem 1. If $a_1, a_2, a_3,\dotsc$ is a sequence of ordinals and $a_i \ge a_j$ whenever $...
3
votes
1answer
217 views

Is cyclic PA interpretable in PA?

If we remove the axiom that zero doesn't have a predecessor, and stipulate that every natural number has a predecessor, and that no number is the successor of itself. And keep all other axioms of $\...
0
votes
0answers
61 views

Multivariate polynomial with infinite but discrete roots on one variable

I want to know if there exists a polynomial $ P(z, x_1,x_2,\ldots,x_n)$ over the rationals such that the set $$ Z_P = \{z | \exists x_1,\ldots,x_n. P(z, x_1,x_2,\ldots,x_n) = 0 \} \subsetneq \mathbb Q ...
21
votes
9answers
3k views

Defining the standard model of PA so that a space alien could understand

First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
13
votes
1answer
1k views

Existence of a model of ZFC in which the natural numbers are really the natural numbers

I know that, from compactness theorem, one can prove that there are models of first order arithmetic in which there is some "number" which is not a successor of zero, in the sense that it is strictly ...
7
votes
2answers
212 views

Measure of the numbers with length of $n$ for a nonstandard number $n$

Is there any nonstandard model of $PA$ with the following properties? There exists a nonstandard number $n\in M$ such that $M\upharpoonright n$ is countable, Let $|x|=\lceil\log_2x\rceil$, ...
10
votes
0answers
428 views

Reverse Mathematics of Euclid's theorem

Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that ...
10
votes
1answer
384 views

Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...
17
votes
1answer
431 views

What non-standard model of arithmetic does Hofstadter reference in GEB?

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
2
votes
0answers
71 views

What is the relation of total functions in second order arithmetic and fast growing hierarchies?

Answer to this questions shows that fast growing hierarchies can grow arbitrarily fast for some definition of 'arbitrary'. Can second order arithmetic define all these functions (for any ordinal) ...
2
votes
0answers
124 views

Is the quantifier-free fragment of Robinson arithmetic essentially undecidable?

It is well known that Robinson arithmetic (Q) is undecidable, and in fact essentially undecidable. Matiyasevich's theorem implies that the quantifier-free fragment of Q is also undecidable. However, I'...
6
votes
1answer
415 views

Can an uncountable model of Peano Arithmetic be recursive?

Can an uncountable model of Peano Arithmetic be recursive? What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
6
votes
1answer
422 views

What is the consistency strength of this theory?

Language: first-order logic Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation). Axioms: those of identity ...
11
votes
2answers
303 views

Are all generalized Scott sets realized as generalized standard systems?

Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so. The standard system of a nonstandard ...
7
votes
2answers
182 views

On models of $Th_{\Pi_2}(PA)$

Let $M$ be a nonstandard model of $PA$. Q1. Is there any way to get a submodel $N\subset M$ such that $N\models Th_{\Pi_2}(PA)$, but $N\not\models PA$? Q2. Especially, what combinatorial ...
1
vote
0answers
285 views

approaching the border between absolute convergence and divergence of series

Let us consider absolute convergent series $\ell^{1^+}$ ordered under eventual dominance (mod finite) $<^*$. T. Bartoszynski proved that unbounded number ${\frak b}(\ell^{1^+}, <^*)$ equals ...
3
votes
0answers
99 views

A conservativity result of intuitionistic set theory over arithmetic

In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...
1
vote
0answers
175 views

Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?

Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...
8
votes
1answer
224 views

Analog of Tennenbaum's theorem for EFA

EFA can prove the exponential function to be total, but it cannot prove the superexponential function to be total. Is there an analog of Tennenbaum's theorem (which states the PA has no recursive non-...
3
votes
1answer
87 views

If one adds an inductive subset to a model of $ACA_0$, do we always get a new model of $ACA_0$?

Suppose $(M, \mathcal X) \models ACA_0$. Recall that a subset $A \subseteq M$ is $inductive$ over $M$ if $M$ satisfies all instances of induction in the expanded language with a predicate for $A$. ...
7
votes
2answers
483 views

Is every true statement independent of $PA$ equivalent to some consistency statement?

Most true statements independent of PA that I know of is equivalent to some consistency statement. For example Con(PA), Con(PA + Con(PA)), Con(PA + Con(PA) + Con (PA + Con(PA)), $\dots$ Goodstein's ...
12
votes
1answer
1k views

What is known about the relationship between Fermat's last theorem and Peano Arithmetic?

As far as I know, whether Fermat's Last Theorem is provable in Peano Arithmetic is an open problem. What is known about this problem? In particular, what is known about the arithmetic systems $PA + \...
7
votes
1answer
208 views

Independent/Easy fraction of sentences over PA

Let $S(n)$ be the set of all sentences over PA of length at most $n$ (counting the quantifier symbols, boolean connectives, arithmetic operations and constants, and counting each variable as length $1$...
8
votes
0answers
251 views

What arithmetic is interpretable in Mayberry's Euclidean set theory?

John Mayberry published what he calls a Euclidean set theory in his book The Foundations of Mathematics in the Theory of Sets. It is ZF with the axiom of infinity replaced by an axiom saying "the ...
6
votes
1answer
374 views

Is ZFC+(negation of a large cardinal axiom) arithmetically sound?

My knowledge in set theory is very limited, so I apologize if this question is naive or trivial: Let $A$ to be a large cardinal axiom. $T=ZFC+\neg A$ is a consistent theory. My question is: Question ...
1
vote
2answers
669 views

Can you remove all the extra arithmetic from ZFC (or other theories)?

Let $\mathbb{N}$ be the standard model of the natural numbers. For any statement in the language of arithmetic, we can translate into a statement in the language of set theory by asking if it is true ...
7
votes
2answers
525 views

On a theorem of Zhang Jinwen about models of arithmetic

In the paper ''A Nonstandard Model of Arithmetic Constructed by means of Forcing Method'', Zhang Jinwen states the following in his abstract: The first nonstandard model of arithmetic was given by ...
6
votes
1answer
156 views

Logical complexity of hard functions conjectures

Let $\phi_1$ and $\phi_2$ be the following statements: $\phi_1:$ There is a function $f:\{0,1\}^*\to\{0,1\}$ computable in $E$ that has circuit complexity $2^{\Omega(n)}$. $\phi_2:$ There is a ...
11
votes
2answers
1k views

Trouble with models of PA and ZFC

I have a big trouble in my mind, here is my false reasoning: The Goodstein's theorem is undecidable in (first order) Peano Arithmetic. There exist a non standard model N of PA where the Goodstein's ...
5
votes
1answer
146 views

Can extensions of $Q$ contradict Löb with recursive reflection?

It is an odd and arguably unacceptable situation that $PA$ does not have $\vdash_{PA}(Pr_{PA}\ulcorner A\urcorner\to A)$ for false recursive sentences $A$. However, it is not clear to me that Löb'...
2
votes
1answer
104 views

Does $WKL_0$ plus CON(PA+X) give a binary tree model of PA+X?

In the context of reverse mathematics $WKL_0$ is considered equivalent to Gödel's completeness theorem over $RCA_0$. Does this mean that e.g. $WKL_0$ plus the consistency statement CON(PA+X) gives a ...
1
vote
0answers
106 views

How do I justify these nontheorems in the absence of the Existence Property for $PA$

Let $\Pi$ be the provability predicate for $PA$. I want to conclude that $PA\nvdash\exists x(\alpha(x)\wedge\lnot\Pi\ulcorner \alpha(\overset{.}{x}) \urcorner)$ and $PA\nvdash\exists x(\lnot \alpha(x)\...
2
votes
1answer
156 views

How does the existence property fail in $PA$?

Who or what is a good reference that explains how the (numerical) existence property fails for $PA$? Alternatively, what is a good example? It e.g. is clear that the disjunction property must fail ...
6
votes
2answers
552 views

Are omega-consistent extensions of PA always consistent with each other?

The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just: ...
4
votes
0answers
247 views

the strength of saying “each sentence of true arithmetic has a recursive proof”

Let $PA_{\omega}$ be just like $PA$ except that $PA_{\omega}$-proofs can use any number of applications of the recursive $\omega$-rule. The recursive $\omega$-rule allows the following: For each ...