All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
9
votes
2
answers
1k
views
Elementary end extensions of models of Peano Arithmetic in uncountable languages
A well-known theorem of Mills asserts that there is a model of Peano Arithmetic $M$ in an uncountable language such that $M$ has no elementary end extension (e.e.e.). I ask whether every complete ...
- 1,403
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 ...
- 1,403
7
votes
1
answer
198
views
A well-behaved $A$ that is almost contained in every element of some filter for a countable arithmetically closed family $\mathfrak X$
The question has relevance for constructing Scott sets with certain extra desirable properties.
Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: ...
- 2,240
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
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
39
votes
3
answers
3k
views
Why do stacked quantifiers in PA correspond to ordinals up to $\epsilon_0$?
I am trying to understand why induction up to exactly $\epsilon_0$ is necessary to prove the cut-elimination theorem for first-order Peano Arithmetic; or, as I understand, equivalently, why the length ...
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
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
57
votes
2
answers
7k
views
What arithmetic information is contained in the algebraic K-theory of the integers
I'm always looking for applications of homotopy theory to other fields, mostly as a way to make my talks more interesting or to motivate the field to non-specialists. It seems like most talks about ...
- 30.3k
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
11
votes
1
answer
433
views
Does any lower bound on proofs of FLT improve Shepherdson 1965?
In 1965 Shepherdson proved that FLT is independent of the fragment of PA that uses only open induction and signature $0,S,+\times$. Indeed $2x+1\neq 2y$ is independent of that fragment. Schmerl ...
- 11.2k
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
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
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 ...
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
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
0
votes
0
answers
315
views
Definitions for Oddness
In the thread Even Xor Odd Infinities I defined odd models of Modular Arithmetic (MA) as models satisfying the axioms of MA and two first order statements. Even XOR Odd Infinities?
$O1) \forall x(x=0 ...
- 687
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
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
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
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
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-...
- 687
2
votes
0
answers
84
views
Seeking name for an order raising operator in Higher Order Arithmetic.
Any class $X$ of order $j$ in HOA is in bijection with the order $j+1$ class built up from singletons $\{x\}$ of natural numbers $x$ just the way that $X$ is built up from the numbers $x$. And of ...
- 11.2k
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
2
votes
0
answers
223
views
Is this fragment of arithmetic on $p^{-\infty} {\mathbb Z}$ decidable?
Let $p$ be a prime number. Consider the abelian group $p^{-\infty} {\mathbb Z} = \bigcup p^{-n} {\mathbb Z}$ consisting of rational numbers whose denominator is a power of $p$, under addition.
View $...
- 13.3k
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
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
3
votes
2
answers
624
views
Models of the natural numbers in ultrapowers in the universe.
Our question arises from wondering about the systems of natural numbers in models ZFC + Con(ZFC) and ZFC + $\neg$Con(ZFC). In thinking of the systems of natural numbers of these models, we came to ...
user10290
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 ...
- 295
3
votes
1
answer
405
views
Godel 's Ladder: Undecidable PI_N sentences for N =2, 3, ......
After Godel's groundbreaking results, a plethora of $\Pi_1^0$ undecidable arithmetical sentences have been found by many authors.
But what about $\Pi_n^0$ for $n=2,3,.....$ ?
There are, to my ...
- 7,853
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
3
answers
996
views
Applicability of Deduction theorem to Primitive recursive arithmetic [closed]
Hello. I already asked the question here. The main point is that I tried to prove in Primitive recursive arithmetic (PRA) the totality of the Ackerman function, and I found, that the single thing ...
- 15
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
5
votes
2
answers
2k
views
How many models of Peano arithmetic are isomorphic to the standard model and how many models of Peano arithmetic are non-standard?
I am currently writing a paper on non-standard models of Peano arithmetic and I am having trouble finding references or information that discuss the relative sizes of how many models of Peano ...
- 1,441
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
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 ...
- 2,151
12
votes
4
answers
931
views
Parameters in arithmetic induction axiom schemas
The induction schema of Peano Arithmetic is standardly given as the universal closure of $\phi(0)\land \forall x (\phi(x)\rightarrow \phi(x+1)) \rightarrow \forall x\phi(x)$. However, since the ...
- 313
2
votes
3
answers
552
views
Generalizations of PA and its standard and non-standard models
Consider Peano's axioms — in its first-order version and without addition and multiplication — with its single injective function $S$:
$(\forall x) \neg Sx = 0$
$\Big(\phi(0)\ \ \&\ \...
- 9,730
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. ...
- 237k
8
votes
1
answer
897
views
Nelson natural number objects in a topos (say)
Nelson's predicative arithmetic (survey article) is a very weak system of arithmetic extending Robinson's $Q$ (Wikipedia).
We can have natural number objects in a topos, or even a merely finitely ...
- 35.5k
4
votes
2
answers
924
views
Natural numbers of great kolmogorov complexity
Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...
- 7,853
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
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 (...
- 7,853
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 (...
3
votes
1
answer
437
views
Axiomatizations of complete theories
This question was motivated by this recent question by Ricky Demer.
In his paper $\Pi^0_1$ classes and Boolean combinations of recursively enumerable sets, Carl Jockusch showed that there is no ...
- 44.4k
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
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
694
views
Implication of Polignac's conjecture on prime distribution in models of PA
Polignac's conjecture (PC) is that there exists infinitely many pairs of consecutive prime numbers that are a distance $d$ apart for some natural number $d$. The twin prime conjecture is the ...
- 2,762
0
votes
2
answers
998
views
Is division considered the mathematical dual of multiplication? [closed]
I'm doing a bit of research for a tech presentation that touches on the subject of mathematical duality. (To be clear, my presentation is not on mathematics or duality, but mentions duality in passing....
- 121
3
votes
0
answers
343
views
example just slightly better than the greedy construction
Roth's theorem provides an estimate for the largest
size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial three-...
- 3,595