Questions tagged [peano-axioms]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
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: ...
3
votes
0answers
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, ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
3answers
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/...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
0answers
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: ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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, ...
6
votes
0answers
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}$-...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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. ...
2
votes
4answers
164 views

How does the Peano axiom of induction prevent S-loops?

First, let me state what I understand to be the first-order rendition of Peano's 5th axiom: the axiom of induction. For all natural numbers, for any relation/property/predicate $R$... $$(R(0) \land \...
0
votes
1answer
41 views

How do we prove there is no natural number between $a$ and its successor $a\texttt{+}\texttt{+}$?

Let $a,b$ be natural numbers. Then $a < b$ if and only if $a\texttt{+}\texttt{+}\leq b$. MY ATTEMPT If $a < b$, we may suppose by contradiction that $a\texttt{+}\texttt{+} > b$. Thus we ...
0
votes
0answers
27 views

For any natural numbers $a,b,c$,prove that associativity of the product $(a\times b)\times c = a\times(b\times c)$.

For any natural numbers $a,b,c$, we have that $(a\times b)\times c = a\times(b\times c)$. MY ATTEMPT We shall prove it by induction on $c$. For $c = 0$, one has that \begin{align*} (a\times b)\times ...
0
votes
0answers
26 views

Prove for natural numbers that $n\times m = 0$ if and only if at least one of $n,m$ is equal zero.

Let $n,m$ be natural numbers. Then $n\times m = 0$ if and only if at least one of $n,m$ is equal zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive. MY ATTEMPT Suppose ...
1
vote
1answer
91 views

Let $m,n$ be natural numbers. Then prove the commutativity of the product $n\times m = m\times n$.

Let $m,n$ be natural numbers. Then $n\times m = m\times n$. MY ATTEMPT (EDIT) Lemma 1 We shall need first the following result: $m\times 0 = 0$. Let us prove it by induction on $m$. Indeed, one ...
2
votes
1answer
69 views

For any natural numbers $a,b,c$, prove the associativity property $(a + b) + c = a + (b + c)$.

For any natural numbers $a,b,c$, we have $(a + b) + c = a + (b + c)$. MY ATTEMPT We shall prove it by induction on $c$. For $c = 0$, we have that $(a + b) + 0 = a + b$ and $a + (b + 0) = a + b$. ...
1
vote
1answer
42 views

Can I do this instead to prove the Strong Principle of Induction (Tao 2.2.14)?

I have already read the following (this one and this one too) discussions on Stack Exchange and they have not answered my query. Proposition 2.2.14 asks the reader to prove that: Proposition $2.2.14$ ...
0
votes
1answer
30 views

Find all functions that compose with the successor function

In Mac Lane/Birkhoff's Algebra, they spend some time discussing the natural numbers and give the Peano Axioms, roughly (from memory) $\sigma$ is injective 0 is not the successor of any element the ...
2
votes
1answer
55 views

Prove the induction axiom via the induction rule

Consider the formal system $P'$ which is the same as $PA$, but without all the induction axioms and with an additional induction rule: If $\vdash A_x[0]$ and $\vdash A\to A_x[Sx]$, then $\vdash A$. ...
3
votes
2answers
84 views

Can proper elementarily equivalent end extensions ever be definable?

