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 ...
