Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
875
questions
42
votes
2
answers
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 ...
- 403
38
votes
2
answers
8k
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 $\...
- 799
32
votes
5
answers
6k
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 ...
- 901
31
votes
6
answers
4k
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 ...
user170039
29
votes
1
answer
2k
views
Can Peano arithmetic prove the consistency of "baby arithmetic"?
I am reading Peter Smith's An Introduction to Gödel's Theorems. In chapter 10, he defines "baby arithmetic" $\mathsf{BA}$ to be the zeroth-order version of Peano arithmetic ($\mathsf{PA}$) ...
- 6,128
27
votes
1
answer
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 ...
- 48.8k
26
votes
3
answers
7k
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 ...
user223391
25
votes
2
answers
3k
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 ...
- 361
23
votes
4
answers
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)$ ...
- 345
22
votes
6
answers
3k
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 ...
- 679
22
votes
4
answers
9k
views
Why is Peano arithmetic undecidable?
I read that Presburger arithmetic is decidable while Peano arithmetic is undecidable. Peano arithmetic extends Presburger arithmetic just with the addition of the multiplication operator. Can someone ...
- 645
21
votes
5
answers
3k
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 ...
- 252
20
votes
1
answer
425
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 ...
- 3,683
19
votes
1
answer
435
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 ...
- 229k
17
votes
4
answers
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$?
- 505
17
votes
2
answers
4k
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 ...
- 23.2k
17
votes
1
answer
784
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-...
- 179
16
votes
2
answers
3k
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.
- 66.1k
16
votes
2
answers
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 ...
- 775
16
votes
1
answer
745
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?
- 225
16
votes
1
answer
530
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 ...
15
votes
3
answers
3k
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 ...
- 66.1k
15
votes
3
answers
2k
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,939
14
votes
3
answers
4k
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 ...
- 161
13
votes
2
answers
406
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?
user77335
13
votes
1
answer
2k
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, ...
- 2,487
13
votes
1
answer
786
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 ...
- 3,656
12
votes
2
answers
1k
views
Is there a nonstandard model of Peano's arithmetic where any element has only finitely many prime divisors?
By the compactness theorem, there are nonstandard models where don't have finite prime decomposition, and some elements are divisible by infinitely many distinct primes. But what if we want a nice ...
- 1,961
12
votes
2
answers
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. ...
- 1,906
12
votes
1
answer
405
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 ...
11
votes
2
answers
1k
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 ...
- 129
11
votes
3
answers
464
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 ...
- 11.7k
11
votes
1
answer
628
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 ...
- 125
10
votes
1
answer
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 ...
- 3,549
10
votes
2
answers
1k
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, ...
- 9,827
10
votes
1
answer
335
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 (...
- 66.1k
10
votes
4
answers
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 ...
- 9,852
9
votes
1
answer
2k
views
What's the relationship between ZFC and Peano axioms? Are they overlapping, complementary or separate?
What's the relationship between ZFC and Peano axioms? Are they overlapping, complementary or separate?
I'm particularly wondering whether natural number stuff like order can expressed in ZFC at all. ...
- 7,042
9
votes
2
answers
529
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.
...
- 1,245
9
votes
2
answers
301
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$ ...
- 555
9
votes
1
answer
194
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 ...
- 9,852
8
votes
3
answers
3k
views
Why is the Axiom of Infinity necessary?
I am having trouble seeing why the Axiom of Infinity is necessary to construct an infinite set. According to a professor of who's mine teaching a class on "infinity," the Peano axioms are only ...
- 135
8
votes
2
answers
1k
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 ...
- 52.2k
8
votes
3
answers
398
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 ...
- 99
8
votes
1
answer
564
views
Why are we using first-order logic and how to fix PA?
First-order logic (FOL) is pretty bad at pinning down specific structures for which we have no problem to think about intuitively. The classical example for me is $\Bbb N$, for which the first-order ...
- 29k
8
votes
1
answer
445
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
1
answer
2k
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 ...
- 4,051
8
votes
2
answers
929
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 ...
- 2,106
8
votes
3
answers
554
views
How can induction work on non-standard natural numbers?
When we consider the Peano axioms minus the induction scheme, we can have strange, but still quite understandable models in which there are "parallel strands" of numbers, as I imagine in the ...
- 29k
8
votes
1
answer
1k
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 ...
- 17.7k