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

learn more… | top users | synonyms

1
vote
0answers
21 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
30 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
44 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
69 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
63 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
74 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
34 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
54 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
71 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
24 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
25 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
135 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, ...
1
vote
2answers
60 views

How to prove that if m and n are natural numbers than m+n is also a natural number?

Problem sounds easy enough - prove that if $m$ is in set of all natural numbers (let's call it $\mathbb N$) and so is $n$ than $m+n$ also must be there. Probably it should be done using induction. But ...
0
votes
1answer
32 views

Need help with a basic proof using Paeno Axioms showing that a recursively defined function is one to one

Assume $(N, 0_N, ++^N) and (N˜, 0_{N˜} , ++^{N˜} )$ are two systems satisfying the Peano axioms. Define the function $T : N → N˜$ by $T(0_N) = 0_{N˜}$ and $T(n++^N) = T(n)++^{N˜}$ Prove that ...
3
votes
2answers
65 views

Finite list of axioms of $\mathsf{ACA}_0$ - reference?

It seems to be common knowledge that $\mathsf{ACA}_0$ can be finitely axiomatized, see for example Can a finite axiomatization of PA be expressed in a finitely axiomatizable first order set theory? ...
0
votes
1answer
109 views

Is every natural number even or odd?

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx = 0)$. MA has finite models and every infinite model of MA must ...
1
vote
0answers
152 views

True statements about natural numbers that are undecidable in Peano Arithmetic *assuming consistency of PA only*?

I am looking for statements $P$ of Peano Arithmetic (PA) that have the following properties: They are as concrete and simple as possible. It is provable by finitistic means that neither $P$ nor ...
1
vote
2answers
52 views

How to show inductive principle doesn't work for this system?

I have to prove why each Peano axiom that doesn't hold for a set $\mathbb{N}$ with base case $1$, and $S(1) = 2, S(2) = 3, S(3) = 1$, and $S(n) = n + 1$ for all $n \geq 4$. Obviously $S(3) = 1$ ...
1
vote
1answer
32 views

If $x \in P$ and $x \neq 1$, then $x = S(y)$ for some $y \in P$

$P$ is a Peano system and $S$ is the successor function. We want to show that all $x \in P$ (except $1$) are successors of some $y \in P$, so I guess we can use induction. The case where $x = 1$ is ...
1
vote
1answer
64 views

Prove an addition property of Natural numbers

Prove: For any $x,y \in \mathbb{N}, y \neq x+y$. I'm only suppose to use the Peano axioms as defined here http://aleph0.clarku.edu/~djoyce/numbers/peano.pdf and the properties of addition in ...
3
votes
2answers
55 views

Is is possible to prove that two systems of axioms are equivalent

The question is self explanatory. Is it possible to prove that two systems of axioms in two very different branches of math are equivalent? Is there a textbook to help me? Thanks!!
1
vote
0answers
49 views

Prove that the product of 2 positive natural numbers is also positive.

First time doing real analysis, using Tao's Analysis I, and I'm stuck in the second problem (2.3.2) If n and m are both positive, then nm is also positive. How do I prove such an obvious statement? I ...
8
votes
1answer
166 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 ...
5
votes
1answer
77 views

If a statement holds for all standard models of PA, then does it hold for all models?

Suppose that $\varphi$ is a consequence of every standard model of PA. Then is it provable from PA?
3
votes
2answers
92 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
votes
1answer
103 views

Are All Nonstandard Models of PA Ill-Founded?

We often use sets to represent natural numbers, but we can also use natural numbers to represent sets. For example, we can use the binary expansion of a natural number to represent a set. The number ...
2
votes
4answers
270 views

Can a Peano Set have two or more zeros?

I repeat the Peano Axioms: 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 equal are themselves ...
1
vote
2answers
148 views

proof by induction that every non-zero natural number has a predecessor

I am trying to prove by induction that every non-zero natural number has at least one predecessor. However, I don't know what to use as a base case, since 0 is not non-zero and I haven't yet ...
1
vote
2answers
102 views

Can we make recursion into an axiom schema?

The language of second-order arithmetic is (by definition) generated by a constant symbol $0$ and a unary function $S$. However, first-order arithmetic (hereafter $\mathrm{PA}$) famously requires a ...
2
votes
3answers
80 views

