Questions tagged [peano-axioms]

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

Filter by
Sorted by
Tagged with
1
vote
4answers
282 views

How do Peano Axioms imply “nextness” with the successor?

Going with this explanation of Peano's Axioms, I cannot understand how/where the successor function is definitively stated to be the very next number in the case of natural numbers. In this treatment, ...
0
votes
0answers
41 views

Why natural numbers are generalized in $\mathbb{Z}$ to ensure the group structure respect to the sum?

The natural numbers $\mathbb{N}$ are defined through the Peano axioms and then generalized in $\mathbb{Z}$ to ensure the group structure with respect to the sum. Why do we need to ensure such group ...
0
votes
1answer
49 views

Is this sufficient to prove the associativity of natural number addition?

This question is regarding the same proposition as is discussed in How should this proof of the associativity of natural number addition be understood? Here I wish to ask if a much simpler proof than ...
1
vote
0answers
154 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 ...
2
votes
0answers
77 views

A property of representable functions?

Recall that a function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is representable in Peano arithmetic if there exists a formula $\varphi(x_1,\dots ,x_k,y)$ such that for every $n_1,\dots,n_k,m\in\mathbb{N}...
2
votes
3answers
223 views

Peano Axiom Proofs: Proving $a < b$, if and only if $a + + \leq b$

As for where I am getting my Peano Axioms, its from Terrance Tao's Analysis I text (math.unm.edu/~crisp/courses/math401/tao.pdf). I am unsure whether my proof is correct for proving the forward ...
1
vote
1answer
84 views

$a < b$ and $c<d$ imply $a+c < b+d$

$a < b$ and $c<d$ imply $a+c < b+d$ when $a,b,c,d$ are arbitrary nonnegative integers. I know that (assuming we include zero) $$\begin{align*} a<b \Leftrightarrow (\exists x\in \mathbb ...
1
vote
1answer
63 views

Is Peano arithmetic complete for quantifier free formulas and strict arithmetical formulas?

By a quantifier free arithmetical sentence I mean a fully quantified sentence in the language of Peano arithemtic $``PA"$, in prenex normal form having no existential quantifier. By a strict ...
0
votes
0answers
62 views

Show that first order Peano's axioms capture the natural numbers regarding satisfiablity

Denote be $\mathcal P_{MO}$ the set of the monadic second order axioms of Peano. Then as shown by Dedekind any two model are isomorphic to $\mathbb N$. Hence for a monadic second order sentence we ...
1
vote
1answer
87 views

Induction with two variables in PA

This probably has been asked before, but apologies, I don't know how to locate it. I want to prove $\forall x,y: P(x, y)$. My premises are: $$P(0, 0) \wedge \\ [\forall x: P(x, 0)] \wedge \\ [\...
2
votes
1answer
273 views

proof of formula with Peano-axioms

For all natural numbers n define $\Delta_n$ as: $\Delta_0$ is the constant $0$ and $\Delta_{n+1}$ is $S(\Delta_n)$. Here is S the function for the follower, i.e. $\forall x: S(x) = x+1$. 1)I want ...
4
votes
1answer
626 views

Difference between first and second order induction?

Can anyone explain the difference between induction as it's stated in first order logic and that from second order logic? I don't understand the difference as it pertains to things like Peano axioms.
4
votes
0answers
175 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 ...
1
vote
1answer
36 views

Why do we need the following set to have an infinite set?

By Dedekind's definition: Definition: We say that some set $S$ is infinite if there exists an injection $f:S\rightarrow S$ such that $\operatorname{Im}(f)\neq S$ (or $f(S)\neq S)$. Now, the book ...
4
votes
1answer
77 views

Definition of nonstandard models without enumerations

To define nonstandard models of Peano arithmetic or set theory, many articles use enumerations like $x>0, x>1, \dots$ where $x$ is said to be a nonstandard natural number, ie a number that is ...
1
vote
1answer
305 views

What is the best book to learn Peano Arithmetic

My goal is to develop an automated proof program for Peano arithmetic. I want to know as much proofs as possible in this system for both my mathematical culture and to enrich the database of my future ...
2
votes
1answer
217 views

Can we prove that the peano axioms are true for $(\mathbb N, \sigma)$ in type theory?

In mathematical logic that I'm used to (i.e. we have first-order formulas and a sequent calculus to derive formula's from axioms), we never prove that the peano axioms are true for the natural numbers,...
1
vote
2answers
113 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 ...
4
votes
1answer
191 views

Well-orders on non-standard models of Peano arithmetic

The standard model of Peano's arithmetic, $\mathbb{N}$, has the useful property that the order $\leq$ is a well-order. However, being a well-order cannot be expressed in the language of first-order ...
2
votes
1answer
86 views

