Questions tagged [peano-axioms]

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

1
vote
0answers
69 views

Mathematical induction - the set version v.s. predicate version

There are two versions I know for mathematical induction, as well as structural induction. One says for all subset $S$ of $\Bbb N$, $1\in S\wedge (\forall n,~n\in S\rightarrow s(n)\in S)\rightarrow S=\...
0
votes
1answer
39 views

Is it to say that whenever we use mathematical induction, we're inevitably admitting Peano axioms for $\Bbb N$ indeed?

From Enderton's mathematical logic book sec 1.1, there is a thing called construction sequence for wffs. For example, $P\wedge Q\to R$ can be thought as $\langle P,~Q,~P\wedge Q,~R,~P\wedge Q\to R\...
2
votes
1answer
91 views

Variations in the Statement of Strong Induction: Equivalent or Different?

I often see two variations in how the principle of strong induction is stated: First Variation: $\Big(B\!\subseteq\!\mathbb{N}\wedge1\!\in\!B\wedge\big(\forall x[x\!\leq\!k\rightarrow x\!\in\!B]\...
0
votes
1answer
44 views

Is $K_{n-1}$ a $\Sigma_{n-1}$-elementary substruture of $K_n$ [closed]

Is $K_{n-1}$ a $\Sigma_{n-1}$ elementary substruture of $K_n$? Let $M$ be any non-standard model of PA. $K_n$ is define to be the set of $\Sigma_n$-definable elements of $M$. I have a feeling the ...
18
votes
6answers
2k 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 ...
0
votes
2answers
53 views

How do I know what I need to show when using induction? (Peano axioms)

As an exercise I wanted to prove that addition was commutative using the Peano axioms. To quickly restate the definition of addition (where $S(n)$ is the successor function of $n$, which we can show ...
4
votes
2answers
796 views

Prove addition is commutative using axioms, definitions, and induction

I wanted to try to prove the commutative property of addition before reading too much about it and "spoiling" things for myself. So I am curious how close I got. First, some axioms (statements/...
2
votes
3answers
362 views

Some questions about the successor function

So I am learning about the successor function $S(n)$ where we have $S(n) = n+1$ basically. So $S(0) = 1, S(1) = 2, S(2) = 3, S(3) = 4$, etc. But are we explicitly mapping $0$ through $9$ "by hand" ...
2
votes
3answers
419 views

Proof of Strong Induction Using Well-Ordering Principle

Context: I keep running into circular reasoning in attempting to derive strong induction (more generally "induction" whether it be weak or strong) from the well-ordering principle. Assume: Peano ...
3
votes
1answer
230 views

Exercises and solutions for natural deduction proofs in Robinson and Peano arithmetic

Does any of you know where I can find Exercises and solutions for natural deduction proofs in Robinson and Peano arithmetic? Thanks and regards.
4
votes
0answers
114 views

Is there a weak set theory that can prove that the natural numbers is a model of PA?

$ZFC$ proves that $\mathbb N$ is a model of $PA$. Even $ZF$ does. How weak can go? In particular, is there some weak set theory that proves that $\mathbb N$ is a model of $PA$, but does not proof ...
4
votes
2answers
88 views

Is it true that $0\in 1$?

From Zermelo–Fraenkel set theory and Peano axioms, we have $0=\varnothing$ and $1=\varnothing\cup{\{\varnothing\}}\implies0\in 1$. Many thanks for your help!
0
votes
2answers
195 views

Peano Axioms and loops

I want to know if the usual Peano axioms can really deal with "problems" like the following loop: I honestly don't see the axioms avoid the last diagram. Thanks in advice.
1
vote
0answers
73 views

First Incompleteness Theorem made exact…

First Incompleteness Theorem, according to WIKIpedia: "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are ...
4
votes
2answers
179 views

Show that PA can prove the pigeon-hole principle

So the following exercise is from Richard Kaye's Book exercise 5.12 (Chapter 5) The pigeon-hole principle is the scheme: For any formula, $\psi$, in the language of arithmetics, $\forall s\ (\...
7
votes
2answers
349 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 ...
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 ...
2
votes
3answers
367 views

Is every true statement about the natural numbers provable in ZFC?

Related questions: Difference between undecidable statements in set-theory and number theory? Is the arithmetic most mathematicans use a modelled within first or a second order logic? Peano's axioms ...
3
votes
2answers
81 views

For any two models of PA, is one model a cut of the other?

For two models of arithmetic $M_1=(S_1, 0_1, 1_1, +_1, \times_1, <_1)$, $M_2(S_2, 0_2, 1_2, +_2, \times_2, <_2)$, we say that the $M_1$ is a cut of the $M_2$ if there is a $S \subseteq S_2$ such ...
1
vote
1answer
250 views

Proving that no number is the successor of itself

I'm doing my research project on Peano Arithmetic, and need to show the PA can prove that no number is the successor of itself. I've seen an answer here: Peano's Axiom: Is it implied that ...
0
votes
1answer
74 views

Logic proof for $(x\leq y\to 0\leq y-x), x+y-y=x$, and the property that the product two consecutive numbers is even

I need to find the proof for $(x\leq y\to 0\leq y-x)$ $x+y-y=x$ $(\exists u ((u+u)=s(x)\times x))$, where s is the successor function. Or, the product of two consecutive natural numbers is even. I ...
1
vote
0answers
90 views

What's a good source on how to construct all sets of numbers?

Lately I've been interested in building, formally, all sets of numbers, starting from ℕ, then ℤ, then ℚ, then ℙ, then ℝ, then iℝ, then ℂ. The only book I have come up, so far, is "Foundations of ...
12
votes
2answers
957 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. ...
2
votes
1answer
95 views

Why the following initial segment is NOT a model of PA

Let $M$ be a non-standard model of PA, fix an $a \in M$ \ $\mathbb{N}$ Consider the collection: $$I:=\{b\in M\ |\ b<a^n,\ \text{for some }n \in \mathbb{N}\}$$ It is easy to see that this is ...
0
votes
2answers
133 views

Formulation of the Successor Function as an Endofunction in First-Order Logic

The Peano axioms are often listed (among other ways) as a set of 5 axioms in an informal language or 3 axioms in a formal language. For example: Informal (see, e.g., http://mathworld.wolfram.com/...
1
vote
1answer
198 views

Precise reason why a non standard model of arithmetic is not isomorphic to the natural numbers

So I'm looking for a (more) precise reason why a non standard model of arithmetic is not isomorphic to the natural numbers. Under the usual language of arithmetics, +, <, S, $0$, $\times$ I.E) Let ...
1
vote
0answers
114 views

Why do we need second-order logic?

I often read that without second-order logic we can't have a theory of natural numbers because we wouldn't be able to express the well-ordering principle. OK, then there must be a flaw in the ...
0
votes
1answer
47 views

Upper bound of the “number” of countable models of Th$\mathbb{N}$ up to isomorphism

So basically I want to find out what is the upper bound of the "number" of countable models of Th($\mathbb{N})$ up to isomorphism. In the book by Richard Kaye, on Peano arithmetics, he simply said ...
2
votes
2answers
59 views

Clarification needed on ordering $\mathbb{Z}[X]$ in the language of arithmetic.

I have been reading the book by richard kaye, on peano arithmetic. In section 2.1, he gave the following statement. "$\mathbb{Z}[X]$ is made into a $L_A$ structure by defining an order $<$ making $...
4
votes
0answers
92 views

Show that there are only $\aleph_0$ many countable models of the following theory.

Consider a language $L$ with $<0,1,S>$, where $S$ is the successor function. Show that there are only $\aleph_0$ many countable models of Th$(\mathbb{N})$, under $L$. This is one of the ...
1
vote
3answers
92 views

Defining the sum on the set $\mathbb N$

Suppose we have a set $\mathbb N$, $0\in \mathbb N$ and $\sigma\colon \mathbb N \to \mathbb N$ satisfying Peano axioms of natural numbers. Inside ZF (or ZFC if needed) how do we define the "addition"...
1
vote
2answers
522 views

Why induction works when the starting point $0$ and the theorem valid for non-zero natural numbers in Peano's arithmetics

First of all, I should note that I'm working on Peano's axioms for constructing natural numbers. For example, lets try to prove that "every natural number is the sum of four squares" by induction.The ...
1
vote
1answer
91 views

Is arithmetic on the naturals $\omega$-consistent?

Is there any first order theory of arithmetic of the natural numbers that is known to be $\omega$-consistent if it is consistent? If yes, then how?
2
votes
2answers
68 views

Existence of inaccessible natural number divisible by every standard natural number under PA

Let $P$ be the proposition that there exists a non-zero number that is divisible by every standard natural number. Let $N$ be a non-standard model of PA. Must $P$ be true in $N$?
4
votes
2answers
120 views

Definition or Axiom for less than for real numbers

I was curious as to what the definition for $<$ would be concerning real numbers. I have looked at Peanos axioms which discusses inequalities for every $a, b\in\mathbb{N}$, $a<b$ iff there is ...
2
votes
1answer
116 views

Nonstandard cardinalities and $\mathbb{N}$

Let us work in the standard ZFC universe $S$. Within it there also exist nonstandard models of ZFC. In our standard universe we have (standard) $\mathbb{N}$ with countable cardinality. Within the ...
0
votes
1answer
74 views

A question about $S(n)=S(m) \Rightarrow n=m$, S being the successor function.

In Naive Set Theory, Halmos proves that $S(n)=S(m) \Rightarrow n=m$ in this way: We are now ready to prove $(V)$. Suppose indeed that $n$ and $m$ are natural numbers and that $n^+ = m^+$. Since $...
1
vote
3answers
149 views

How to prove $n\leq x \rightarrow x = n \vee Sn \leq x$ using Robinson Arithmetic

Given the definition $n \leq x \Leftrightarrow \exists y \ni y+n=x$, how can one prove $n\leq x \rightarrow x = n \vee Sn \leq x$ in Robinson Arithmetic? I think this should be a proof by induction, ...
3
votes
2answers
158 views

First order Peano axioms and their intepretation

I am still better trying to understand the first order Peano Axioms and their relation to the standard model. Just for reference, here are the axioms I work with: $1.\space \forall x (\neg x+1=0)\...
-4
votes
1answer
165 views

Does AoI follow from Peano's Axioms? [closed]

Using only the axioms of FOL and ZFC-AoI, can we prove the following? $0\in N$ $\land \forall x\in N: S(x)\in N$ $\land \forall x,y \in N:[S(x)=S(y)\implies x=y]$ $\land \forall x\in N:S(x)\neq 0$ ...
0
votes
1answer
331 views

Commutative Property of Natural Number Multiplication

I am working with formal construction of natural numbers, in terms of the empty set and successor function, a la Peano. Here is the definition of addition, defined inductively; Definition : Function +...
2
votes
1answer
102 views

Proof of $\forall x \forall y(x+x \neq y+y+1)$ in Peano arithmetic

How to prove $\forall x \forall y(x+x \neq y+y+1)$ using the axioms of Peano arithmetic?
1
vote
0answers
64 views

What are the practical (if any) problems with PA and the existence of non-standard models

Forgive me if this question sounds naive or somewhat poorly constructed due to my nebulous understanding of the concepts involved... I have recently been reading about the nature of PA, and how, ...
0
votes
2answers
553 views

Difficulty proving the commutative law of multiplication on $\mathbb{N}$

I am trying to prove the commutative law of multiplication for the natural numbers using the Peano axioms. I have already defined addition and order with the successor function. My definition of ...
10
votes
2answers
918 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, ...
4
votes
2answers
108 views

References discussing the technical differences of $\neg\mathrm{Con}(\mathrm{PA})$ and “to exhibit an actual contradiction in PA”?

Question. What references do you recommend that dryly/precisely discuss differences between (0) Trying to prove $\neg\mathrm{Con}(\mathrm{PA})$. (1) Trying to exhibit an actual contradiction in $\...
2
votes
2answers
196 views

Decomposition into primes in Peano arithmetic.

The language of first-order Peano arithmetic seems to me rather limited. As far as I am aware, you have only the symbols $S, 0, +, \times ,= $. Now the theorem of unique factorization into primes, ...
0
votes
2answers
156 views

Questions about Peano axioms and second-order logic

I have what I hope are some simple questions regarding the Peano axioms. I am reading Terence Tao's book "Analysis 1" where he constructs the natural numbers using the Peano axioms, but the axioms are ...
0
votes
1answer
229 views

Peano's Axiom: Is it implied that successor of a number is not the number itself?

Using the Peano's Axioms from MathWorld as the basis, I'm wondering if it is implied that the successor of a number is not the number itself, or is it deducible?
0
votes
1answer
74 views

Prove that it is impossible to define $0$ and “multiplication” on $\Bbb N^2$ such that it becomes a model of **PA** [closed]

Suppose we define addition on $\Bbb N^2$ as $(x_1,x_2)+(y_1,y_2)=(x_1+y_1,x_2+y_2)$. I need to prove that there is no way to define $0$ andd multiplication so that becomes a model of the Peano Axioms ...