Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
1
vote
1answer
85 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
103 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
27 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
58 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
58 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
78 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
71 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 ...
2
votes
1answer
53 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
47 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
49 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
116 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
65 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
96 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
40 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
64 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
54 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
23 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
161 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
929 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
154 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
74 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
42 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
301 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
107 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 ...
0
votes
0answers
24 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 ...
1
vote
1answer
49 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
153 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
86 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
49 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
69 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
89 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
67 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
820 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
196 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
26 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
342 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
81 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
57 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
45 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)\...
6
votes
4answers
120 views
Does the successor function imply order?
My confusion is how order arises from the Peano axioms (wikipedia link).
From this question I'm not sure that "successor" means "greater than." It seems you could take $\mathbf{0}$ and then the ...
22
votes
5answers
3k views
Why does induction have to be an axiom?
I noticed that there is an axiom that says that if $S(n)\implies S(n+1)$, and $S(1)$ is true, then $\forall n \in \Bbb N, S(n).$
My question is why is this an axiom? why can't we derive this from the ...
1
vote
2answers
36 views
Proof that an injective system with $i\notin\textrm{ran}{f}$ has a Peano subsystem.
I follow this link, in particular Exercise 2 at the bottom of page 3.
Def 1. A System is a tripple $(X,i,f)$, where $X$ is a set, $i$ is called initial element, and $f$ is a function $X\to X$.
Def 2....
4
votes
1answer
53 views
Can bounded addition and multiplication be computable in a non-standard model of arithmetic?
Let $M = (N, \oplus, \otimes, <_M, 0_M, 1_M)$ be a nonstandard model of peano arithmetic. $\oplus$ and $\otimes$ are uncomputable due to Tennenbaum's theorem.
For $c \in N$, let $\oplus_{<c}, \...
0
votes
1answer
49 views
Can second order peano arithmetic prove that first order peano arithmetic is sound? [closed]
Can second order peano arithmetic prove that first order peano arithmetic is sound?
Note that I'm not just talking about its axioms, but also its theorems.
1
vote
1answer
68 views
Is the famous problem number #6 solvable in first order Peano arithmetic?
I just came accross the famous "very difficult" problem 6 of the 1988 International Mathematical Olympiad:
Let $a$ and $b$ be positive integers and $k=\frac{a^2+b^2}{1+ab}$. Show that if $k$ is an ...
1
vote
2answers
233 views
Can Peano Arithmetic show that the Continuum Hypothesis is Independent of ZFC?
Can Peano Arithmetic show that the Continuum Hypothesis is Independent of ZFC? In other words, is $PA \vdash Con(ZFC) \implies Con (ZFC + CH) \land Con(ZFC + \lnot CH)$ true?
I believe the answer is ...
6
votes
2answers
100 views
Can two different models of arithmetic have non-comparable views of peano arithmetic?
For a given model of arithmetic $M$, we say that models view of peano arithmetic, $V(M)$, is $\{\phi : M \models (PA \vdash \phi) \}$.
For example the view of the standard model is $\{\phi : PA \...
3
votes
0answers
100 views
Mathematical Induction and Peano Arithmetic
Peano Arithmetic cannot employ Induction for any ε0 ordering. My question is too easy to be interesting and there is a reason obviously for why it has a negative answer. Can you please provide it for ...
