All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
5
votes
0
answers
58
views
Mathematical strength of the statement "Heyting Arithmetic admits Markov's rule"
Consider the following theorem about Heyting arithmetic (HA)
For every arithmetical formula $\phi$ whose only free variable is $n$, if $\text{HA} \vdash \forall n. \phi \lor \lnot \phi$ and $\text{HA}...
- 6,403
12
votes
0
answers
248
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 20.7k
-2
votes
1
answer
208
views
Can this theory interpret Peano arithmetic?
Logic: Bi-sorted first order logic with equality, first sort written in lower case range over natural numbers, the second sort written in upper case range over sets of naturals, "$=$" has no ...
- 426
5
votes
1
answer
371
views
Are PA and Counting Theory synonymous\bi-interpretable?
The following question is whether $\sf PA$ is synonymous or even bi-interpretable with a theory about counting objects in finite sets.
Counting Theory:
$\textbf{Logic:}$ Bi-sorted first order logic ...
- 11.3k
1
vote
0
answers
90
views
About synonymy relationships around these two theories?
The following question is about patterns of synonymy relationships around two theories, $T^+$ and $\sf PA$.
For purposes of self inclusiveness I'll re-iterate $T$ and its extensions.
$\textbf{Logic:}$ ...
- 11.3k
-4
votes
0
answers
135
views
Which arithmetic\set theory is synonymous with this theory?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
Define: $x > y \iff y < x$
Define: $x \leq y \iff x < y \lor x=y$
$ \textbf{...
- 11.3k
-4
votes
1
answer
173
views
To which arithmetic\set theory this theory is bi-interpretable?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
$ \textbf{Axioms:}$
$ \textbf{Order:} \ x < y < z \to x < z $
$ \textbf{...
- 11.3k
12
votes
4
answers
1k
views
Is this theory synonymous with PA?
Language: Mono-sorted first order logic with equality.
Extralogical Primitives: $<, \in$
Define: $x \leq y \iff x < y \lor x=y$
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
- 11.3k
18
votes
3
answers
1k
views
Computable nonstandard models for weak systems of arithmetic
By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of ...
- 16.6k
16
votes
2
answers
713
views
Is (Z,+,0,1,P2,P3) decidable?
Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable?
I know that adding just one of P2, P3 to Presburger keeps it decidable, ...
- 16.6k
7
votes
1
answer
334
views
Why include $0$ and $1$ in the signature of Presburger arithmetic?
I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational ...
- 16.6k
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
- 4,713
26
votes
3
answers
7k
views
Presburger Arithmetic
Presburger arithmetic apparently proves its own consistency. Does anyone have a reference to an exposition of this? It's not clear to me how to encode the statement "Presburger arithmetic is ...
- 35.5k
8
votes
2
answers
2k
views
Axiom to exclude nonstandard natural numbers
In Peano Arithmetic, the induction axiom states that there is no proper subset of the natural numbers that contains 0 and is closed under the successor function. This is intended to rule out the ...
- 16.6k
30
votes
2
answers
3k
views
Even XOR Odd Infinities?
Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$.
(http://en.wikipedia.org/wiki/Peano_axioms#First-...
- 6,377
19
votes
3
answers
2k
views
Is platonism regarding arithmetic consistent with the multiverse view in set theory?
A "truth" platonist for arithmetic believes, given a statement in the language of arithmetic, that the problem whether the statement is true has a definite answer.
Prof. Hamkins has argued for a ...
- 4,713
7
votes
1
answer
489
views
Is $ACA_0$ + 'True Arithmetic exists' interpretable in $ACA$?
Maybe someone here can help me with a question concerning second-order arithmetic. Consider the system $ACA_T := ACA_0 + \exists X \forall x (x \in X \leftrightarrow T(x))$, where $T(x)$ is a $\Pi_1^1$...
- 328
2
votes
0
answers
192
views
Can PA be acyclically complete?
Any formula $\phi$ in the first order language of arithmetic is to be called acyclic if and only if we can associate with it an acyclic undirected graph whose nodes are the variable symbols occurring ...
- 11.3k
6
votes
1
answer
197
views
Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic?
I am currently reading an article titled "Embedding and Coding Below a 1-Generic Degree" by Greenberg and Montalbán(link to a free source:https://pi.math.cornell.edu/~erlkonig/Papers/...
- 1,780
2
votes
0
answers
100
views
Realizing arithmetic hierarchy in algebraic number theory
Is it possible to realize arithmetic hierarchy in algebraic number theory?
For example, consider a $\Pi^0_4$ statement of the form $\forall x \exists y \forall z \exists w \phi(x,y,z,w)=0$ where $\phi$...
- 593
2
votes
1
answer
154
views
The Dirichlet principle and arithmetical induction
Let us consider the Dirichlet principle as follows: for all natural numbers $n > k > 0$, there is no injection from $\{0, \dots, n-1\}$ into $\{0, \dots, k-1\}$.
Is it true that in some non-...
- 236k
1
vote
1
answer
180
views
Natural functions outside $\sf PA$?
Can theories stronger than $\sf PA$ manage to define functions from the naturals to the naturals, that $\sf PA$ cannot? If so, what are examples of those functions?
- 11.3k
1
vote
1
answer
146
views
Can PA define functions related to higher theories?
Working in $\sf ZFC$ we can define a function $F$ from naturals to naturals such that $F(0) = \, ^\circ\ulcorner r({\sf Z}) \urcorner$, where $r({\sf Z})$ is the Rosser sentence of Zermelo set theory $...
- 11.3k
1
vote
2
answers
340
views
Heuristic interpretations of the PA-unprovability of Goodstein's Theorem
I've relatively recently learned about Goodstein's Theorem and its unprovability in Peano arithmetic (the Kirby-Paris Theorem). I do not have any real knowledge of formal logic; but I think I've seen ...
- 708
6
votes
1
answer
743
views
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
- 236k
13
votes
3
answers
1k
views
Which ordinals can be proof-theoretic ordinals of a reasonable theory?
When talking to a friend recently he asked a question - are there any reasonable first-order theories which have proof theoretic ordinal equal to small or large Veblen ordinal? I have then extended ...
- 2,031
5
votes
0
answers
109
views
Computational complexity of arithmetic sentences over classical theories
Below, I use the term "tracker" rather than "realizer" since I'm not requiring the relevant objects to be computable.
Define the relation "$f$ tracks $\varphi$" for $f:\...
- 20.7k
4
votes
1
answer
269
views
Does Peano's axioms prove $\alpha$-induction for primitive recursive sequences for every concrete $\alpha < \varepsilon_0$?
It is well-known that Peano's axioms (PA) cannot prove $\varepsilon_0$-induction for primitive recursive sequences (PRWO($\varepsilon_0$)), because PA + PRWO($\varepsilon_0$) proves the consistency of ...
- 3,042
4
votes
1
answer
193
views
Further research on relevant realizability etc
I just read Dunn's 1979 paper Relevant Robinson's Arithmetic, and the end especially caught my interest. Following the surprising role of constant functions in collapsing "relevant Q with zero&...
- 1,094
23
votes
1
answer
3k
views
What is known about the theory of natural numbers with only 0, successor and max?
Consider the first-order theory whose intended/standard model is the natural numbers $\mathbb{N}$, with constant $0\in \mathbb{N}$, with an injective successor operation $s$ such that $0$ is not a ...
- 236k
1
vote
0
answers
123
views
Is possibile to define transfinite sum and product recursively? [closed]
On mathstackexchange a few days ago I published the following question where I asked about "transfinite" sum and products but actually nobody answered or gave an opinion with a comment: thus ...
3
votes
1
answer
134
views
$\Pi^0_1$ sentences modulo "schematic entailment"
Let $\mathfrak{P}$ be the preorder of $\Delta^0_0$ (= only bounded quantifiers) formulas with one free variable in the language of arithmetic, under the relation $\alpha(x)\le\beta(x)$ iff there is a ...
- 20.7k
21
votes
2
answers
1k
views
Is factorial definable using a $\Delta_0$ formula?
The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?
- 4,713
4
votes
1
answer
155
views
Does this hierarchy of fragments of $I \Sigma_1$ collapse?
Does anyone know whether the following hierarchy of fragments of
$\mathrm{I} \Sigma_1$ (or rather
$\mathrm{I} \Pi_1$) collapses or not?
Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...
- 47.6k
7
votes
4
answers
574
views
A conservative extension of Peano Arithmetic
Ulrich Kohlenbach makes the following intriguing comment here:
"In the 70s S. Feferman introduced a mathematically strong system S=restricted(PA^omega)+QF-AC+mu for classical mathematics (and in ...
- 17.7k
4
votes
1
answer
515
views
Truth Values of Statements in non-standard models
Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
- 2,167
14
votes
1
answer
525
views
Is there a theory between HA and PA that doesn't have Markov's rule?
A theory $T$ admits Markov's rule when
For every formula $\phi(n)$, if $$T \vdash \forall n \in \mathbb N. \phi(n) \lor \lnot \phi(n)$$ and $$T \vdash \lnot \lnot \exists n \in \mathbb N. \phi(n)$$ ...
- 47.6k
5
votes
2
answers
433
views
Models of second-order arithmetic closed under relative constructibility
I know little to nothing about second-order arithmetic and its subsystems. However, I would like to understand when a model of (a subsystem of) second-order arithmetic ($\mathsf{Z}_2$) is downward ...
- 20.7k
32
votes
11
answers
11k
views
Is PA consistent? do we know it?
1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...
- 2,031
4
votes
1
answer
258
views
What is the theory of statements with a provably *bounded* realizer (according to PA)?
$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic.
We can summarize the results from Emil Jeřábek's answer as follows:
\begin{gather*}
T_1 = \{ ...
- 12.9k
-2
votes
1
answer
211
views
Would this alteration safeguard the resulting theory from inconsistency?
If we replace "Emergence" axiom in the theory $T$ presented at posting "What is the set theory synonymous with this order-set theory?" with the following axiom, call the resulting ...
- 11.3k
3
votes
1
answer
169
views
Would this alteration of $T$ affect its synonymy with PA?
If we replace the single axiom "Emergence" in the axiomatic system $T$ presented at posting [What is the set theory synonymous with this order-set theory], by the following schema. Would the ...
- 11.3k
1
vote
1
answer
313
views
What is the set theory synonymous with this order-set theory?
Let $ T$ be a theory written in Mono-sorted first order logic with equality, with extralogical primitives: $<, \in$.
Define: $x \leq y \iff x < y \lor x=y$
Axioms:
$\textbf{Well ordering: }\\\...
- 11.3k
4
votes
0
answers
162
views
Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?
(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
- 2,912
1
vote
1
answer
221
views
Seeking clarification of ultrapower nonstandard model of arithmetic
I've read that one nonstandard model of arithmetic is:
take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers
take a quotent that gives the ultrapower: identify ...
- 1,288
7
votes
1
answer
341
views
Can this weakish system of arithmetic express multiplication for second-sort numbers?
Consider a 2-sorted first-order logic with equality (for first-sort entities). The first sort consists of numbers, the second sort (which will be capitalized) of unary functions. There is one constant,...
- 1,974
2
votes
2
answers
281
views
Interpreting peano arithmetic without parameters
I will accept an answer in the form of references to the literature about my question as well as any other information. I am quite ignorant of the area and that will be clear from my question.
I ...
- 236k
-2
votes
1
answer
416
views
Defining the set of natural numbers in the first order Peano arithmetic [closed]
The question seems simple, but I'm not sure:
let's consider a first order Peano Arithmetic and its standard model $N = \{ 0,1,2,3,... \}$ of natural numbers.
A question: how can we define the whole ...
- 3,065
8
votes
3
answers
427
views
Uncountable model of bounded arithmetic with an elementary end extension
Theorem 1.53 (3) in page 227 of Hajek and Pudlak's book, Metamathematics of First-Order Arithmetic, says:
Theorem. If $M$ is a countable model of $I\Delta_{0}$ such that $M$ has a proper elementary ...
- 236k
3
votes
1
answer
123
views
Kleene normal form theorem for r.e. relations proven in arithmetical theories
After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
- 17.7k