# Questions tagged [peano-axioms]

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

653 questions
Filter by
Sorted by
Tagged with
7 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 some parts (in different colors) that confuse me/which I don't understand: For the red part: ...
41 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, ...
69 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 ...
19 views

### What's the proof theoretic ordinal of this number-set theory?

I was thinking of defining a number-set theory, that is a theory that uses the primitives of equality, strict smaller than, and set membership, in order to coin a theory that is at least as strong as ...
18 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 ...
35 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 ...
23 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 ...
94 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/...
37 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 ...
30 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 ...
44 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 ...
34 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: ...
30 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 ...
29 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 ...
19 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 ...
30 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, ...
116 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 set of $\mathcal{L}$-...
72 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 ...
62 views

### A question about Dedekind-infinite sets and Peano natural integers.

I've doubt about Dedekind-infinite sets, sets which are in bijection with a proper part, in the ZF axiomatic framework, without Axiom of Choice. Assume a Dedekind-infinite set X exists. Then it can ...
79 views

### A fundamental question about relations between axioms

In mathematics, there are several sets of axioms. For example, we have ZFC axioms, Peano axioms, Hilbert's axioms of Euclidean geometry(https://en.wikipedia.org/wiki/Hilbert%27s_axioms), and so on. ...
164 views

18 views

### Higher Order Provability Statements Over A Given Sentence

If I have a sentence $S$ over $\mathrm{PA}$ (or some similar theory which can encode FOL), I can look at the set $X_S$ which contains $S$ and is closed under the standard logical connectives as well ...
46 views

### Why is a single nonnegative number smaller than a sum of nonnegative numbers?

I know this sounds like an incredibly dumb question, but why is a single nonnegative number smaller than a sum of nonnegative numbers in a vector? I know it's true, but I want to know why it's true. ...
163 views