Questions tagged [peano-axioms]

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

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 $\...
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.
3
votes
1answer
1k views

Prove that no positive integer is both even and odd, and that all positive integers are either even or odd

What is says on the can: Prove that no positive integer is both even and odd, and that all positive integers are either even or odd. This, of course, depends on defining even and odd. For extra ...
2
votes
3answers
1k 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 ...
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 ...
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 ...
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 ...
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?
1
vote
2answers
144 views

Proving that Order for N is Anti-symmetric

I'm having trouble deriving the following fact from the basic properties of $+_{\mathbb{N}}$ and the definition: Definition. $\forall n, m \in \mathbb{N}: (n \geq m) \leftrightarrow (\exists a \in \...
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 ...
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 ...
2
votes
1answer
782 views

Non-standard models for Peano Axioms

This might be an easy question, but I still struggle to comprehend non-standard models for Peano axioms. I understand that Godel Theorem tells us that the theory defined by Peano axioms is not ...
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?
5
votes
2answers
573 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 ...
4
votes
0answers
128 views

Algebraically Constructing the Natural Numbers Using a Binary Operation Satisfying Some Properties

Here is the proposed theory: Definition: Let $M$ be a nonempty set with a binary operation $+$ satisfying the following properties: P-0: The operation $+: M \times M \to M$ is both associative and ...
2
votes
4answers
364 views

Are there natural numbers that are not the descendant of 0?

Based on the Peano Axioms (wich are a way to correctly absolutely define the set of natural numbers - correct me if i'm wrong) it is possible to construct a set of symbols that doesn't quite look the ...
3
votes
2answers
211 views

Prove $\langle \mathbb{N}, x \mapsto x +1, 1 \rangle$ is a Peano system without circular reasoning

How can we show that the structure $\langle \mathbb{N}, x \mapsto x +1, 1 \rangle$ is a model of a Peano system? How can we show that it satisfies the axiom of induction? Don't we have to implicitly ...
2
votes
2answers
101 views

Peano/Presburger axioms - “find” numbers lower or equal than another number

[EDIT/CONCLUSION] It turns out it was actually working.. I was just like too stupid to let the prover run for more time and assumed it would take a lot / not be able to prove with what I've provided ...
1
vote
2answers
225 views

For each $x,y,z∈\mathbb N$, if $x<y$ then $x+z<y+z$

For each $x,y,z∈\mathbb{N}$, if $x<y$ then $x+z<y+z$ I know how to solve this if it was $x=y$ then $x+z=y+z$ (which my professor said I need to do) Is there a definition that says I can change ...
1
vote
0answers
120 views

How should this proof of the associativity of natural number addition be understood?

The context of this question is the proofs of the basic laws of arithmetic beginning with Peano's axioms which are stated starting with the number 1, rather than 0. The modified principle of induction ...
1
vote
2answers
97 views

Using the Definition of Dedekind-Infinite to Replace the Axiom of Infinity

The axiom of infinity in ZFC (see this wikipedia link) allows us to construct the natural numbers. But I think we can drop that axiom and replace it with this one: Axiom of Infinity: There exists a ...
-1
votes
1answer
119 views

Not Skolem's Paradox - Part 3

This is a follow up to a previous question: Not Skolem's Paradox - Part 2. Assume we have a countable, non-standard model of Peano Arithmetic in ZFC. This ZFC model must include a set of ordered ...
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 ...
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 ...
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 ...
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....
5
votes
1answer
1k views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...
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 ...
5
votes
1answer
439 views

Stuck on GEB chapter 9 - is b a MU number? is b a TNT number?

I'm reading through Gödel, Escher, Bach, and I found myself stuck at chapter 9. I've been rereading through several times already, but I must be missing something. To clarify my background, I'm a ...
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 ...
7
votes
1answer
555 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 ...
4
votes
2answers
369 views

Peano Arithmetic before Gödel

If I understand correctly, Gödel was the one to discover how to encode finite sequences of integers in Peano Arithmetic, with his Chinese Remainder Theorem trick (his "beta function"). As a ...
1
vote
1answer
809 views

Gödel, Escher, Bach: $ b $ is a power of $ 10 $.

I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
-1
votes
1answer
409 views

How can Peano ever be proved consistent? [closed]

How can Peano ever be proved consistent? Peano cannot prove itself consistent by the incompleteness theorem. So it requires some higher order theory. That may prove Peano consistent, but that proof ...
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 ...
4
votes
1answer
402 views

Are there more true statements than false ones?

Let us enumerate all statements of PA or ZFC by length, upto n characters, then in the limit as $n\rightarrow\infty$, what proportion of statements are provably true, provably false, or independent? ...
3
votes
6answers
834 views

Is Induction Independent of the Other Axioms of PA?

I am trying to come up with a model of first order Peano Arithmetic (PA) where induction fails. Let $PA^{-IND}$ have the same axioms as PA except the first order induction axiom schema is replaced ...
3
votes
0answers
310 views

Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom: $$\forall x \forall y \forall z\bigr((...
3
votes
2answers
513 views

clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

I am not quite sure what really is meant when talking about "arithmetics" in context of Gödel's incompleteness theorems. How I so far understand it: Gödel proved that every sufficiently powerful ...
3
votes
1answer
393 views

Models of real numbers combined with Peano axioms

Suppose you take the axioms for a Dedekind-complete ordered field and weaken the Dedekind-completeness axiom to the corresponding weaker first-order axiom schema (e.g. replace the left and right sets ...
2
votes
0answers
42 views

Is there a formal term for the algebraic structure equivalent to Thurston's hemigroup without identity? [duplicate]

This question is not a duplicated of https://math.stackexchange.com/a/3183330/342834 . It is a follow-on, asking about the distinction between the subject of that post, and the subject of this post. ...
2
votes
1answer
528 views

Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
1
vote
2answers
151 views

“Recursive definitions” in Tao's Analysis Vol I

I am totally confused when Tao gets into recursive definitions (page 26). Paraphrasing, the axioms of natural numbers let us define sequences recursively. Suppose we want to build a sequence $a_0, ...
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 <...
6
votes
1answer
651 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 ...
5
votes
1answer
450 views

How do we know that certain concrete nonstandard models of the natural numbers satisfy the Peano axioms?

It is easy to come up with objects that do not satisfy the Peano axioms. For example, let $\Bbb{S} = \Bbb N \cup \{Z\}$, and $SZ = S0$. Then this clearly violates the axiom that says that $Sa=Sb\to ...
4
votes
1answer
241 views

Initial Segments of Modular Arithmetic

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. MA is $\omega$-inconsistent and all infinite models ...
4
votes
1answer
227 views

Proof of a proposition regarding recursive definitions (from Terence Tao's Analysis I)

I'm currently reading Terence Tao's book Analysis I, and I got stuck on his proposition 2.1.16 about recursive definitions ; actually, I don't understand his (informal) proof of it. First, here are ...
4
votes
2answers
646 views

Natural numbers in Set Theory

We seem to accept the fact $(\omega,+,\times,<,0,1)^{V}$, where $V:=x=x$ is the set theoretic universe, properly reflects what is intuitively understood to be the set of natural numbers, i.e. we ...