Suppose $M\models PA$. Can there be a tuple of formulas $\Psi$ (possibly with parameters from $M$) such that: $\Psi^M\equiv M$ (or more precisely, $\Psi$ is an interpretation of an $\{0,1,+,\cdot,<...
1
vote
1answer
86 views

Is my proof of lemma 2.2.10 (Analysis 1 Tao) correct?

I have recently begun self studying Real Analysis 1 by Tao. Such proofs are new to me and the solutions are not provided in the book. That is why I'm asking this question. Any feedback is welcome, ...
1
vote
1answer
56 views

Is my Peano Axiom proof correct?

I have recently begun reading Terry Tao's Real Analysis 1. The Peano Axiom proofs in the book are very new to me. Because of this, I have little intuition as to whether my proofs are correct. In ...
6
votes
1answer
134 views

Dedekind-infinite objects and NNO in an elementary topos

Let $\mathcal{E}$ be an elementary topos. Call an object $X\in \mathcal{E}$ Dedekind-infinite when it admits a monic but not epi endomorphism. I wonder if in an elementary topos the existence of ...
1
vote
1answer
33 views

How does one prove that Peano Arithmetic can represent all partially computable functions?

I'm interested in establishing that for any partially computable $k$-ary function $f$ there exists a formula $\Phi$ with $k+1$ free variables such that If $f(x_1, \dots, x_k) = y$, then $\Phi(x_1, \...
0
votes
2answers
21 views

Defining positional numeral systems without binary arithmetic operations

Given a totally ordered set of digits $\mathcal{D}$ with cardinality $b\in\mathbb{N}$, least element $d_{\operatorname{min}}\in\mathcal{D}$ and greatest element $d_{\operatorname{max}}\in\mathcal{D}$, ...
0
votes
1answer
46 views

Can this function be described by a formula?

Suppose $PA$ is Peano arithmetic. For $m \in \mathbb{N}$ define $\overline{m}$ as a term in the language of $PA$ using the following recurrence. $$\overline{0} = 0$$ $$\overline{m + 1} = S(\overline{...
0
votes
0answers
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 ...
1
vote
1answer
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. ...
3
votes
2answers
163 views

Strong Induction from Tao

I've already read this, this, and this, and I feel like the answers are only more confusing me more. Definitions and Properties Available: Axioms related to natural numbers: $0 \in \mathbb{N}$ If $...
0
votes
1answer
90 views

Can essential uniqueness justify introducing new constants in a formal system?

Can a positive answer please refer to an elementary exposition, presumably stated in terms of conservative extension of the system with new constants and related axioms? I have not seen this anywhere....
2
votes
3answers
88 views

Proof of existence of unique successor to a positive number

I am studying Terence Tao's Analysis I, 3rd ed., on my own. I am trying to prove the following lemma: Lemma 2.2.10. Let $a$ be a positive number. Then there exists exactly one natural number $b$ ...
5
votes
1answer
85 views

Algebraic number theory in first-order arithmetic

I was inspired to think about how algebraic number theory could be developed in first-order arithmetic, since most developments of ANT do make use of complex numbers. Most of the time such uses of ...
6
votes
1answer
105 views

Alternate definition of the integers

Assuming we have already defined the natural numbers $\mathbb{N}$ and function iteration $f^n$ for a natural number $n$, a set $A$ and a function $f:A\rightarrow A$, do the following axioms (based off ...
3
votes
1answer
35 views

Length of a Deduction

Suppose we have a sentence whose number of of symbols is less than $n$. Assume that this sentence is provable in Peano Arithmetic (with the first-order induction scheme). Also, suppose that we want ...
1
vote
0answers
52 views

Axiomatic natural numbers without induction principle

In the book "Joseph J. Rotman Advanced Modern Algebra" the induction principle is derived by the principle of minimum but not using an axiomatic system of natural numbers. Is it possible to have ...
1
vote
1answer
64 views

Peano axioms without explicit reference to zero

Consider $(N, S)$ with S injective and not surjective and suppose the induction principle holds, where the zero in inductive principle is an element which is not in $S(N)$. Can I prove that $0$ is ...
2
votes
0answers
46 views

What examples of known theorems of PA that were first provable in stronger set theories like Z or ZFC?

Are there known examples of theorems of $\sf PA$ that were first proved in systems vastly more powerful than $\sf PA$, like $\sf ZFC$ for example, and then afterwards the proof of them in $\sf PA$ was ...
2
votes
1answer
58 views

What is the omega-completion of $ACA_0$

The omega rule is an infinitary rule of logic which says that from $\phi(0),\phi(1),\phi(2),...$ you can infer $\forall n\phi(n)$. My question is, what is the theory $T$ obtained by adding the omega ...
0
votes
0answers
52 views

Peano Arithmetic and ZFC

At the suggestion of someone on this forum, I'm reading "Forcing for Mathematicians" by Nik Weaver. I'm on Chapter 2 and the third exercise asks: Give an informal argument that if ZFC is ...
2
votes
2answers
26 views

Am I allowed to substitute terms when reasoning in Peano Arithmetic?

I feel a little silly asking this question, but here goes. I'm on Chapter 1 of "Forcing for Mathematicians" by Nik Weaver and doing some of the exercises. When doing stuff in Peano Arithmetic, can I ...

1
2 3 4 5
14