Questions tagged [peano-axioms]

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

Filter by
Sorted by
Tagged with
37
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 ...
31
votes
2answers
6k 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 $\...
30
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 ...
26
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 ...
25
votes
2answers
2k views

How does Peano Postulates construct Natural numbers only?

I am beginning real analysis and got stuck on the first page (Peano Postulates). It reads as follows, at least in my textbook. Axiom 1.2.1 (Peano Postulates). There exists a set $\Bbb N$ with an ...
24
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 ...
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)$ ...
21
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 ...
20
votes
4answers
8k 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 ...
19
votes
1answer
365 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 ...
18
votes
1answer
648 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-...
17
votes
3answers
4k 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 ...
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
248 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 ...
16
votes
1answer
688 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?
15
votes
1answer
387 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 ...
14
votes
2answers
2k 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
329 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?
13
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?
12
votes
3answers
3k 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
1k 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
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, ...
12
votes
1answer
577 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 ...
12
votes
2answers
449 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. ...
11
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 ...
11
votes
3answers
371 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
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 ...
10
votes
1answer
2k 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
943 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
244 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
223 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

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 ...
9
votes
1answer
153 views

What Turing degrees can truth in $\mathbb{N}$ have for different languages?

Tarski’s theorem implies that set of Gödel numbers of statements in the language of Peano arithmetic which are true in $\mathbb{N}$, the standard model of arithmetic, is not a recursive set. In fact ...
8
votes
1answer
831 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 ...
8
votes
1answer
319 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\...
8
votes
1answer
169 views

Really confused about the relationship between set theory, functions, ZFC, Peano axioms, etc.

I don't understand how everything relates. It seems that ZFC is a "first order theory" with axioms described in the language of first order logic, and it can recreate all the same axioms of Peano ...
8
votes
2answers
178 views

“Transfinite Peano Axioms”

Perhaps, the class of ordinals $\Omega$ can be axiomatised up to isomorphism by claiming it to be well-ordered such that for every subset $X\subseteq \Omega$ there exists a "succesor" ordinal $\sigma$ ...
7
votes
3answers
1k 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
511 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
2answers
474 views

Peano's successor function [duplicate]

I have been trying to get my head round ZF set theory and Peano's axioms, but I have hit some confusion over Peano's definition of the successor function, or more accurately von Neumann's model. Why ...
7
votes
3answers
240 views

Are there “interesting” theorems in Peano arithmetic, that only use the addition operation?

More precisely, are there "interesting" theorems of Presburger arithmetic, other than the following four well-known "interesting" ones? The commutativity of addition. The theorem stating there are ...
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
359 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
5answers
390 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 ...
7
votes
2answers
686 views

Can a finite axiomatization of PA be expressed in a finitely axiomatizable first order set theory?

Peano Arithmetic has an infinite number of axioms because of its induction schema; Likewise $\sf ZFC$ has an infinite number of axioms because of its axiom schema of replacement. $\sf NBG$ however ...
7
votes
1answer
536 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 ...
7
votes
2answers
250 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 successors are ...

1
2 3 4 5
14