Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
653
questions
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 ...
