Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
1answer
43 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
120 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
66 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
162 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
83 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
52 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
46 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
55 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
96 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
243 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
128 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
67 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
167 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
117 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
95 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
106 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
57 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
60 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
208 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
84 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
124 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
55 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
101 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
93 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
81 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
228 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
997 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
294 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
187 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
48 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
323 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
130 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
81 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
70 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
176 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
146 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
54 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
134 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
119 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
36 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 ...
1
vote
1answer
94 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
913 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
248 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
31 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
423 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
84 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 ...
0
votes
1answer
60 views

$PA \vdash \forall x(S(S(S…(S(x))…))) \neq \bar{0} $

I sign $\bar{k}$ the elements in $\mathbb{N}$ model for $PA$, and I use $\neq$ instead of $\neg(a=b)$ andd $S^n(x)$ as $S(S(...S(x))))$ just for convenience. I was trying to show $PA\vdash \forall x(...
0
votes
1answer
53 views

Peano axioms and Herbrand's theorem

We denote the Peano axioms with $\mathsf {PA}$ and $S=\{0,1,+,\cdot,<\}$ denotes the language of number theory. Let $\varphi$ be the formula $$(1+1)\cdot v_2\equiv(v_0+v_1)\cdot(v_0+v_1+1)+(1+1)\...