Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [peano-axioms]

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

3
votes
0answers
62 views

Consistency of PA from a Formalist Perspective

In this lengthy thread there's people bickering back and forth about the consistency of PA (Peano Arithmetic) and misunderstandings abound. In reading it I came to an understanding I found useful, ...
1
vote
3answers
72 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
38 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
76 views

How is induction (without hypothesis) to be used in this proof that $a\ne{b}\implies{a<b\lor{b<a}}$ for $\mathbb{N}$?

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. Süss and H. Kunle. It's part ...
1
vote
1answer
45 views

Is this a logically satisfacotry proof of the associativity of natural number addition?

This is again related to my previous question How should this proof of the associativity of natural number addition be understood? Here the natural numbers are defined as starting with one. Peano's ...
0
votes
1answer
38 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
102 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
58 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
126 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
81 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
38 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
34 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
43 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
86 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 ...
1
vote
1answer
112 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
110 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
29 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
60 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
106 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
85 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
86 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 ...
3
votes
1answer
63 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
53 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
53 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
143 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
67 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
104 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
43 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
70 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
69 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
16 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
41 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
173 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
944 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. ...
6
votes
1answer
199 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 ...
4
votes
1answer
102 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
43 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 ...
17
votes
1answer
307 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
115 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
42 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
57 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
159 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 ...
2
votes
1answer
105 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
50 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
75 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
95 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
32 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 ...
0
votes
1answer
69 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
866 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
211 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 ...