# Questions tagged [peano-axioms]

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

561 questions
1answer
77 views

### Is there an error in this proof the the “strong induction” theorem? Is this Escherian logic?

By set predicates, I mean the "tests for inclusion" used in defining sets. That may be more of a computer scientific than mathematical use of the the term predicate. I included predicate logic in ...
1answer
42 views

1answer
36 views

### Peano axioms: S(1)=1?

I was reading through the Peano axioms here, and a question came up: Can we define $S(0)=1$, and $S(1)=1$? It seems to me (at least as it is stated) that it would satisfy all of the axioms listed. ...
1answer
32 views

### Terminology: arithmetic vs. expressible vs. represented

A function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is arithmetic iff its graph is arithmetic, i.e., there is a formula $\psi(\vec{x},y)$ in the language of Peano arithmetic such that for all $\vec{a}$ ...
2answers
47 views

### Proof of cancellation law for multiplication of natural numbers.

The cancellation law for the multiplication of natural numbers is: $$\forall m, n\in\mathbb N, \forall p\in\mathbb N-\{0\}, m\cdot p=n\cdot p\Rightarrow m=n.$$ Is it possible to show this using ...
3answers
194 views

### Are there “interesting” theorems in Peano arithmetic, that only use the addition operation?

More precisely, are there "interesting" theorems of Presburger arithmetic, other than the following four well-known "interesting" ones? The commutativity of addition. The theorem stating there are ...
1answer
65 views

### Do Gödel's incompleteness theorems apply to finitist axiomatic systems that reject the axiom of infinity?

I'm curious which axiomatic frameworks Gödel's incompleteness theorems apply. Do the theorems apply to any axiomatic system that adopts potential infinity? Or just to those that adopt completed ...
2answers
89 views

1answer
66 views

### Peano axioms and commutativity of addition

I'm trying to prove the commutativity of addition in Peano arithmetic in something like a natural deduction system, but am stuck halfway (I say "something like a natural deduction system" because I ...
4answers
132 views

### Proving $a\ne{b}\implies{a<b}\lor{b<a}$ for natural numbers beginning with 1 using Peano's Axioms without induction hypothesis

Here, I am asking specifically about a proof which does not use an induction hypothesis, and which relies exclusively on Peano's axioms as stated herein. My interest is not in simply producing the ...
1answer
59 views

### Peano axioms: prove that there is no natural number between n and sucessor of n

Let $m \in \mathbb{N}$. Show that $\nexists n \in \mathbb{N}$ such that $m < n < s(m)$, where $s$ is the successor function. Here's my proof using only the Peano Axioms I was introduced. I'd ...
2answers
95 views

### How to prove that first-order PA proves the consistency of each of its finite sub-theories?

The locus classicus of this theorem (the ''reflexivity'' of PA) is Mostowski's 1952 On models of axiomatic systems. I freely admit that I can't read the rather archaic formalism of this paper. Is ...
0answers
55 views

### Nonstandard proof codes for Con(PA)

Note: This question is inspired by a paper being discussed in the FoM mailing list. The formal statement Con(PA) is a statement about the existence of a proof code for the derivation of a ...
1answer
88 views

### Is the 'copy' of the naturals in ZF a unique way to represent the second-order arithmetic in first-order logic?

The following line of thought came into me while studying introductory logic and set theory. I feel like there is an error in it somewhere, but I can't point it. It might even be correct. We have the ...
1answer
23 views

1answer
28 views

### Peano axiom of induction- why cannot it be replaced by something simpler?

The Peano axiom of induction for natural numbers says that For any property $P(n)$ , if $P(0)$ holds, and that whenever $P(n)$ holds, $P(n++)$ holds, then $P(n)$ holds for all natural numbers. Can ...
0answers
57 views

0answers
145 views

### How did mathematicans prove things before ZFC or Peano

I do not get it. How was a+b=b+a or a (b +c) = ab + ac proved by ancient mathematicians before set theory or Peano axioms? If you cannot logically prove the laws of arithmetic without Peano or set ...
0answers
55 views

### Axiomatizing a “bounded” companion to PA

There's nothing special about PA here, I'm just focusing on it since it's strong enough to ignore lots of minor technical issues around foundations. If switching to some other theory would yield a ...
2answers
53 views

### A (quantifier-free) is true in standard model of PA ==> PA |- A ??

Is the following statement correct ? A is a formula in PA without a quantifier and A is true for the standard model of arithmetic, i.e. the model |N = (N,+,×,0,1,<) This means: |N |= A ==> A is ...
1answer
39 views

### Is it necessary to prove uniqueness of Peano addition?

If we define addition as follows: Define $a+0=a$. For all $a,b\in\mathbb N$ such that $a+b$ is defined, define $a+S(b)=S(a+b)$. It's easy to show through induction that this defines addition for all ...
1answer
112 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, ...
4answers
114 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, ...
0answers
39 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 ...
1answer
43 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 ...
0answers
119 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 ...
0answers
65 views

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}... 3answers 159 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 ...