Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [peano-axioms]

For questions on Peano axioms, a set of axioms for the natural numbers.

36
votes
2answers
2k views

Difference between provability and truth of Goodstein's theorem

I have been thinking about the difference between provability and truth and think this example can illustrate what I have been wondering about: We know that Goodstein's theorem (G) is unprovable in ...
29
votes
6answers
3k views

A question on Terence Tao's representation of Peano Axioms

While reading Terence Tao's book on Analysis I had some questions regarding the implication of the Peano Axioms. After writing the following four axioms (which I will write without changing their ...
28
votes
2answers
5k views

How is exponentiation defined in Peano arithmetic?

How would exponentiation be defined in Peano arithmetic? Unless $n$ is fixed natural number, $x^n$ seems to be hard to define. Edit 2: So, what would be the way to define $x^n+y^n = z^n$ using $\...
23
votes
5answers
4k views

Why does induction have to be an axiom?

I noticed that there is an axiom that says that if $S(n)\implies S(n+1)$, and $S(1)$ is true, then $\forall n \in \Bbb N, S(n).$ My question is why is this an axiom? why can't we derive this from the ...
23
votes
4answers
2k views

Statement provable for all parameters, but unprovable when quantified

I've been reading a book on Gödel's incompleteness theorems and it makes the following claim regarding provability of statements in Peano arithmetic (paraphrased): There exists a formula $A(x)$ ...
23
votes
1answer
1k views

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

Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It is known to be independent of Peano Arithemtic (PA), and in fact, was the first such purely number theoretic ...
20
votes
4answers
7k views

Why is Peano arithmetic undecidable?

I read that Presburger arithmetic is decidable while Peano arithmetic is undecidable, and actually Peano arithmaetic extends Presburger arithmetic just with the addition of the multiplication operator....
20
votes
5answers
2k views

Purpose of the Peano Axioms

Wikipedia says the Peano Axioms are a set of axioms for the natural numbers. Is the purpose of the axioms to create a base on which we can build the rest of mathematicas formally? If this is true ...
18
votes
6answers
2k views

Do we have to prove how parentheses work in the Peano axioms?

One thing that has bothered me so far while learning about the Peano axioms is that the use of parentheses just comes out of nowhere and we automatically assume they are true in how they work. For ...
17
votes
4answers
2k views

Leaving out one of the Peano Axioms

