All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
3
votes
1
answer
181
views
Least ordinal not embedded in a total order
If $(E,<)$ is a linear order, let $s(E,<)$ denote the least ordinal which doesn't embed in $(E,<)$.
I am trying to prove the following:
If $(M,+,.,0,1)$ is a model of open induction, (or ...
- 2,519
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 ...
- 261
3
votes
0
answers
187
views
Reducing Consistency of $PA$ [closed]
By godel translation consistency of $PA$ is equivalent to consistency of $HA$.
I want to know any similar theorems for $PA$.
1.What is the minimal theory $T\subsetneq PA$ such that the proof of $PA\...
- 1,689
43
votes
1
answer
2k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
- 32.5k
8
votes
0
answers
198
views
Kripke models of $HA$
Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$.
What is the strongest theory of arithmetic like $T$ such that for
every kripke model $K\...
- 1,689
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
11
votes
2
answers
1k
views
Why is there a need for ordinal analysis?
Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...
- 139
4
votes
1
answer
347
views
Proving moduli of uniform continuity in RCA_0
Simpson's Subsystems of Second Order Arithmetic (pp. 134ff.) uses RCA$_0$ to prove various theorems of analysis for all continuous functions with a suitable modulus of uniform continuity. And he ...
- 11.1k
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
16
votes
1
answer
831
views
Can there be computable non-standard models of PA in a weaker sense?
By Tennenbaum's theorem, in the usual sense of computability for models,
neither addition nor multiplication can be computable in a countable non-standard model of PA.
Weak version:
Can addition or ...
user5810
2
votes
1
answer
185
views
What are the adequacy conditions for Rosser Provability?
Famously, Rosser introduced a provability predicate $\pi[A]$ that holds iff $\exists x(xP[A]\wedge\forall y(y\le x\to\lnot yP[\lnot A]))$.
Supposing $PA$ is consistent, what are the adequacy ...
- 3,574
4
votes
0
answers
126
views
Lascar strong types in fragments of arithmetic
Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.)
Definition Given a saturated model ${\cal M}$ ...
0
votes
1
answer
294
views
Non-standard naturals and goodstein sequences [closed]
By the Kirby–Paris theorem, Goodstein's theorem is independent of Peano arithmetic (PA). Therefore there are non-standard models in which every Goodstein sequence terminates. However, Tennenbaum's ...
- 19
4
votes
1
answer
245
views
Induction and nonstandard halting times of standard machines
For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: $$SH(\mathcal{N})=\{n\in\...
- 20.7k
3
votes
1
answer
265
views
PA proves that functions are total
Is there a total recursive function $f:N \to N$ such that for no $\Sigma_1$ formula $\phi(x,y)$ which defines it (i.e., defines its graph), is it true that PA proves that "$\phi$ defines a total ...
- 428
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 ...
4
votes
1
answer
499
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
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?
- 313
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$...
- 71
13
votes
2
answers
1k
views
nonstandard models and mathematical theorems
Is there a first order statement about the natural numbers (not nonstandard analysis) such that the truth of the statement is easier to see in a nonstandard model? In other words, do nonstandard ...
2
votes
1
answer
201
views
Total formulae in a theory equivalent to $\Delta_0$ formulae in the theory?
Let a formula $\phi$ of the language of first-order Peano arithmetic be total in a theory Th that extends PA iff, for any $k_1, \dots, k_n \in \omega$, Th $\vdash \phi(\bar k_1, \dots, \bar k_n)$ or ...
4
votes
1
answer
436
views
Adding consistency statements to Peano arithmetic allows more instances of transfinite induction?
Consider the hierarchy given by $\cal S_0 =$ first-order Peano arithmetic, $\cal S_{\alpha+1}=\cal S_{\alpha} + Con(S_\alpha)$ (a consistency statement for $\cal S_\alpha$), and if $\alpha$ is a limit ...
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
6
votes
1
answer
382
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
16
votes
1
answer
1k
views
Is there a nonstandard model of arithmetic having precisely one inductive truth predicate?
$\newcommand\Tr{\text{Tr}}$My question is whether there can be a nonstandard model of PA having a unique inductive truth predicate.
Background. If $\mathcal{N}=\langle N,+,\cdot,0,1,<\rangle$ is ...
- 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 ...
- 28.2k
9
votes
1
answer
1k
views
Does Nelson try to prove PA inconsistent directly?
Edward Nelson is known for his serious attempts to show that Peano axioms, and sometimes even weaker theories, are inconsistent. I wasn't able to find Nelson's papers anywhere, so I wanted to ask a ...
- 28.2k
14
votes
4
answers
1k
views
Boolean Valued Models of PA
O.K, a massively naive question. I've never really studied any non-standard models of PA before. I was just wondering if there's ever been any attempt to use the kind of Boolean valued model theory ...
- 631
1
vote
2
answers
790
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
4
votes
1
answer
366
views
"Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?" [Tarski]
In his paper "Restricted set-theoretical defintions in arithmetic" Raphael Robinson cites a problem posed by Tarski:
Is it possible to give a restricted set-theoretical
definition of addition of ...
- 9,720
0
votes
1
answer
336
views
Definability of arithmetic functions and relations
Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand (...
- 9,720
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
7
votes
1
answer
447
views
The definition of < in Robinson's Q
I recently had to explain how the basic axioms in Simpson's Subsystems of Second Order Arithmetic were interpretable in Robinson's Q. Most of the axioms are actually the same, except that Simpson ...
- 44.4k
10
votes
1
answer
761
views
Forcing, cuts, and Dedekind-finite cardinalities
Tl;dr version: there are two natural classes of cuts in the nonstandard model of arithmetic consisting of the Dedekind-finite sets (if, in fact, they constitute such a model); both these classes are ...
- 20.7k
12
votes
1
answer
835
views
Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?
Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
- 6,819
8
votes
2
answers
560
views
Models of PRA/EFA with induction on $X$ but not $\omega^X$
As I currently understand it, induction on formulas containing $N+1$ first-order quantifiers is required to prove the well-ordering of the ordinal $(\omega \uparrow\uparrow N) < \epsilon_0$, that ...
5
votes
2
answers
663
views
Overspill in models of arithmetic
Assume that $M$ is a non-standard model of complete arithmetic, i.e. of the theory $Th(\mathbb{N})$. Suppose that $R$ and $S$ are proper cuts of $M$. (With a cut, I mean a subset of the universe of $M$...
user49449
7
votes
1
answer
705
views
Does the totality of Ackermann's function prove the consistency of $\Sigma_1$-induction?
It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the ...
- 777
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, ...
- 428
1
vote
0
answers
222
views
First-order Peano Axioms and order-completeness of $\mathbb{N}$ [closed]
Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo.
Notation: We denote the system of first-order Peano Axioms (along with ...
- 596
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
4
votes
1
answer
1k
views
Transfinite induction vs induction in mathematics
What are the nontrivial theorems one can prove about natural numbers which need transfinite induction? By "need transfinite induction" I mean one can show that the statement is not provable in ...
2
votes
1
answer
347
views
Elementary proof of bounds on factor polynomials
The question Getting a bound on the coefficients of the factor polynomial got very nice answers on Gelfond's theorem. But for work on proof theory of arithmetic I want a proof in arithmetic. The ...
- 11.1k
3
votes
0
answers
343
views
Peano (Dedekind) categoricity
What is the smallest fragment of second order logic such that $Th(\mathbb{N})$ in that logic is categorical (only one model, namely natural numbers, up to isomorphism). For example, can we do this in ...
0
votes
1
answer
571
views
Recursive Non-standard Models of Modular Arithmetic? [closed]
Any algebraically closed field (ACF) is a model of Modular arithmetic (MA). (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)...
- 687
3
votes
2
answers
328
views
Efficient representations of natural numbers via arithmetical expressions
A given natural number $n \in \mathbb{N}$ has many representations
as expressions mixing other natural numbers and the operators and punctuation symbols
$\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...
- 151k
3
votes
3
answers
683
views
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
In models of PA with restricted induction power (for example, only $I\Sigma_n$ is present), the failure of higher induction scheme is characterised by the existence of definable cuts (like $\Sigma_2$ ...
- 3,038
4
votes
1
answer
376
views
Interpreting the Galois theory of finite extensions of $\mathbb{Q}$ in PA
Any finite extension of the rationals, along with its Galois group, can be interpreted in Peano arithmetic by straightforward means. For a fixed bound $n$ in the degree this is uniform in the ...
- 11.1k
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
3
votes
2
answers
993
views
Neither Even Nor Odd Natural Numbers
Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. In Even XOR Odd Infinities? I asked if this statement ...
- 687