Can every true arithmetical sentence be proved from the first-order Peano arithmetic system?

Consider the first-order Peano Arithmetic axioms (which consist of the standard succesor, addition and multiplication axioms, along with first-order induction axioms, as detailed in Wikipedia). This ...
0
votes
1answer
185 views

Bijection between two Peano triples.

Let $(P_1, \sigma_1, s_1)$ and $(P_2, \sigma_2, s_2)$ be two Peano triples. Can we show that there exists a bijection $g:P_1 \to P_2$ such that $g(\sigma_1) = \sigma_2$ and $g \circ s_1 = s_2 \circ g$...
-2
votes
2answers
333 views

Does Gödel's incompleteness theorem invoke a Law of Excluded Middle contradiction? [closed]

Does Gödel's incompleteness theorem cause the Law of Non Contradiction to contradict its self? If so, would this be a considered a conjecture?
0
votes
0answers
101 views

Why Presburger arithmetic cannot prove pigeonhole principle

The pigeonhole principle is the scheme $\forall \bar{a},s \{\forall x\!<\!s\!+\!1 \exists y\!<\!s\psi(x,y,\bar{a}) \to \exists x_1,x_2\!<\!s\!+\!1\exists y\!<\!s[x_1\neq x_2 \wedge \psi(...
1
vote
1answer
200 views

Existence of Natural Numbers as an Axiom

By natural numbers $\mathbb{N}$ I understand any set satisfying Peano axioms: $0 \in \mathbb{N}$ $\sigma : \mathbb{N} \to \mathbb{N}$ $\forall n \in \mathbb{N} \; . \; \sigma(n) \neq 0$ $\forall n,m \...
0
votes
1answer
65 views

What is Complete Induction without Hypothesis?: Ordering of $\mathbb{N}$ from Peano's Axioms

The following is from Fundamentals of Mathematics, Volume 1 Foundations of Mathematics: The Real Number System and Algebra; Edited by H. Behnke, F. Bachmann, K. Fladt, W. Suess and H. Kunle I've used ...
1
vote
1answer
138 views

Do induction axioms of Peano Arithmetic have other simple equivalent forms?

For the example of Presburger Arithmetic, which consists of basic axioms for successor, addition, as well as an infinite set of induction axioms. However, it is well known that Presburger Arithmetic ...
0
votes
1answer
163 views

Proving well ordering principle from PMI (PCI) from peano axioms

Axiomatically, set $\mathbb{N}$ is constructed via injective function $s:\mathbb{N}\rightarrow \mathbb{N}$ and an element $1\in\mathbb{N}$ and we have that $\forall n\in\mathbb{N}:s(n)\neq1$. Together ...
0
votes
0answers
18 views

Proving the addition law for equality, eg. $+$ is compatible with $=$ on $\mathbb{N}$

Using following definition of addition (Peano arithmetic): Definition:$+:\Bbb{N}\times\Bbb{N}\rightarrow \Bbb{N}$ $$\forall a\in\mathbb{N}:a+1=s(a)\tag{i}$$ $$\forall a,b\in\mathbb{N}:a+s(b)=s(...
0
votes
1answer
93 views

Proving the commutative law for 1-based $\Bbb{N}$

We will work with $1$-based natural numbers, that is $0\notin\Bbb{N}$. Let $s:\Bbb{N}\rightarrow\Bbb{N}$ be the function axiomatically given in peano axioms, we define addition and multiplication as ...
1
vote
1answer
372 views

Inductive proof using Fitch software

I am trying to prove the integer square root theorem $\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land (x < (y+1)^2))$ for $\lfloor \sqrt{x} \rfloor$. In words: for any natural ...
7
votes
3answers
1k views

George Boolos and Gödel's Second Incompleteness Theorem

In Mind, Vol. 103, January 1994, pp. 1-3, George Boolos wrote: And so on. In fact, if a claim can be proved, then it can be proved that the claim can be proved. And that too can be proved. ...
7
votes
1answer
537 views

Is Fermat's last theorem provable in Peano arithmetic?

The sentence $S$ which Gödel in his proof of the incompleteness theorem proves to be be unprovable in the system of Peano arithmetic can be proved (as a true theorem of PA) outside PA (and necessarily ...
5
votes
1answer
619 views

What's the relationship between ZFC and Peano axioms? Are they overlapping, complementary or separate?

What's the relationship between ZFC and Peano axioms? Are they overlapping, complementary or separate? I'm particularly wondering whether natural number stuff like order can expressed in ZFC at all. ...
0
votes
2answers
66 views

Proof of induction from higher starting point

I'd like to request to verify this proof that for a arbitrary natural $n_0$ this holds: $[C(n_0+1) $ and $\forall n>n_0 : C (n) \implies C (n+1)] \implies \forall n> n_0 : C (n) $ ($C (n)$ means ...
19
votes
1answer
365 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 ...
2
votes
1answer
157 views

Goedel's first incompleteness theorem, the omega rule, and Tennant's reflection rule

Typical discussions of Goedel's first incompleteness theorem note that PA can prove of each integer that it doesn't number the proof of the Goedel sentence $G$. They then note that using an omega rule ...
1
vote
1answer
202 views

Multiplication cancellation property by Peano axioms

I am trying to prove cancellation property of multiplication of natural numbers, $xy=xz$ implies $y=z$, with Peano axioms and arithmetic but not using or defining order on natural numbers. It can be ...
2
votes
1answer
109 views

Mathematical Induction: First vs. Second order Induction Axiom

The second-order variables in the second order Induction Axiom of (second order) Peano Arithmetic range over the set of all subsets of the natural numbers, that is, it has uncountable cardinality. ...
5
votes
1answer
231 views

Understanding and proving prop 2.1.16 in Tao's Analysis I concerning recursive definitions

Notes: Tao's axioms and original proposition statement and proof are given below. Similar questions have been asked here and here, but I was not able to resolve my issues. In particular, I have ...
3
votes
1answer
202 views

What if someone comes up with a proof of consistency of arithmetic under the following conditions?

Suppose that one day, someone comes up with a proof of consistency of Peano arithmetic (PA) within itself. Then, does it mean that PA is actually inconsistent? Because, by the Gödel's incompleteness ...
5
votes
1answer
62 views

Research areas in Peano arithmetics

So I recently just finished a course on Peano arithmetics and it's non-standard models. I am very much intrigue by this topic. Hence I am rather curious what are some research areas surrounding PA ...
1
vote
2answers
219 views

How can I prove this proposition from Peano Axioms: (Cancellation law). Let a, b, c be natural numbers such that a + b = a + c. Then we have b = c.

Peano Axioms. Axiom 2.1 $0$ is a natural number. Axiom 2.2 If $n$ is a natural number then $n++$ is also a natural number. (Here $n++$ denotes the successor of $n$ and previously ...
0
votes
2answers
224 views

How to prove the generalized associative law for addition on $\mathbb N$?

Let $(a_1,\cdots,a_n)$ where $n>3$ be a finite sequence in $\mathbb N$. Then there is a sequence $(s_1,\cdots,s_n)$ such that $s_1=a_1$ and $s_{i+1}=s_i+a_{i+1}$ for all $1\leq i<n$ (I proved ...
1
vote
1answer
37 views

Would a proof predicate change if a stronger system used despite sharing language?

This is a follow-up question from Proof predicate in PA and stronger system Suppose that two theories $T_1$ and $T_2$ share the same language - thus only axioms differ such that $T_2$ is a stronger ...
2
votes
1answer
120 views

Proof predicate in PA and stronger system

It is said that proof predicate of PA is primitive recursive, but I cannot find explicit form of the proof predicate, or how it is defined. What is this proof predicate? What about defining for other ...
3
votes
3answers
1k views

Order of the natural numbers

The set of natural numbers as given from the Peano axioms $(N,S)$ has an order. I saw in wikipedia that $(N,+)$ is a commutative monoid, but since the naturals have an order structure by ...
2
votes
3answers
346 views

Does countable induction over $\mathbb N$ require the axiom of infinity?

Consider ordinary induction over $\mathbb N$: Proving $P(0)$ Assume $P(k)$ being true for some natural $k$ Prove $P(k+1)$ Does this require the existence of $\mathbb N$ and hence the ...
0
votes
0answers
39 views

Deciding whether sets of Godel's number is recursive.

let $\alpha$ be a sentence (closed formula) in number theory language, such that $PA\nvdash\neg\alpha$. For any sentence $\beta$ , let us denote $g(\beta)$ as $\beta$'s Godel number. We define the ...
2
votes
4answers
576 views

“No infinite descending membership chains”, Peano Axioms, Axiom of Regularity

I use ZFC with the axiom of Regularity. At page 62 of my notes I prove that "There is no infinite descending membership chains" (because of well-ordering of $\mathbb{N}_0$), The Lemma "No infinite ...
0
votes
1answer
86 views

$\forall k,n \in\mathbb N:k\in n\iff k\subsetneq n$ [Proof Verification and Suggestion for shorter or simpler proof]

I'm not sure if my below proof contains subtle errors that I'm unable to recognize. Please have a check on it! Furthermore, I found that my proof is long. Please suggest me any simpler or shorter ...

1 2 3
4
5
14