Questions tagged [peano-axioms]

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

100 questions
5k views

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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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? ...
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 ...
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((...
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 ...
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 ...
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. ...
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" ...
151 views

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 ...
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 ...