Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
866
questions
7
votes
0
answers
74
views
Extending a Model of $ T + \operatorname {Con} ( T ) $ to a model of $ T + \neg \operatorname {Con} ( T ) $
Let $ T $ be a recursively axiomatizable extension of $ \mathsf {PA} $ and $ \mathfrak M $ be a model of $ T + \operatorname {Con} ( T ) $. Is it true that there must exist a model $ \mathfrak N $ ...
- 6,401
0
votes
0
answers
42
views
How does consistency PA+¬Con(PA) implies consistency of PA?
There is a question on stack overflow showing that if PA is consistent then PA+¬Con(PA) is also consistent.
The thing is, that it should also work vice versa, that if PA+¬Con(PA) is consistent, then ...
1
vote
2
answers
65
views
Proof of the Principle of Backwards Induction
I'm trying to prove the following proposition, where "++" denotes the successor function (i.e., 2++ = S(2) = 3).
Let $n$ be a natural number, and let $P(m)$ be a property pertaining
to the ...
- 137
0
votes
2
answers
44
views
Peano structure ordering and the recursion theorem circular definitions
Suppose $(P, 0, S)$ is a Peano structure. I am trying to prove the Recursion theorem* and I'm mixed up as to if the recursion theorem needs to be proven first or the order $<$ needs to be defined ...
- 1,172
0
votes
1
answer
58
views
Successor axiom in Robinson arithmetic
The successor axioms of Robinson Arithmetic (Q) are:
$\forall x\,(Sx\neq0)$
$\forall x\forall y\,[(Sx=Sy)\rightarrow x=y]$
$\forall y\,[y=0\;\lor\;\exists x\,(Sx=y)]$
Note that 3. differs from the ...
- 535
1
vote
6
answers
174
views
In the Peano Axioms, how do we know that the successor of a natural number $n$ is $n + 1$? (It's never explicitly stated that it should be "$+1$")
The Peano Axioms never explicitly state that the successor function is $n$ $+ 1$. Is this just taken by convention? It's as if we should already know what the natural numbers are and know that the ...
2
votes
2
answers
111
views
Proof by induction without using inductive hypothesis / Peano Axioms
I thought the following was the case:
In a proof by induction, one must use the inductive hypothesis at some point. Otherwise, the proof is either a) wrong or b) correct yet needn't be written in the ...
- 137
0
votes
1
answer
32
views
standard model of $\mathbb{N}$ and true $\Pi^0_1$ sentences
Does the fact that provability of some true $\Pi^0_1$ sentences is equivalent to the existence of particular (I do not know from the top of my head to which ones, does someone know how they are called)...
- 3,991
0
votes
0
answers
51
views
How can one understand the axiomatization of numbers and their operations?
I've recently taken an interest in arithmetic and how it can be axiomatized. I haven't been reading very deeply about some of the known axioms I've come across, like Peano axioms, which by my ...
- 35
1
vote
1
answer
47
views
An alternative axiom to the peano axiom of induction?
$\def\N{\mathbf{N}}$
The peano axioms:
$0\in\N$
$n\in\N \implies S(n)\in\N$
$\forall n\in\N, S(n)\neq0$
$\forall n,m\in\N, n=m \iff S(n)=S(m)$
$[(0\in X) \wedge(\forall n\in\N, n\in X \implies S(n)\...
- 409
0
votes
0
answers
37
views
why induction is considered as an axiom?
We know that induction principle and well ordered principle of $\mathbb{N}$ are equivalent, so why do mathematicians choose induction to be an axiom and the well ordered to be a consequence, and not ...
- 15
2
votes
1
answer
95
views
Fifth Peano axiom — Properties of the natural numbers
This question is kind of a follow-up question to this. I am also using Terence Tao's book and I still struggle to understand why the fifth Peano axiom is valid.
Tao defines the fifth axiom in the ...
- 155
0
votes
2
answers
41
views
Does this in complete detail prove $\forall x, y \in N, x + (y + 0) = (x + y) + 0$?
My goal is to prove math theorems without skipping any steps. Is this proof correct?
I googled Peano exercises
I found: http://www.public.coe.edu/~jwhite/s11/fndho5.s11.pdf
Question 1 says to prove ...
- 554
0
votes
0
answers
31
views
Proof of $\forall y(Sx + y = S(x + y))$ in Peano Arithmetic.
I am following a proof of $\forall y(Sx + y = S(x + y))$. The base case is $Sx + 0 = S(x + 0)$, and for its proof the author says this:
"If $y = 0$, note that by PA2 ($\forall x x + 0 = x$) we ...
- 485
0
votes
1
answer
44
views
Explicit Substitution in Peano Arithmetic proofs.
I am creating a proof of $S0 \times SS0 = SS0$ in Peano Arithmetic, and a big part of my proof is finding equivalences and then substituting in to relevant formulae. Now I know I can do that with the ...
- 485
-1
votes
2
answers
64
views
Applying Peano Axioms to Subsets of Natural Numbers [duplicate]
Concise Question
Is it possible to apply the Peano axioms to subsets of the natural numbers and thus define arithmetic operations on those subsets strictly in terms of those subsets? If so, is it also ...
- 123
2
votes
2
answers
243
views
Proof in Peano Arithmetic
I am trying to prove $S0 \times SS0$ using the axioms of Peano Arithmetic. The axioms are:
$\forall x \hspace{0.05cm}0 \ne Sx$
$\forall x \forall y \hspace{0.05cm} (Sx = Sy \rightarrow x = y)$
$\...
- 485
0
votes
1
answer
18
views
Is this sequence and its range definable in PA?
Fix a base $b \geq 2$, and consider the sequence $1, 22, 333,$ etc, where we interpret those symbols in base $b$. So, for example, given $b=2$, we have the sequence $1$, $1010_2$, $111111_2$, etc. For ...
- 16.7k
3
votes
1
answer
105
views
Can exponentiation be defined in Robison's Q by use of the exponential Diophantine equation?
Robinson's Q is an axiomatization of arithmetic which only defines addition and multiplication, and does not have the axiom schema of induction (unlike Peano axioms).
I was wondering, given ...
- 2,220
1
vote
1
answer
71
views
What is adding Con(PA) to PA good for?
Is there any non-trivial statement in PA + Con(PA), that was not already in PA? where PA = Peano Arithmetic
The standard model of PA (the basis of number theory) seems to be a model of PA + Con(PA) ...
- 583
1
vote
0
answers
57
views
Peano arithmetic, definitional equivalence and mutual interpretability
I have read in John Corcoran's "Mutual Interpretability is not Definitional Equivalence" (meeting abstract, 1979, p. 430) that the following two "second-order" axiomatizations of ...
- 83
3
votes
1
answer
65
views
Extending empty set + adjunction to interpret PA
Let N = empty set + adjunction. N interprets Q.1 Q + induction yields PA.
Does N + epsilon-induction interpret PA? If so:
Are they mutually interpretable, sententially equivalent, and/or bi-...
- 5,547
0
votes
2
answers
93
views
Which combination of Peano axioms shows that $0\neq 1?$ [closed]
Please vote to close this question. It's really dumb as when I was reading the Peano axioms, axiom 8 didn't register. Don't waste your time reading this question.... I also cannot delete it (I have ...
- 15.4k
1
vote
1
answer
71
views
Why is does this first-order set of axioms NOT genetically define the natural numbers?
It is a theorem of model theory that any recursively enumerable set of axioms $\Gamma$ for number theory permit non-standard models. That is, if there is one model for $\Gamma$, then there are two ...
- 1,043
2
votes
3
answers
125
views
Operation 'Referencing' In Abstract Algebra
I recently started an Abstract Algebra course so I may not know all of the 'necessary' vocabulary to fully express my question, but here is my attempt. First I need to provide some background thinking....
- 31
0
votes
1
answer
73
views
On an alternative definition of addition, $S(a)\ +'\ S(b) = S(a\ +'\ (b\ +'\ 1))$, assuming the first nine Peano axioms.
Full disclaimer: I have edited the question to make it simpler, and therefore some of the comments may no longer make much sense.
Assume we have defined the set $\mathbb{N}$ using the first nine Peano ...
- 15.4k
2
votes
0
answers
52
views
Presburger arithmetic is consistent, but relative to what?
In the Wikipedia article for (the first-order theory of) Presburger arithmetic, it is stated (among other properties) that Presburger arithmetic is consistent. What meta-theory does he rely on in ...
- 65
1
vote
1
answer
50
views
Peano addition commutativity proof by induction
I hope you are already familiar with the five Peano axioms, from which point we use the standard numerals $0,1,2,3,\dots$ as some shorthand notation for each element of our set $\mathbb{N}$. The ...
0
votes
0
answers
40
views
Peano' s Systems
Lets consider $(A,g,a_{0})$ , where $A$ is a set, $g$ is a function and $a_{0}$ is the first element of $A$. If $(A,g,a_{0})$ follows all the Peano's axioms, than we can find an isomorphism f between $...
- 127
1
vote
0
answers
88
views
Induction with an existential quantifier
In short, I am altering the condition in the standard natural number induction principle. I obtain principles such as
$$\forall n. \Big(\big(n=0\lor \exists p. ((Sp=n)\land \phi(p))\big)\to \phi(n))\...
- 11.8k
0
votes
0
answers
69
views
Is Smullyans Axiom System P.E. correct?
Raymond Smullyan in his book on Gödel's incompleteness theorems introduces a certain axiom system for Peano arithmetic with exponentiation (PE, see below). He then shows that under the assumption that ...
- 2,004
0
votes
0
answers
60
views
Why bother constructing the natural numbers from ZFC set theory?
I am learning about classical set theory and how $\mathbb{N}$ can be constructed from sets satisfying ZFC in such a way that the Peano arithmetic axioms are satisfied.
Although the construction is ...
- 1,119
1
vote
2
answers
52
views
Building product in $\Bbb N$ using the function $s: n\mapsto n+1$
using the Peano's axioms we can give a description of the set of natural numbers.
Let's consider the functions
$s: \Bbb N\to \Bbb N$ defined by $s(n)=n+1$
and
$f^n=\begin{cases}
id, &\text{ if } n=...
- 127
0
votes
0
answers
28
views
Reverse mathematics and Peano categoricity, a question
Simpson and Yokoyama in the paper
"Reverse mathematics and Peano categoricity"
Try to show that in RCA0, if weak konig lemma doesn't hold, then Peano categoricity doesn't hold either. This ...
0
votes
0
answers
25
views
What set of properties completely defines the set of natural numbers over addition?
In my spare time, I have been recreationally developing an alternative approach to constructing the natural numbers as sets within ZFC. I have an explicit set which I say behaves like $\mathbb{N}_0$ ...
- 3,970
0
votes
0
answers
49
views
A question about axiom of regularity
I am reading Analysis from Terence Tao.
The Axiom of regularity is defined as follows:
If A is a non-empty set, then there is at least one element x of A which is either not a set, or is disjoint ...
- 41
2
votes
3
answers
288
views
How do I prove that the addition of natural numbers, as defined by Peano, is unique?
In other words, for any two natural numbers, there exist no more than one natural number that equals the sum of the two numbers. Or rather, for any two natural numbers, their sum is unique.
In first ...
- 673
0
votes
0
answers
59
views
What proof system is this paper by Hamano and Okada introducing?
In Hamano and Okada's "A relationship among Gentzen's proof-reduction, Kirby-Paris' hydra game, and Buchholz's hydra game", they briefly introduce a proof calculus for Peano arithmetic, but ...
- 630
0
votes
1
answer
60
views
Godelian sentences in other first order languages
I've been asked to teach an intro to logic and computation course. This is not a field that I am particularly familiar with, but I am happy to have the chance to learn it - hopefully - properly.
Since ...
- 65
2
votes
0
answers
51
views
A Peano system with an infinite initial segment
Let $T$ be a binary tree with the lexicographic order. And $f:T→T$ be the successor operation.
We denote the empty sequence in $T$ by $i$.
Also Suppose that:
For all $X⊂T$ if these two conditions hold:...
0
votes
0
answers
36
views
The set of all finite sequences in RCA0
In the book "subsystems of second order arithmetic", page 68, Simpson claimed that the set of all codes of finite sequences (denoted by "Seq") exists by sigma 0-0 comprehension. I ...
3
votes
0
answers
29
views
In RCA0, Prove that for all n, fⁿ(i) exists
I wanted to prove in RCA0 that:
If f:A→A be a function and i∈A, then for all n, fⁿ(i) exists.
To reach that, I proved another theorem. I wrote my proof but I'm not sure it's rigorous. If you read it, ...
0
votes
0
answers
35
views
A confusion about ω-incompleteness and proof by induction
I faced with a phenomenon called ω-incompleteness of a theory T, which means that for all n, T can prove that P(n) holds, but it can't prove "∀n P(n)".
So, my question is, in a first order ...
0
votes
1
answer
51
views
Does Z₂ Prove the iteration theorem?
iteration theorem:
Let (ℕ,0,S) be the structure of natural numbers. And let W be an arbitrary set and c be an arbitrary member of W and g be a function from W into W. Then, there is a unique function ...
1
vote
2
answers
54
views
Assuming the following definition of the addition of natural numbers, how do I prove that $\forall a:0+a=a$
Natural numbers and the succesor function S are defined according to the Peano axioms.
Addition is defined recursively (DIFFERENTLY from the traditional Peano definition, though I am trying to prove ...
- 673
1
vote
0
answers
68
views
Peano arithmetic without addition
Take the usual theory of First Order Peano Arithmetic with the signature $(0, s, +, \times)$. Now consider these two questions:
Take the set of PA theorems which don't involve '$\times$'. Is there a ...
- 51.1k
3
votes
0
answers
67
views
non-constructive existence of a number
We have shown in my logic lecture that PA (and even the weaker subsystem Q) are complete with respect to $\Sigma_0^1$-Sätzen. A $\Sigma_0^1$-Satz is a closed formula of the form $\exists v_0\exists ...
- 2,721
1
vote
0
answers
35
views
What is the importance of Peano categoricity?
We know that Dedekind in 1888 proved that second order peano arithmetic(PA2) is categorical. My question is, why is it important? Does it have any mathematical, philosophical or foundamental ...
1
vote
0
answers
28
views
Peano categoricity is equivalent to weak konig lemma
Peano categoricity (PC) says that:
Every model for second order peano system is isomorphic to standard model.
i.e PC says that every peano system such as
(A, f, i) is isomorphic to (N, S, 0).
Simpson ...
0
votes
1
answer
37
views
Can I use a addition table with infinite length and height to define addition on the natural numbers rather than Peano's Axioms? [closed]
I'm reading David Steward's "Foundations of Mathematics" and in chapter 8 he is building an axiomatic system for the natural numbers with addition defined using Peano's Axioms. I don't ...
- 3