All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
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 ...
- 47.8k
-1
votes
2
answers
638
views
Peano axioms— mathematical induction and other axioms
The Peano axioms of $\Bbb N$ are:
$1 \in \Bbb N$, i.e. $\Bbb N$ is not empty and contains an element denoted by $1$.
Every natural number has a successor, i.e. $\forall n\in\Bbb N, \exists!s(n)\in\...
- 63.9k
22
votes
5
answers
1k
views
What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?
I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic.
Definitions. ...
- 63.9k
7
votes
1
answer
572
views
Finding a PA cut in a nonstandard model of PA
For a certain project I am currently working on, I need to be able to find PA cuts in nonstandard models of PA, in desirable intervals. For example, I wonder if the following is true, where $\...
- 63.9k
8
votes
2
answers
428
views
Models of arithmetic in a signature with exponentiation but not addition and multiplication
Let $\mathcal{L}_{\mathrm{exp}}$ be the language with signature $(0, ^\prime, <, \mathrm{exp})$ (with $0$ interpreted as zero, $^\prime$ as successor, and $\mathrm{exp}(x)$ as $2^x$) and let $\...
- 63.9k
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 ...
- 63.9k
7
votes
0
answers
344
views
Nelson's contradiction in finitism
I have read up, in Shoenfield and elsewhere, on a lot of the details involved in Nelson's failed proof of the inconsistency of arithmetic. I understand the Kritchman-Raz proof; the proof of the ...
- 189
7
votes
2
answers
708
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 ...
- 63.9k
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 ...
- 63.9k
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 ...
- 63.9k
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 ...
- 63.9k
4
votes
0
answers
431
views
How can I prove that primitive recursion “preserves” representability in Peano Arithmetic?
I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.
By recursive function ...
- 49
3
votes
0
answers
191
views
Set theories that are complete modulo finite-order arithmetic
In a previous question, I asked whether there can be effectively axiomatizable set theories (at least as strong as, say, ZF) that are complete modulo first-order arithmetic, to which the answer is no; ...
- 675
3
votes
0
answers
172
views
Interpretability of primitive recursive functions in Peano Arithmetic
Let $R$ be a set of defining equations for primitive recursive functions successively built up from $s, +, \cdot$.
Is PA + $R$ interpretable in PA? (Interpretability understood in the sense of Tarski, ...
- 189
25
votes
4
answers
3k
views
What can be proven in Peano arithmetic but not Heyting arithmetic?
Hi. I'll confess from the start to not being a logician. In fact this question came up not from research but during a discussion with a friend about whether the classical proof that $\sqrt{2}$ is ...
- 63.9k
1
vote
0
answers
107
views
Formalization in PA in the Kritchman-Raz proof
In their paper Kritchman and Raz present a proof of Gödel's second theorem using Kolmogorov complexity. To make it work, they operate in some (weak) formal theory $T$ that incorporates some arithmetic,...
- 189
2
votes
0
answers
237
views
Representing iteration of a function in PA
Let $\mathscr{L}$ be a (recursive) FOL language, with numeral symbols $\underline{0},\underline{1},\ldots$. Let $T$ be a recursive, consistent theory, containing PA (or even just Robinson arithmetic)....
- 18.7k
10
votes
1
answer
414
views
Concrete examples of statements not provable in PRA + $\epsilon_0$-induction that are provable in PA?
It is well-known that $\mathbf{PRA}$ plus $\epsilon_0$-induction on bounded formulas cannot prove all $\mathbf{PA}$ theorems (essentially because $I\Sigma_1$ plus $\epsilon_0$-induction on bounded ...
- 47.8k
5
votes
3
answers
1k
views
Are there first-order statements that second order PA proves that first order PA does not?
Are there first-order statements that second order PA proves that first order PA does not? Is this known one way or the other? Could you share an example? (edit: to clarify, by 'second order PA' I don'...
- 82.7k
4
votes
0
answers
203
views
The Return of Graham Arithmetics: adding induction up to $g_{64}$
In my previous question The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$, I introduced an extension of Robinson Arithmetics with the recursive definition of Tetraction, a small ...
- 7,853
12
votes
2
answers
868
views
The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$
As you all know, Ronald Graham just passed away. He is famous for many fabulous contributions to finite combinatorics, and much much more, but perhaps none of them is as popular as the infamous ...
- 5,831
16
votes
2
answers
2k
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 ...
- 82.7k
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 ...
- 63.9k
7
votes
0
answers
179
views
The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory
Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...
- 7,853
10
votes
1
answer
807
views
Why can't we embed Tarski's truth in PA?
I recently learned that ZFC can prove $Con(PA)$ because it can give a model of PA, but I'm not given the technical details. (My teacher thinks it is too obvious to even mention.)
What plagues me is ...
- 73.2k
5
votes
1
answer
393
views
Lob theorem for Robinson arithmetic
If i'm not wrong, the theory which Lob theorem applies to should be sufficiently strong, satisfying 3 "derivability" conditions, like PA.
$Q$ is the Robinson arithmetic.
I'm afraid $Q$, is ...
- 47.8k
2
votes
2
answers
436
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 \...
54
votes
1
answer
3k
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 ...
- 841
8
votes
1
answer
491
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 ...
- 32.2k
1
vote
2
answers
267
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 ...
- 20.7k
3
votes
0
answers
301
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, ...
- 18.7k
17
votes
1
answer
2k
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 + \...
- 52.4k
9
votes
1
answer
644
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 ...
- 20.7k
6
votes
0
answers
422
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$.
...
- 1,452
0
votes
3
answers
1k
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 ...
- 6,132
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 ...
- 5,831
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....
- 5,831
2
votes
1
answer
366
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 (...
- 20.7k
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
1
vote
1
answer
466
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 $...
- 20.7k
3
votes
1
answer
233
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 $\...
- 11.3k
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
18
votes
1
answer
3k
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 ...
- 28.2k
21
votes
5
answers
2k
views
Alternative Arithmetics
Although, beyond any doubts, $ZFC$ is by and large the predominantly accepted theory of sets, there have been a few attempt to establish some serious competitors in town.
I just quote two of them (...
20
votes
3
answers
2k
views
Can FPA really prove its consistency?
I will ask the question first and then explain.
QUESTION: FPA can prove its own consistency in the Godelian sense. But can it really prove its consistency?
FPA is a multi-sorted first-order theory,...
- 1,974
7
votes
2
answers
241
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$, then $|\{...
CommunityBot
- 1
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 ...
CommunityBot
- 1
10
votes
1
answer
542
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 ...
- 1,228
19
votes
1
answer
748
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"...
- 24.8k
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 ...
- 4,727