One-element model of first-order PA

The First-Order axiomatisation of PA is: $\forall x. x = x$ $\forall x, y. x = y \rightarrow y = x$ $\forall x, y, z. x = y \land y = z \rightarrow x = z$ $\forall x. 0 \ne S(x)$ $\forall x, y. S(x) ...
1
vote
1answer
190 views

proof of commutativity of multiplication for natural numbers using Peano's axiom

How do you prove commutativity of multiplication using peano's axioms.I know we have to use induction and I have already proved n*1=1*n.But I cant think of how to prove the inductive step.
2
votes
2answers
64 views

Can Goodstein's theorem be expressed as an axiom or axiom scheme in PA?

A statement like $\mathsf{Con(PA)}$ depends (or at least seems to depend) on a specific Gödel numbering. My question is whether Goodstein's theorem may be expressed directly in the language of ...
1
vote
1answer
128 views

Proving the definition of addition

Here is Theorem 4 and the proof of its part 2 from E. Landau's Foundations of Analysis. ($x'$ means $s(x)$ where $s$ is the successor function). In part 1 he proved that there is at most one way to ...
4
votes
2answers
132 views

Why is the language of arithmetic usually $(+, \cdot, 0, s)$, not $(+, \cdot, 0, 1)$?

The formalized theory of arithmetic has usually $(+, \cdot, 0, s)$ as its language. However, from what we usually do in ring theory, it seems natural to use $(+, \cdot, 0, 1)$ as the language of ...
0
votes
1answer
93 views

How is addition on N formally defined in textbooks on real analysis?

This is a follow-up question to Why does the definition of addition require proofs? In Landau's Foundations of Analysis, his definition of addition on the natural numbers seems a bit strange to me -- ...
1
vote
2answers
142 views

Why does the definition of addition require proofs?

The book is Foundations of Analysis by E. Landau. I delve into analysis for the first time. Before I would encounter merely a definition of something in a textbook, but now there is something more. ...
2
votes
2answers
67 views

Expressions in Peano Arithmetic that falsify these statements?

I'm trying to find expressions ($P$ and $Q$) using Peano arithmetic that falsify these 'equivalences'. I have some intuition about the nature of expressions using higher level theories, but not ...
2
votes
2answers
154 views

How can the Gödel sentence be Pi_1

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve ...
1
vote
1answer
60 views

A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a ...
2
votes
1answer
84 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
3
votes
4answers
173 views

Successor of 0 is 1

Using the Peano axioms as the foundation for arithmetic (but further elementary structure can be developed), where S is the successor operation and 0 is an element of what we will call the set of ...
2
votes
1answer
74 views

Why Quantifier Free Formulas define Linear Functions.

How do you prove that functions definable by quantifier-free formulas must be linear? I am interested for the structure $\langle Q,+,0\rangle$.
0
votes
0answers
97 views

When is a Decidable Set Decidable?

Can the same set be decidable in a strong theory and undecidable in a weaker theory? Some possible examples. Goodstein's theorem says every Goodstein sequence, $g(n)$, eventually terminates. ...
1
vote
2answers
79 views

Systems the Peano axioms can be derived in

I know that the Peano axioms can be got from ZF set theory, and lambda calculus. What other systems can they be derived (I'm not sure if that is quite the right word here) in, and which the simplest ...
1
vote
1answer
67 views

Hyperoperations and $\mathsf{PA}$

I am very confused about the "role of the hyperoperations" in the peano arithmetic. For example addition's and multiplication's axioms are given. $A_1$ $\forall x(x+0=x)$ $A_2$ $\forall ...
1
vote
1answer
63 views

First-order Peano Axioms and order-completeness of $\mathbb{N}$

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo. Notation: We denote the system of first-order Peano Axioms (along with ...
-1
votes
1answer
116 views

Every Countable Model of PA is Recursive?

I am interested in any obvious flaws in the following argument. Assume we have a countable model of Peano arithmetic in a meta-theory like ZFC. Assume this model has a set of ordered triplets, ...
0
votes
1answer
49 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 ...
4
votes
1answer
127 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 ...