# Questions tagged [peano-axioms]

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

875 questions
Filter by
Sorted by
Tagged with
93 views

### How do you understand $a\times1=a$ in Peano axioms?

How do you understand $a\times1=a$ in Peano axioms? This should be understood as replacing $1$ with $a$? For example, when we multiply $3$ by $2$, that means: replace each $1$ in the number three with ...
296 views

### Provably total functions in $\mathsf{Q}$

I was interested in the relations between induction and recursion, and so a natural question (to my mind, anyway), was how much we can prove without appealing to induction, i.e. which functions are ...
• 5,150
246 views

### Show that $(P,S,1)$ is a Peano system if and only if it satisfies the Iteration Theorem

You can skip the first section(hints and useful things) if you want, I will keep editing this along I got more findings related to the question. Hints and useful things: I find out that the book from ...
1 vote
294 views

### Prove trichotomy law of addition in $\mathbb{N}$ (Peano Axioms).

I need help in my proof trichotomy law of addition in $\mathbb{N}$ (Peano Axioms). I have already proved that addition is associative and commutative. Also I proved the cancellation law and some ...
• 3,180
1 vote
152 views

• 369
1 vote
89 views

### Prove the Principle of Complete Induction

The question is stated as: Prove the Principle of Complete Induction $$(\forall B)([B \subseteq P \land (\forall x)((\forall y)(y<x \Rightarrow y \in B)\Rightarrow x \in B)] \Rightarrow P=B)$$ (...
270 views

### Prove that the entire underlying set in a Peano System with the strict order relation($<$) forms a unique strictly ascending sequence

Original question: Prove that $1<2<3<4$,etc in a Peano System That is the definition of Peano system by the used textbook. Peano Systems: By a Peano System we mean a set $P$, a particular ...
200 views

### Kaye-Wong paper Theorem 6.5

In the paper On Interpretations of Arithmetic and Set Theory of Kaye and Wong they say that Theorem 6.5 (that PA can be interpreted in ZF-Inf*, that is, ZF plus every set is contained in a transitive ...
• 1,608
183 views

### Epsilon recursion and ZF-Inf+TC in the Inverse Ackermann Interpretation

In the paper On Interpretations of Arithmetic and Set Theory of Kaye and Wong they write: Equipped with $\in$-induction, we obtain an inverse interpretation of PA in ZF−Inf*. The plan is to define a ...
• 1,608
196 views

• 13
1 vote
275 views

### Function by recursion on a set $X$ satisfy Peano's axioms

I've been stuck on this theorem for like two days and I still don't really get it. I'm reading the construction of natural numbers using "classic set theory for guided independent study", ...
• 686
76 views

### What is a set with a function $f$ that don't satisfy peano's axioms?

I'm reading "classic set theory for guided independent study", and i'm studying the construction of natural numbers using peano's axioms. The three axioms they give me are: A Peano system is ...
• 686
76 views

### Peter Smith's Hilbertian argument

Peter Smith in "An Introduction to Gödel's Theorems" presents a broadly Hilbertian argument (in the sense of Hilbert's program) on page 276 (2nd edition): Theorem 37.2 If $I$ is consistent ...
• 1,608
1 vote
74 views

### Kripke's proof of the incompleteness of PA

In Hillary Putnam's writeup on Kripke's beautiful incompleteness proof of PA, which I learned about from Noah Schweber's answer here, I can convince myself that (see the top of p.56) "$s$ ...
• 1,608
29 views

• 341
86 views

### Every provably recursive function in PA is bounded by a Hardy function

The following lemma and proof are from Takeuti's Proof Theory (2nd edition, pp. 126-127), I've highlighted the problematic part in blue: How does Takeuti get this inequality? If the proof $x$ is not ...
• 1,608
93 views

### Characterization of provably recursive functions in PA

This concerns Takeuti's Proof Theory: the book contains a lot of wonderful material, but the presentation is sometimes lacking (and so many typos!). At least that has been my experience so far, ...
• 1,608
288 views

### While using the method of proof by contradiction, are we "assuming" consistency?

I am aware of threads here and here which asks something similar. However, I had something very specific to ask under the same context. I have a very elementary question about the connection between ...
24 views

### What's the strength of weakening induction in PA by relativizing it to naturals?

If we weaken induction in PA to the following scheme: $\forall m [\phi(0) \land \forall n < m (\phi(n) \to \phi(n+1)) \to \forall n \leq m (\phi(n))]$ Where $\phi$ is any formula in the language ...
• 4,137
69 views

### Proving addition preserves order in natural numbers

I have the following question: Prove $a≥b$ if and only if $a+c≥b+c$ $\forall$ natural numbers. (using Peano Axioms) The solution I checked is different from what I used and same applies to the ones I ...
• 1,801
1 vote
95 views

### When can a statement in Second Order Logic be converted into a statement in First Order Logic

I was reading on first and second order logic (The first has quantifiers over individuals of the domain and the second can have quantifiers over predicates as well - see this question: Differentiating ...
• 425
362 views

### Are mathematical operations axioms?

Are mathematical operations axioms? I will give an example of multiplication, but this also applies to division, subtraction and addition. Idea of multiplication was invented by people to increase/...
262 views

### Exercise 2.2.1 in Analysis by Terence Tao Induction Proof of Addition Associative Law Natural Numbers

The proposition 2.2.5 and also exercise 2.2.1 of Analysis by Terence Tao is as below: Show for any natural numbers $a, b, c$, we have $(a+b)+c = a+(b+c)$ the associative rule The proof should use ...
• 499
46 views

### Defining specific Exponentiation in PA

Given the dictionary {0,1,+,*,<} can I write a simple formula with only x occurs free, that states "x is an exponent of 6"? When I say simple, I mean, without using complicated techniques like ...
1 vote
108 views

### Show that the decidability of a statement is undecidable.

In this system of axioms, it can be shown that A = 5 is undecidable Axioms: A is a prime number, A is greater than 4, A is less than 8 This is because both A = 5 and A = 7 are consistent with these ...
1 vote
48 views

### Proving Natural Predecessor existence using Well Order

I know that the Principle of Induction is equivalent to Well Order at least in Natural Numbers, but I have seen that the demonstration of Induction using Well Order uses the existence of Predecessor: ...
54 views

### Prove trichotomy of order WITHOUT induction?

Claim. If $x,y \in \mathbb N$, then at least one of these is true: (a) $x>y$; (b) $x=y$; or (c) $x<y$. It seems that the usual proof of this claim uses induction. Is it possible to prove this ... 1 vote
164 views

### How do I derive fraction multiplications from Peano axioms

and sorry for the noob questions :) Trying to teach my 10 year old daughter some math and came across the Peano axioms. On the following resource there are two sets of axioms, one is based on symbols ...
• 11
26 views

### Is there a place which has the functional (programming) definition of Numbers in various forms?

I am familiar with the Peano Natural Number definition which is what you see in intro to functional programming courses and examples. But I have also much later encountered a practical implementation ...
• 3,472
96 views

### Peano arithmetic - Why is adding n to m the same as incrementing m n times?

Addition(+) is defined using the successor function(++) in Peano arithmetic as: 0 + m = m (n++) + m = (n + m)++ While these are intuitive axioms that are consistent with my previous, elementary, ... 327 views

### Is there a natural intermediate version of PA?

Below, "logic" means "regular logic containing first-order logic" in the sense of Ebbinghaus/Flum/Thomas. Setup For a logic $\mathcal{L}$, let $\mathcal{PA}(\mathcal{L})$ be the ...
• 229k
105 views

### How to prove $x=5$ using the Peano Axioms?

This question relates to Proposition V of Gödel's 1931 Incompleteness theorem (and another one posted on math.stackexchange here ) which says: For every recursive relation $R(x_{1},...,x_{n})$ there ...
• 541