What happens if you leave N4 (from Ross' book) out of the Peano axioms which states that if $n$ and $m$ in $\mathbb{N}$ have the same successor, then $n = m$?
17
votes
1answer
660 views

Are the real numbers ever needed to prove a property of the natural numbers?

Suppose no one had invented/discovered the real numbers yet (so e.g., no calculus), would this constrain the possible theorems or knowledge we could have about the natural numbers?
17
votes
1answer
323 views

A model-theoretic question re: Nelson and exponentiation

EDIT: I am not asking about the validity of exponentiation, or PA. My question is about a specific technical claim which Nelson makes in this article (pp. 9-12): that a certain theory does not prove ...
17
votes
1answer
610 views

Is every model of modular arithmetic either even or odd?

Modular Arithmetic (MA) has the same axioms as first order Peano Axioms (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. (http://en.wikipedia.org/wiki/Peano_axioms#First-...
16
votes
3answers
3k views

What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would ...
16
votes
1answer
214 views

Is there a 'nice' axiomatization in the language of arithmetic of the statements ZF proves about the natural numbers?

It's well known that ZF (equivalently ZFC by this question) proves more about the natural numbers than PA. The set of such statements is recursively enumerable so it is recursively axiomatizable. Is ...
15
votes
1answer
334 views

Tennenbaum's theorem without overspill

While trying to clean up Wikipedia's proof sketch for Tennenbaum's theorem (there is no computable non-standard model of Peano Arithmetic), the following strategy occurred to me. Since it seems to be ...
13
votes
2answers
1k views

How does (ZFC-Infinity+“There is no infinite set”) compare with PA?

How does (ZFC-Infinity+"There is no infinite set") compare with (first order) PA? Intuitively, neither theory should be more powerful than the other.
13
votes
2answers
302 views

Growth-rate vs totality

How can one prove the statement, "If a function grows fast enough, it cant be proven total in PA, unless PA is inconsistent"? How fast must it grow to be not provably total?
12
votes
3answers
2k views

How to express “b is a power of 10” – Typographical Number Theory in Gödel Escher Bach

The book Gödel, Escher, Bach (GEB) by Douglas R. Hofstadter introduces a formal system called “Typographical Number Theory” (TNT). It's essentially first order predicate logic over the universe of ...
12
votes
2answers
954 views

Who first proved Peano Arithmetic is not finitely axiomatizable?

By Peano Arithmetic I mean first order Peano Arithmetic. The earliest proof that it is not finitely axiomatizable that I know of is R. Montague, Semantical Closure and Non-Finite Axiomatizability I. ...
12
votes
1answer
506 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
11
votes
1answer
1k views

Why wouldn't someone accept Gentzen's consistency proof?

Reading the consistency section of the Peano Axioms wikipedia page, I came across this sentence: The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, ...
11
votes
2answers
423 views

Can A Decidable Theory Have Nonrecursive Models?

Tennenbaum's theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA. ...
10
votes
3answers
321 views

Why might Dieudonne have been “begging the question” by appealing to second-order Peano Axioms?

Following a comment by Peter Smith, I've been reading A. R. D. Mathias's paper The Ignorance of Bourbaki. Parts of the paper are above my head, but I understand it well enough for my own amateurish ...
10
votes
1answer
1k views

Is it a paradox if I prove something as unprovable?

The Goldbach Conjecture asserts: It is possible to write every even number greater that 2 as the sum of two primes. Assume I can prove that the Goldbach Conjecture is unprovable from the Peano ...
10
votes
2answers
917 views

Is there an effective theory which “solves” the halting problem?

I'm looking for an effective theory $T$ that solves the halting problem, in the sense that for every Turing machine $M$, $T$ either proves that $M$ halts, or that it does not halt. On the face of it, ...
10
votes
1answer
208 views

Does ZFC prove a sentence in the language of arithmetic that PA+Con(ZFC) cannot prove?

Assume ZFC is consistent. Then its clear that PA+Con(ZFC) proves a sentence whose translation cannot be proved by ZFC (namely, that ZFC is consistent). Does ZFC prove a sentence in the language (...
10
votes
3answers
2k views

Can we prove that odd and even numbers alternate without using induction?

It is a simple exercise to prove using mathematical induction that if a natural number n > 1 is not divisible by 2, then n can be written as m + m + 1 for some natural number m. (Depending on your ...
10
votes
0answers
209 views

Is it possible to formalize all mathematics in terms of ordinals only?

Our experience shows that all finitary mathematical objects could be encoded using the natural numbers, and all operations on those objects could be expressed in terms of a few basic operations on ...
9
votes
2answers
3k views

Why don't we use Presburger's arithmetic instead of Peano's arithmetic?

I was reading about quantifier elimination and discovered the Presburger Arithmetic, the article mentions two points about it: It is decidable, complete and consistent. It omits multiplication ...
9
votes
3answers
2k views

Why are addition and multiplication included in the signature of first-order Peano arithmetic?

In the second-order approach to Peano Arithmetic, the only non-logical symbols are the constant $0$ and the successor function $S(*).$ But, when we go to first-order Peano Arithmetic, something goes ...
9
votes
3answers
1k views

Why is it impossible to define multiplication in Presburger arithmetic?

Peano arithmetic defines multiplication recursivly as: $$\begin{gather}a\cdot0=a\\a\cdot S(b)=a+(a\cdot b)\end{gather}$$ Why is this not possible in Presburger arithmetic?
8
votes
2answers
2k views

Deducing PA's axioms in ZFC

Recently I've stumbled across this claim: Peano axioms can be deduced in ZFC I found a lot of info regarding this claim (e.g. what would (one version of) the natural numbers look like within the ...
8
votes
1answer
302 views

Is “PA has no non-standard models” consistent with ZF?

I have seen several proofs that there exist nonstandard models of arithmetic, but they all seem to rely on the compactness theorem, which is not implied by ZF. So are there any proofs in ZF that there'...
8
votes
2answers
2k views

Can someone explain definition of number 1?

I've found the next piece of text: As an example of the second failing, Poincaré recalled the definition of the number 1 offered by another of the logicists, Burali-Forti: $$1 = \imath\,T'\{Ko\...
7
votes
3answers
997 views

George Boolos and Gödel's Second Incompleteness Theorem

In Mind, Vol. 103, January 1994, pp. 1-3, George Boolos wrote: And so on. In fact, if a claim can be proved, then it can be proved that the claim can be proved. And that too can be proved. ...
7
votes
2answers
345 views

How Can the Peano Postulates Be Categorical If They Have NonStandard Models?

Having just read Noah Schweber's excellent answer to this question, I am reminded of something that has always mystified me. I was taught that the Peano Postulates are categorical (that is, any two ...
7
votes
1answer
1k views

Why is better to work with first-order Peano's axioms than with second-order Peano's axioms?

In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the second-order version the operations: addition, multiplication and exponentiation ...
7
votes
2answers
320 views

Formalizing proof of Godel sentence's non-provability?

In the question What does it mean for something to be true but not provable in peano arithmetic? Henning Makholm states, "...he [Godel] gave a (formalizable, with a few additional technical ...
7
votes
2answers
498 views

Defining addition in second order logic

(before saying it's duplicate, read whole question) I was told by someone that we can define addition and multiplication purely in terms of successor function, provided that we work in second order ...
7
votes
1answer
421 views

Why is bounded induction stronger than open induction?

It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, "There exists an n <...
7
votes
1answer
243 views

How common (dense) are undecidable propositions in Peano Arithmetic?

Godel, Turing Rosser et al proved they exist. Are they more like the primes, infinite in number, but getting rarer and rarer as you go along? (Consider larger and larger propositions?) Or are they ...
7
votes
1answer
553 views

Nonstandard models of Presburger Arithmetic

I have a question about nonstandard models of Presburger Arithmetic. I read that an example of a nonstandard model is the set of polynomials with rational coefficients with positive leading ...
6
votes
1answer
648 views

Presburger arithmetic

In discovering that Presburger's arithmetic is one of the weaker systems in PA that does not violate Godel's first incompleteness theorem. Upon reading the wiki article, it said that Presburger proved ...
6
votes
2answers
147 views

Why isn't it necessary to postulate the existence of $1$?

These are the Peano axioms, I'll focus on the second one now: If $a$ is a number, the successor of $a$ is a number. Basically, here is defined the successor function $S(n)=n+1$. My question is, ...
6
votes
2answers
106 views

Can two different models of arithmetic have non-comparable views of peano arithmetic?

For a given model of arithmetic $M$, we say that models view of peano arithmetic, $V(M)$, is $\{\phi : M \models (PA \vdash \phi) \}$. For example the view of the standard model is $\{\phi : PA \...
6
votes
4answers
221 views

Does the successor function imply order?

My confusion is how order arises from the Peano axioms (wikipedia link). From this question I'm not sure that "successor" means "greater than." It seems you could take $\mathbf{0}$ and then the ...
6
votes
2answers
393 views

Is it possible to develop Analysis solely from Peano's axioms

...and a few definitions on the way? When I studied Calculus using Spivak's book It was clearly shown that, in order to prove some fundamental theorems (intermediate value theorem being one of them), ...
6
votes
1answer
292 views

Is Fermat's last theorem provable in Peano arithmetic?

The sentence $S$ which Gödel in his proof of the incompleteness theorem proves to be be unprovable in the system of Peano arithmetic can be proved (as a true theorem of PA) outside PA (and necessarily ...
6
votes
2answers
190 views

Peano axioms: 3 or 5 axioms?

The Peano axioms are usually stated as follows: Zero is a number. If a is a number, the successor of a is a number. zero is not the successor of a number. Two numbers of which the ...