Questions tagged [peano-axioms]

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

Filter by
Sorted by
Tagged with
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 $ ...
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 ...
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 ...
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)\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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

1
2 3 4 5
18