All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
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
1
vote
1
answer
629
views
In what sense is the "descending chain principle" for ordinals less than $\epsilon_0$ 'infinitary?
In the introduction to his paper "Assignment of Ordinals to Terms for Primitive Recursive Functionals of Finite Type", W.A. Howard writes:
Gentzen...showed that the consistency of first order (...
- 6,132
8
votes
0
answers
1k
views
What's Reeb's take on naive integers?
Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
- 16.6k
13
votes
3
answers
1k
views
Reducing ACA₀ proof to First Order PA
According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA.
http://en.wikipedia.org/wiki/Reverse_Mathematics
First of all I have a few questions about the proof:
a - What ...
- 1,659
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
3
votes
0
answers
144
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 ...
- 355
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
1
vote
1
answer
311
views
Forcing the consistency of $ZF$ from a fragment of $ZF$
Implicit in the technique of forcing is the following relative consistency result:
If $\mathfrak M$$\vDash$$T$, and therefore $T$ is consistent (where $\mathfrak M$ is the ground model) then if $\...
- 6,132
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
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,829
3
votes
1
answer
404
views
Simplest PA theorem whose proof requires encoding of sequences even though the statement itself doesn't
What is the simplest number-theoretic theorem whose proof requires exponentiation or finite sequences/sets (so any proof in Peano Arithmetic would need to use encodings of such things using e.g. Gödel'...
- 1,174
27
votes
1
answer
678
views
Decidability of equality of expressions built using 1,+,-,*,/,^
Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
- 371
25
votes
3
answers
3k
views
Composite pairs of the form n!-1 and n!+1
It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$.
Is ...
- 44.4k
3
votes
0
answers
85
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) ...
- 225
4
votes
0
answers
292
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 ...
- 449
2
votes
2
answers
1k
views
Are there non-commutative models of arithmetic which have a prime number structure?
Peano Arithmetic (PA) models have a prime number structure and commutativity of addition and multiplication. Presburger arithmetic (PrA) models of arithmetic have addition without multiplication and ...
user10290
1
vote
1
answer
238
views
Elementary functions in a formalized PA
I'm having trouble understanding some parts of the paper "Provably computable functions and the fast growing hierarchy" by Buchholz and Wainer (1987).
On page 183 they say that their system has ...
- 1,174
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
1
vote
1
answer
186
views
What is difference between length of proof and length of its presentation in Peano Arithmetic?
In this paper http://www.sciencedirect.com/science/article/pii/0304397584901117 page $19$ or $29$ it seems to imply there is a difference between length of proof and length of its presentation in ...
- 13.9k
6
votes
2
answers
929
views
First-order vs second-order provability
Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except ∀x(Sx≠0) is replaced with ∃x(Sx=0). Let MA2 be the second-order variation, with second-order induction.
...
- 1,974
2
votes
1
answer
247
views
How can two theories $T$ and $T+\phi$ be mutually interpretable?
Following Koellner in http://plato.stanford.edu/entries/independence-large-cardinals/, "a theory $T_1$ is interpretable in $T_2$ ($T_1 \leq T_2$) when, roughly speaking, there is a translation $\tau$ ...
- 23
5
votes
2
answers
983
views
finite or infinite many quadratic fields embedding into quaternion algebras?
Suppose $H$ is a indefinite quaternion algebra over $\mathbb{Q}$. Are there infinitely many quadratic fields that can be embedded into $H$?
- 709
3
votes
3
answers
2k
views
"Interesting" properties of sets of natural numbers
On Wikipedia, there is a list of properties of sets of reals, which are in some sense "interesting": just have a look.
I could not find a comparable list of properties of sets of natural numbers (...
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 ...
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
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 ...
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
12
votes
1
answer
1k
views
Is an ultrafinitist Hilbert's program doomed?
Hilbert's program is popularly understood as an attempt to justify infinitary mathematics with a finitary consistency proof. Godel's Second Theorem is usually considered as showing this is not ...
- 1,974
7
votes
4
answers
912
views
Reference Request: Non-Standard Models of PA
I am attempting to write an expository paper on non-standard models of PA that is accesible to students taking an introductory graduate course in mathematical logic (covering Godel's incompleteness ...
- 1,441
1
vote
0
answers
113
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)\...
- 3,574
10
votes
0
answers
161
views
Minkowski's lattice theorem in fragments of arithmetic
It is widely remarked that Minkowski's lattice theorem (or, convex body theorem) is a kind of geometrical pigeonhole principle. And it seems it should have a very elementary proof at least for convex ...
- 11.2k
9
votes
1
answer
898
views
Does higher order arithmetic interpret the axiom of choice?
By second order arithmetic I mean the axiomatic theory $Z_2$, that is Peano arithmetic extended by second order variables with the full comprehension axiom, and not defined semantically using power ...
- 11.2k
5
votes
0
answers
287
views
Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?
Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).
7
votes
1
answer
701
views
Has Ribet's theorem been proved using only finite powers of primes?
Ribet proved the Serre epsilon conjecture using $p$-adic Galois representations (http://math.berkeley.edu/~ribet/Articles/invent_100.pdf). Can someone show how to replace all use of $p$-adics in ...
- 11.2k
4
votes
2
answers
743
views
NNO = (first order) PA
Recall the definition of a Natural Numbers Object in a topos, and the first order axioms for Peano Arithmetic. I am more familiar with the first definition than the second, so I cannot tell from the (...
- 35.5k
4
votes
0
answers
219
views
Construction of model of arithmetic from an arbitrary model
Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that:
$M'\models PA^-$ (or $...
- 1,689
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
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
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,730
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
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.2k
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
3
votes
2
answers
353
views
Reference request: Minimal Axiomatizations of PA over (+,x,<=).
Many years ago, when I was still a high school student, I came up with a certain first-order axiomatization of PA over the signature (+, x, ≤). Out of nostalgia, I've decided to clean up what I ...
- 573
0
votes
2
answers
2k
views
Gödel, Escher, Bach: b is a power of 10. [closed]
I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
- 9
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 ...
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,730
3
votes
0
answers
198
views
What is the known weakest axiom system has Löb's derivability conditions?
We know that Peano Arithmetic satisfies Löb's derivability conditions, which is required in the proof of Gödel's 2nd incompleteness theorem. Is this the best result? If not, is there any known weaker ...
- 779
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
8
votes
2
answers
1k
views
Weakest subsystems of second order arithmetic for mathematical logic
It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it?
What about the incompleteness theorems? Is ...
- 1,465
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