All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
68 questions
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 + \...
68
votes
4
answers
12k
views
Nelson's program to show inconsistency of ZF
At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say:
Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel ...
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 ...
34
votes
8
answers
8k
views
Arithmetic fixed point theorem
I want to understand the idea of the proof of the artihmetic fixed point theorem. The theorem is crucial in the proof of Gödel's first Incompletness theorem.
First some notation: We work in NT, the ...
12
votes
4
answers
1k
views
Is this theory synonymous with PA?
Language: Mono-sorted first order logic with equality.
Extralogical Primitives: <,∈
Define: x≤y⟺x<y∨x=y
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
42
votes
7
answers
3k
views
How would one even begin to try to prove that a simple number-theoretic statement is undecidable?
This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other ...
39
votes
3
answers
3k
views
Why do stacked quantifiers in PA correspond to ordinals up to ϵ0?
I am trying to understand why induction up to exactly ϵ0 is necessary to prove the cut-elimination theorem for first-order Peano Arithmetic; or, as I understand, equivalently, why the length ...
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 (...
30
votes
2
answers
3k
views
Even XOR Odd Infinities?
Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except ∀x(Sx≠0) is replaced with ∃x(Sx=0).
(http://en.wikipedia.org/wiki/Peano_axioms#First-...
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. ...
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 ...
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 ...
15
votes
5
answers
2k
views
In what sense does the sentence con(PA) "say" that PA is consistent?
It seems common amongst logicians to think of "truth" as being relative to a particular structure. Consider, for instance, the first-order theory of groups. The sentence $\forall x\forall y(...
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 ...
12
votes
1
answer
976
views
What metatheory proves ACA0 conservative over PA?
Simpson's book shows ACA0 is conservative over PA in the natural way by model theory using definable subsets. Of course, ACA0 being conservative over PA is ...
10
votes
2
answers
1k
views
A question about open induction
An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring R can be extended to a model of open induction ...
43
votes
1
answer
3k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of ZFC/set theory and PA(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
33
votes
2
answers
3k
views
Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?
There are many interpretations of arithmetic in set theory. The
Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor:
0={ }
1={0}
...
29
votes
10
answers
4k
views
Defining the standard model of PA so that a space alien could understand
First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
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 ...
12
votes
2
answers
868
views
The inconsistency of Graham Arithmetics plus ∀n,n<g64
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 ...
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 ...
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,...
7
votes
1
answer
414
views
Is there an E1-definition of primality?
Here, E1 denotes the set of arithmetic formulas starting with a bounded existential quantifier, followed by a quantifier-free formula. Is there an E1-formula ϕ such that ϕ(n) holds
iff ...
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: <,∈.
Define: x≤y⟺x<y∨x=y
Axioms:
$\textbf{Well ordering: }\\\...
-1
votes
3
answers
1k
views
Naturally definable sets of natural numbers
(This is a follow-up question from over there: Natural models of graphs.)
(And it has a follow-up question over there: Naturally definable sets of natural numbers (2): Can the circle be broken?)
...
-2
votes
1
answer
369
views
Is this extension of the projectively extended real line, consistent?
This posting has been Edited. The edited material shall be noted.
The projectively extended real line ˆR=R∪{∞} is one system which allows division by zero! Yet it ...
32
votes
2
answers
3k
views
Do we expect that sufficiently large computable ordinals settle every question of arithmetic?
I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
27
votes
5
answers
4k
views
What is induction up to ε0?
This is a question asked out of curiosity, and because I can't understand the Wikipedia page.
I have often been told that PA cannot prove the validity of induction up to ε0, which has ...
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 ...
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,...
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 ...
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
17
votes
3
answers
3k
views
Gödel's Incompleteness Theorem and the complexity of arithmetic
In How complicated can structures be? Jouko Väänänen says:
The guiding result of mathematical logic is the Incompleteness Theorem of Gödel,
which says that the logical structure of number theory ...
16
votes
2
answers
1k
views
How special is first-order PA?
This is a modified version of a question which was asked and bountied at MSE without success.
Below, "PA" refers to first-order Peano arithmetic.
There are various "...
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 ...
12
votes
1
answer
482
views
Is there a useful measure of density of decidable sentences in PA?
Essential undecidability of PA says every complete extension of PA includes a non r.e. set of new "axioms," all undecidable in PA. In that sense lots of sentences of PA are undecidable in ...
12
votes
1
answer
835
views
Transfinitely extending PA — can we get stronger than ZFC?
Let PA denote the theory of natural numbers with constants (0,1) and binary operators (+,×) based on the first-order predicate calculus with equality, having the following axioms, ...
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 ...
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/...
9
votes
4
answers
3k
views
Incompleteness and nonstandard models of arithmetic
The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.
Reading Peter Smith's "Gödel Without (Too Many) Tears",...
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 ...
8
votes
1
answer
574
views
Iterated Gentzen: or, a Sith objection to the proof of consistency of PA
Preamble: In the year … in a galaxy far far away, a nasty Sith named Darth Dubious (...
8
votes
2
answers
560
views
Models of PRA/EFA with induction on X but not ω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 (ω↑↑N)<ϵ0, that ...
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 N". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
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 ...
7
votes
1
answer
358
views
Proving short consistency: can we do better than brute force search?
This is a minor variation of a question originally asked on MSE by user779130 and bountied by me, without success. Throughout, "length" refers to the number of symbols, not lines, in a proof....
6
votes
1
answer
727
views
What is the consistency strength of this theory?
Language: first-order logic
Primitives: =,S,∈ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation).
Axioms: those of identity ...
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 ACA0 is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
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 ...