# Questions tagged [peano-axioms]

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

866 questions
Filter by
Sorted by
Tagged with
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
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
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 ...
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
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
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 ...
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 ...
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
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
47 views

• 485
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
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
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
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 ...
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
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
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
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
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
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
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 ...
40 views

• 127
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 ...
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
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
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 ...
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
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 ...
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:...
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 ...
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, ...
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 ...
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
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
68 views

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