All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
10
votes
2
answers
2k
views
The different Branches of Arithmetic
... "and then the
different branches of Arithmetic--
Ambition, Distraction, Uglification,
and Derision."
(Alice in Wonderland, chapter IX: the Mock Turtle's story)
As a child I wondered for ...
- 60.6k
1
vote
1
answer
271
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....
3
votes
1
answer
171
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 ...
6
votes
3
answers
1k
views
Set theory inside arithmetics via the Ackermann yoga
Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of ZF-Infinity in PA (see for refs this MO question and here for an excellent ...
- 7,853
4
votes
3
answers
360
views
End Extension models of $I\Delta_0$
Recently I'm thinking about question below, but I can not prove or disprove it.
Is it true that for every model $M\models I\Delta_0$ there exists a
model $M'\models PA$ such that $M'$ is end ...
- 1,689
9
votes
1
answer
874
views
Is there any set theory $T$ such that $T$ plus true arithmetic is complete with respect to statements in set theory?
Is there an effective set theory $T$ such that $T + $$TA$ is consistient and complete. It should at least prove all theorems of $ZF$ true, so that it is a "standard" set theory. In particular, the ...
- 6,403
14
votes
0
answers
654
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 ...
- 35.5k
11
votes
1
answer
2k
views
Uncountable nonstandard models of PA
Standard techniques (no pun intended) can be used to show that countable nonstandard models of Peano Arithmetic are order isomorphic to $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$. Once we have used ...
- 2,762
6
votes
0
answers
113
views
When can two elementary end extensions of models of PA be uniquely amalgamated?
$\DeclareMathOperator{Cod}{Cod}$
$\DeclareMathOperator{Scl}{Scl}$
$\DeclareMathOperator{Def}{Def}$
$\DeclareMathOperator{Lt}{Lt}$
Background:
All of the background to this question can be found in ...
18
votes
3
answers
2k
views
Is Robinson Arithmetic biinterpretable with some theory in LST?
Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
- 3,267
7
votes
1
answer
597
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,403
12
votes
1
answer
1k
views
How to locate the paper that established Robinson Arithmetic?
If I'm not mistaken, it was in his seminal paper “An Essentially Undecidable Axiom System”, published in
Proceedings of the International Congress of Mathematicians (1950), 1952:729–730,
where R.M. ...
- 2,992
9
votes
4
answers
3k
views
Incompleteness and nonstandard models of arithmetic
The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.
Reading Peter Smith's "Gödel Without (Too Many) Tears",...
- 1,465
8
votes
1
answer
545
views
How arithmetical is algebraic exponentiation?
Suppose $K$ is an exponential real closed field, i.e. there is an isomorphism, say exp, between the additive group of $K$ and the multiplicative group of its positive elements.
Assume further that $Z$ ...
- 521
10
votes
3
answers
618
views
If an oracle Turing machine halts with every infinite arithmetic oracle, can it fail to halt with some non-arithmetic oracle?
Let $e$ be an index of an oracle Turing machine program and $k$ be some natural number. Let us say that a subset of $\mathbb N$ is arithmetic if it is definable in the model $\langle \mathbb N,+,\cdot,...
- 2,240
1
vote
0
answers
194
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{...
- 173
9
votes
2
answers
1k
views
divisible by all standard prime numbers
This question is about prime numbers in nonstandard models of Peano Arithmetic. Every such model looks like N+AxZ, where A is a dense linear order without end points.
There are many nonstandard ...
7
votes
1
answer
414
views
Is there an $E_1$-definition of primality?
Here, $E_1$ denotes the set of arithmetic formulas starting with a bounded existential quantifier, followed by a quantifier-free formula. Is there an $E_1$-formula $\phi$ such that $\phi(n)$ holds
iff ...
- 521
25
votes
2
answers
3k
views
Is there a known natural model of Peano Arithmetic where Goodstein's theorem fails?
(I've previously asked this question on the sister site here, but got no responses).
Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It turns out that this ...
- 6,556
11
votes
1
answer
1k
views
The (un)decidability of Robinson-Arithmetic-without-Multiplication?
I asked this over at math.stackexchange, and though a number of people were interested enough to vote up the question, I didn't get an answer -- which makes me wonder whether it isn't quite so trivial/...
- 1,599
6
votes
3
answers
1k
views
Provability in Second-Order Arithmetic without the Successor Axiom
Consider second-order Peano Arithmetic Z2, i.e. the two-sorted first-order theory with induction and comprehension. Remove the assumption about the totality of the successor relationship (the ...
- 1,974
4
votes
1
answer
480
views
$f_{\epsilon_0}$ and provably total functions in $PA$
A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that
$f(x)=y \iff PA\vdash \phi(x,y)$ and
$PA\vdash \forall x \exists y \phi(x,y)$
I know (not in ...
- 2,619
9
votes
1
answer
927
views
Application of the Riemann hypothesis and the ABC conjecture to independence results
In Old Home Page of Andreas Weiermann Andreas Weiermann has stated the following:
Quite recently I submitted a preprint about an application of the Riemann hypothesis and the ABC conjecture to ...
- 32.2k
9
votes
1
answer
580
views
Interpreting Robinson arithmetic in a very weak set theory
It is known that adjunctive set theory interprets Robinson arithmetic, and that extensionality is not needed for that. (Montagna and Mancini, "A minimal predicative set theory", Notre Dame Journal of ...
1
vote
0
answers
346
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 ...
- 88
0
votes
0
answers
104
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
...
- 163
7
votes
1
answer
246
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$...
- 2,912
8
votes
3
answers
2k
views
Does the Feferman-Schutte analysis give a precise characterization of Predicative Second-Order Arithmetic?
A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
- 4,597
5
votes
1
answer
195
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'...
- 3,574
9
votes
1
answer
1k
views
ERA, PRA, PA, transfinite induction and equivalences
I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist.
For instance I'm ...
2
votes
1
answer
225
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 ...
- 3,574
3
votes
0
answers
324
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
1
answer
172
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 ...
- 1,689
3
votes
1
answer
120
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$. ...
- 1,882
6
votes
1
answer
383
views
Formal systems needed to formalize relative independence results
We know that Con(ZF) implies Con(ZFC+GCH), Con(ZF+neg(AC)) and Con(ZFC+neg(CH)). But what are some weak theories in which these relative independence results are provable? In particular, are they ...
- 4,985
1
vote
3
answers
3k
views
Why Does Induction Prove Multiplication is Commutative?
Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom:
$$\forall x \forall y \forall z\bigr((Sx=...
- 687
10
votes
4
answers
5k
views
Historically first uses of mathematical induction
I'm interested in find out what were some of the first uses of mathematical induction in the literature.
I am aware that in order to define addition and multiplication axiomatically, mathematical ...
user2529
1
vote
0
answers
205
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 { ...
- 6,403
4
votes
1
answer
876
views
Derivability conditions for Robinson arithmetic
Two pieces of hearsay I have encountered about Robinson's Q:
Q fails to satisfy the Löb derivability conditions;
Pudlák criticised the Löb derivability conditions and suggested rival, weaker ...
- 2,283
10
votes
2
answers
1k
views
A question about open induction
An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
- 6,219
6
votes
1
answer
209
views
Is $PRA$ + $TI({\epsilon_0})$ mutually interpretable with some theory in the language of set theory?
As is well known, the following theory is equiconsistent with $PA$:
$ZFC$ with the axiom of infinity replaced by its negation.
Since this theory is equiconsistent with $PA$, it would seem ...
- 6,132
1
vote
2
answers
793
views
An interpretation of not-Con(PA)
Edit After Andreas Blass answer below and comments below the original post I have changed it to accommodate posters' remarks. I hope it is clear and makes more sense now.
Let $\mathrm{PA}$ be the ...
- 1,112
6
votes
1
answer
988
views
Nonstandard models of PA of large cardinal size
It is easy to overlook the fact that the existence of a given large cardinal provides us with a true arithmetical statement that would otherwise be false if the large cardinal notion were not ...
- 2,762
4
votes
1
answer
500
views
Does PA+Con(PA) entail the existence of non-standard models of PA?
Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$?
Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ ...
- 125
0
votes
1
answer
495
views
Infinite board games: sentences about
As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...
- 851
2
votes
3
answers
852
views
Can a Decidable Theory Have Non-recursive Models?
Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.
...
- 687
12
votes
1
answer
976
views
What metatheory proves $\mathsf{ACA}_0$ conservative over PA?
Simpson's book shows $\mathsf{ACA}_0$ is conservative over $\mathsf{PA}$ in the natural way by model theory using definable subsets. Of course, $\mathsf{ACA}_0$ being conservative over PA is ...
- 11.2k
8
votes
0
answers
345
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 ...
- 11.2k
3
votes
3
answers
314
views
Semantic reflection
Let $\ulcorner \cdot \urcorner$ be a fixed encoding of formulas by numbers, e.g.
let $\ulcorner \varphi \urcorner$ denote the Godel number of $\varphi$.
Let $T$ be a first-order arithmetic theory, e....
- 5,502
12
votes
2
answers
973
views
Z_2 versus second-order PA
These days, Peano Arithmetic ($PA$) refers to the first-order version of the axioms, where induction is only over formulas referring to natural number variables. Peano's original version of the ...
- 35.5k