Peano arithmetic (or Peano axioms) is a set of axioms for the natural numbers proposed by Giuseppe Peano in 1889.

learn more… | top users | synonyms

50
votes
3answers
6k 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 ...
37
votes
7answers
2k 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 ...
35
votes
2answers
2k 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 ...
29
votes
3answers
2k 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 ...
27
votes
8answers
3k 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 ...
27
votes
3answers
2k 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)$. ...
26
votes
1answer
427 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 ...
24
votes
3answers
2k 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 ...
15
votes
4answers
2k views

What is induction up to epsilon_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 $\epsilon\_0$, which has been ...
13
votes
6answers
1k 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?
12
votes
2answers
1k views

Is there a known natural model of Peano Arithmetic where Goodstein's theorem fails?

(I've previously asked this question on the sister site here, but got no responses). Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It turns out that this ...
12
votes
1answer
260 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 ...
12
votes
1answer
604 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 ...
12
votes
1answer
389 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, ...
11
votes
1answer
394 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 ...
10
votes
5answers
1k 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 ...
10
votes
3answers
731 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 ...
10
votes
2answers
639 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 ...
9
votes
4answers
489 views

Boolean Valued Models of PA

O.K, a massively naive question. I've never really studied any non-standard models of PA before. I was just wondering if there's ever been any attempt to use the kind of Boolean valued model theory ...
9
votes
4answers
3k views

Historically first uses of mathematical induction

I'm interested in find out what were some of the first uses of mathematical induction in the literature. I am aware that in order to define addition and multiplication axiomatically, mathematical ...
9
votes
3answers
260 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 ...
9
votes
2answers
389 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 ...
9
votes
1answer
681 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 ...
8
votes
10answers
4k 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 ...
8
votes
3answers
306 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 ...
8
votes
1answer
345 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 ...
8
votes
1answer
369 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 ...
8
votes
2answers
830 views

The different Branches of Arithmetics

... "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 ...
7
votes
4answers
2k 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) ...
7
votes
3answers
1k 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 ...
7
votes
3answers
434 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 ...
7
votes
4answers
567 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 ...
7
votes
1answer
997 views

models of PA which are isomorphic but not elementarily equivalent?

On page 164 of his book Models of Peano Arithmetic, Kaye states Friedman's Theorem: Let $M{\vDash}PA$ be nonstandard and countable, let $a\in M$ and let $n\in {\mathbb N}$. Then there is a proper ...
7
votes
1answer
176 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 ...
7
votes
1answer
610 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 ...
7
votes
1answer
579 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 ...
7
votes
1answer
257 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 ...
7
votes
1answer
273 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 ...
7
votes
1answer
510 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 ...
6
votes
2answers
364 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. ...
6
votes
1answer
162 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$: ...
6
votes
1answer
268 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 ...
6
votes
1answer
490 views

How to locate the paper that established Robinson Arithmetic?

If I'm not mistaken, it was in his seminal paper “An Essentially Undecidable Axiom System”, published in Proceedings of the International Congress of Mathematics (1950), 729–730, where R.M. ...
5
votes
4answers
492 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 ...
5
votes
3answers
3k views

Non-computable but easily described arithmetical functions

I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted ...
5
votes
2answers
881 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 ...
5
votes
2answers
557 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 ...
5
votes
2answers
849 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 ...
5
votes
2answers
163 views

Models of PRA/EFA with induction on $X$ but not $\omega^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 $(\omega \uparrow\uparrow N) < \epsilon_0$, that ...
4
votes
7answers
3k views

Are real numbers countable in constructive mathematics?

We are talking about ordinary reals in constructive mathematics. Let represent each real number by infinite converging series: $$r = [\;(a_0,b_0),(a_1,b_1),...,(a_i,b_i),...\;]$$ $$where\quad a_i ...