Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 + \...
Christopher King's user avatar
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 ...
Andreas Thom's user avatar
  • 25.5k
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 ...
David White's user avatar
  • 30.3k
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 ...
Martin Brandenburg's user avatar
12 votes
4 answers
1k views

Is this theory synonymous with PA?

Language: Mono-sorted first order logic with equality. Extralogical Primitives: <, Define: xyx<yx=y $\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
Zuhair Al-Johar's user avatar
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 ...
gowers's user avatar
  • 29k
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 ...
Eliezer Yudkowsky's user avatar
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(Sx0) is replaced with x(Sx=0). (http://en.wikipedia.org/wiki/Peano_axioms#First-...
Russell Easterly's user avatar
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. ...
Joel David Hamkins's user avatar
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 ...
AEWARG's user avatar
  • 261
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 ...
Piotr Hajlasz's user avatar
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(...
Joe Lamond's user avatar
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 ...
Lucas K.'s user avatar
  • 1,659
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 ...
Colin McLarty's user avatar
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 ...
Sidney Raffer's user avatar
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 ...
Gro-Tsen's user avatar
  • 32.5k
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} ...
Joel David Hamkins's user avatar
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 ...
Pace Nielsen's user avatar
  • 18.7k
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 ...
Zakharia Stanley's user avatar
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 ...
Mirco A. Mannucci's user avatar
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 ...
Keshav Srinivasan's user avatar
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,...
abo's user avatar
  • 1,974
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 ...
M Carl's user avatar
  • 521
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: xyx<yx=y Axioms: $\textbf{Well ordering: }\\\...
Zuhair Al-Johar's user avatar
-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?) ...
Hans-Peter Stricker's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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. ...
Qiaochu Yuan's user avatar
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 ...
David E Speyer's user avatar
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 ...
Brendan Cordy's user avatar
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,...
abo's user avatar
  • 1,974
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 ...
user avatar
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 ...
Hans-Peter Stricker's user avatar
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 "...
Noah Schweber's user avatar
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 ...
Wojowu's user avatar
  • 28.2k
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 ...
Colin McLarty's user avatar
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, ...
Vladimir Reshetnikov's user avatar
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 ...
abo's user avatar
  • 1,974
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/...
Peter Smith's user avatar
  • 1,599
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",...
Marc Alcobé García's user avatar
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 ...
Primitive Recursive Fab's user avatar
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 (...
Mirco A. Mannucci's user avatar
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 ...
Eliezer Yudkowsky's user avatar
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 ...
Mikhail Katz's user avatar
  • 16.6k
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 ...
Mikhail Katz's user avatar
  • 16.6k
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....
Noah Schweber's user avatar
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 ...
Zuhair Al-Johar's user avatar
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. ...
Julian Newman's user avatar
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 ...
Mirco A. Mannucci's user avatar