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

learn more… | top users | synonyms

1
vote
3answers
42 views

Regarding Peano's Axioms

According to the Wikipedia entry on the Peano axioms: "the number 1 can be defined as $S(0)$, 2 as $S(S(0))$ (which is also $S(1)$), and, in general, any natural number n as the result of n-fold ...
2
votes
2answers
46 views

Variations in the successor fuction from Peano's axioms

Concerning the successor function in Peano's axioms, what prevents me from defining it in the following way: 0 to 2, 2 to 1, 1 to 4, 4 to 3, 3 to 6, 6 to 5, 5 to 8, 8 to 7 ... and so on. It seems ...
0
votes
1answer
73 views

Which one of the following logical propositions is to be preferred?

I'm trying to update the symbolism of Giuseppe Peano's "Arithmetices Principia", to make the translation freely available. Might I ask you, which of the following might be a correct mathematical ...
4
votes
1answer
60 views

Transfinite Induction in Peano Arithmetic

I have heard that Peano Arithmetic (PA) cannot perform transfinite induction up to $\varepsilon_0$. This seems to imply that it can induct up to smaller ordinals, like $\omega$ or $\omega^\omega$ or ...
1
vote
2answers
61 views

Set of axioms for finite subset of Natural Numbers

I would like to get a set of Peano like first-order axioms for a finite subset of natural numbers $N'$ such that $0 \leq N' \leq Max$, with $Max$ denoting the upper-bound. (So my signature might be ...
2
votes
3answers
42 views

Prove that the greatest common factor of $m+n$ and $m^2+n^2$ is 1 or 2 if $m$ and $n$ are relatively prime.

Prove that the greatest common factor of $m+n$ and $m^2+n^2$ is $1$ or $2$ if $m$ and $n$ are relatively prime natural numbers. Can anyone give a step-by-step answer for this?
0
votes
3answers
45 views

Why doesn't inequality hold as a property in natural number induction?

It is said that all natural numbers follow the rule of induction: if a said property holds for one number and for its successor, it holds for all natural numbers. But, let us define the following ...
1
vote
1answer
35 views

Modifying the Peano Axioms to allow multiple successors

If you took the familiar Peano Axioms and replaced the axiom $x \in \mathbb{N} \implies \exists y\in \mathbb{N}(y =S(x))$ with $x \in \mathbb{M} \implies (\exists y_1\in \mathbb{M})(\exists ...
2
votes
2answers
95 views

embdedding standard models of PA into nonstandard models

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...
1
vote
1answer
57 views

Failures of categoricity not related to size?

The paradigmatic cases I know of theories failing to be categorical are cases that seem tied to the language's inability to distinguish between different infinite cardinalities of the theories domain. ...
2
votes
4answers
142 views

Peano's Axioms: Mathematical Philosophy

In Peano Axioms, why is it necessary to define number and successor. Does not using them imply that we know what they mean? Or could they have just as easily been any two arbitrary terms which are not ...
1
vote
2answers
57 views

Prove that the set of all integers $>0$ is the smallest inductive set

An inductive set is a set $I$ such that $1 \in I$ and if $x \in I$ then $x+1 \in I.$ Some authors define the set of all integers $>0$ as the smallest inductive set, say Apostol's Analysis. But I ...
1
vote
1answer
80 views

How is first-order logic derived from the natural numbers?

I've heard that first-order logic comes from Peano Arithmetic, yet I can't see how. We don't need numbers to formulate quantifiers, variables, functions, constants, relations or even sets. Insted, it ...
1
vote
1answer
146 views

Construction of a model of Peano Arithmetic

I'm studying the axioms of Zermelo-Frankel Set Theory at the moment. I already know the following six axioms: The axiom of empty set The axiom of extensionality The axiom of pairing The axiom of ...
0
votes
0answers
46 views

Strong logical system without principle of explosion

Are there some logical systems strong enough to contain theorems of first/second order Peano Arithmetic but constructed in such way that principle of explosion does not hold for them?
1
vote
0answers
42 views

Is there a difference between induction in Peano Arithmetic and Presburger Arithmetic

Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics I was thinking ...
2
votes
1answer
52 views

Peano's Axioms and Induction

I was reading Landau's Foundations of Analysis. He starts his construction of number systems by stating five axioms. My question is related to the fifth, the axiom of induction: Let there be given a ...
2
votes
4answers
105 views

Counting numbers vs Natural numbers; Peano Axioms

I can feel that my question is going to be a somewhat lengthy one, but I will try my best to deliver it in as short a form as I can manage. So to begin, I've always thought that the numbers such as ...
2
votes
2answers
71 views

Check my proof of “overspill” in non-standard models of Peano arithmetic.

Proposition Let $\mathcal{M}$ be a nonstandard model of Peano arithmetic, $\phi(v,\bar{w})$ a formula in the language of arithmetic, and $\bar{a} \in \mathbb{M}$. Show that if $\mathcal{M} \models ...
1
vote
1answer
35 views

Proving the order relation in $\mathrm{PA}$ is total.

Let $\mathrm{PA}$ be the first order logic axioms of Peano Arithmetic. Define an order relation by: $$ x\leq y\; \text{ if }\; (\exists z)(x+z=y). $$ Can it be proved that this relation is total?
8
votes
1answer
229 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 ...
4
votes
0answers
91 views

Incompleteness theorem

Correct me if I am wrong at any point! Godel's incompleteness theorem allows us to express "PA is consistent" in the language of Peano arithmetic, and shows that this is not provable in PA. Let's ...
1
vote
1answer
86 views

Prove true in natural numbers (Peano Arithmetic)

While reviewing old exercise sheets, I have found this question and am having difficulties understanding some of the logic: Let $\mathbb{N}$(natural numbers) be a model for Peano Arithmetic, that ...
1
vote
2answers
109 views

Prove $x' \neq x$ using Peano axioms

I am looking at Edmund Landau, Foundation of analysis and do not agree with is proof of Theorem 2 part 2. I put the pages here for easy reference (http://pbrd.co/1y89p7b and http://pbrd.co/1y89A2s). ...
1
vote
1answer
104 views

Definition of the sum of natural numbers

After define the natural numbers using the Peano axioms, I'm trying to understand the definition of sum between natural numbers, let $s$ be the successor function used in the Peano axioms. The most ...
2
votes
1answer
49 views

Why is it impossible to define multiplication in Presburger arithmetic yet possible to define exponentiation in Peano Arithmethic?

Hello my question is related to Why is it impossible to define multiplication in Presburger arithmetic? and to How is exponentiation defined in Peano arithmetic?. I would have preferred to add it as a ...
2
votes
3answers
90 views

Possible not countable extension of the natural numbers?

This question comes from:Is $1234567891011121314151617181920212223......$ an integer? We define $\mathcal{A}$ as the set of infinite strings of digits $$ \bar a_i=a_0 a_1a_2a_3\cdots a_i \cdots ...
1
vote
2answers
149 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 ...
2
votes
4answers
149 views

Another problem on Peano Axioms (indirectly) from Tao's Analysis book

In Terence Tao's book Analysis I, the definition of $1$ is given right after stating the first two axioms, namely the following axioms, Axiom 1. $0$ is a natural number. Then Tao elaborates the ...
0
votes
1answer
61 views

Why are all computable functions representable in PA?

I'm trying to understand the proof of the first incompleteness theorem, and more specifically, the diagonal lemma. Suppose $GN(x)$ is the Gödel Number of a formula $x$. The first step of the diagonal ...
1
vote
1answer
101 views

Reference request - Outline of Edward Nelson's Inconsistency Proof

Edward Nelson retracted his inconsistency proof before it was published. Unfortunately, the outline given by Nelson has been removed. Is there a copy of it on the web? I am interested in how the ...
6
votes
2answers
115 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, ...
1
vote
2answers
68 views

For which subsystems T of 2nd order arithmetic is there a model of T + $\neg$Con(T)?

A theory T might have the following property: there is a model of T + $\neg$Con(T) 1st order PA has this property, but full 2nd order PA doesn't. Among subsystems of 2nd order arithmetic, which ones ...
6
votes
2answers
134 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 ...
1
vote
2answers
66 views

How can I prove this proposition from Peano Axioms?

The problem is, Prove that for each positive natural number $a$ there exists a natural number $b$ such that $b{++}=a$. Using only the followings, Peano Axioms. Axiom 2.1 ...
1
vote
1answer
116 views

Prove $n<m{++}\leq n{++}\iff m=n$ from Peano Axioms

The problem is, Prove that $n<m{++}\leq n{++}\iff m=n$. Using only the followings, Peano Axioms (see the axioms here). Definition of Addition: Let $m$ be a natural number. We ...
19
votes
6answers
1k 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 ...
1
vote
1answer
98 views

Existence of nonstandard elementary extensions of $PA$?

My question follows from the 1958 result of MacDowell–Specker (located originally in Modelle der Arithmetik, J. Symbolic Logic Volume 38, Issue 4 (1973), 651-652) of the proof of the following ...
0
votes
1answer
91 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 ...
3
votes
1answer
71 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 ...
3
votes
2answers
73 views

Are these two definitions of the natural numbers equivalent?

If we consider two definitions of the natural numbers: Definition 1 $N$ is the set that satisfies all of: There is an element $0$ in $N$. For each element $n$ in $N$, there is the successor of ...
1
vote
1answer
78 views

Proving that successor of a number is not zero

I am stuck proving the simple claim that $Sx \neq 0$ in say Peano Arithmetic (the first order theory of arithmetic) or Robinson Arithmetic or Presburger Arithmetic. I see that this is sometimes added ...
1
vote
2answers
103 views

Is $\neg Con(PA)$ true in a model of $PA+\neg Con(PA)$?

It is known that if Peano arithmetic (PA) is consistent then $PA+\neg Con(PA)$ is also consistent. One way we can express $Con(PA)$ is $\forall x(\neg P(x))$ where $P(x)$ expresses that $x$ encodes a ...
2
votes
0answers
40 views

Prove $[(n, k)] = 7^{*} \iff n - k = 7$

Prove $[(n, k)] = 7^{*} \iff n - k = 7$ given $7^{*} = [(8,1)] \in \mathbb{Z}$ and $k < n \in \mathbb{N}$ using any facts about addition in the Peano System. $k < n \in \mathbb{N}$ is ...
0
votes
1answer
37 views

Natural numbers proof via Peano's axioms (not trichotomy)

Prove that for each $x,y$ an element of the natural numbers ($\mathbb{N}$), $x<y$ or $x=y$ or $x>y$. So at least one is true. I have the definition of order to work with and the basic algebra of ...
3
votes
1answer
67 views

defining inequality of natural numbers by case-analysis

If I add to Peano Arithmetic a relation (predicate?) symbol $\leq$ and an axiom $\forall n\forall m(n\leq m \leftrightarrow n=m \lor S(n)\leq m)$, can I prove $\forall n\forall m(n\leq m \to n\leq ...
1
vote
4answers
84 views

Name this binary operation on $\Bbb N$

An operation $\ominus$ for the natural numbers is defined as follows: $$a\ominus 0 = 0\ominus a = a\\S(a)\ominus S(b) = a\ominus b$$ Here $S$ is the successor function. The operation $a\ominus b$ is ...
1
vote
1answer
39 views

How can Goodstein's theorem be expressed in PA

I understand Goodstein's Theorem and its proof. I'm trying to understand the proof of why Goodstein's Theorem cannot be proved in PA. However, it's not immediately clear to me that Goodstein's Theorem ...
0
votes
1answer
28 views

Show that $\mathbb{N}=\{ 0\} \sqcup S(n)$ and also that that union is disjoint?

Show that $\mathbb{N}=\{ 0\} \sqcup S(n)$ and also that that union is disjoint? I've been assigned this exercise in my lectures of elements of mathematics 2. Three axioms have been given for a Peano ...
6
votes
1answer
234 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, ...