Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
160
questions with no upvoted or accepted answers
7
votes
0
answers
2k
views
Proving the trichotomy of order for the natural numbers
Is my proof correct?
The trichotomy of order for natural numbers states: Let $a,b$ be natural numbers. Then exactly one of the following statements is true:
I. $a < b$
II. $a = b$
III. $a > ...
- 5,333
6
votes
0
answers
163
views
To what degree are arbitrary true statements about the natural numbers provable?
Gödel's First Incompleteness Theorem states that if we have a recursive and consistent set of axioms $A$ in $\mathcal{L}_{\text{NT}}$, then there is a true first order statement about natural numbers $...
- 1,047
6
votes
0
answers
80
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 ...
- 229k
5
votes
0
answers
114
views
Can ZFC decide more values of the Busy Beaver function than PA?
This is related to a previous question. In that question, I asked whether ZFC can define the Busy Beaver function. I was told even Peano Arithmetic(PA) can define it, and also that PA can't decide ...
- 16.8k
5
votes
0
answers
393
views
Independence of First-Order Peano Axioms
In class was given these 7 (first-order) axioms of Peano arithmetic (the + denotes successor):
NT1 $\quad(\forall x) \neg\left(x^{+}=\overline{0}\right)$
NT2 $\quad(\forall x)(\forall y)\left(x^{+}=y^...
- 828
4
votes
0
answers
112
views
Is there a least standard model of Peano Arithmetics?
Here's the informal part: I'm trying to get a better intuition about the differences between the standard model and the non-standard ones. Some people seem to be really good at imagining what non-...
- 41
4
votes
0
answers
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
4
votes
0
answers
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
4
votes
0
answers
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
4
votes
0
answers
287
views
Algebraically Constructing the Natural Numbers Using a Binary Operation Satisfying Some Properties
Here is the proposed theory:
Definition: Let $M$ be a nonempty set with a binary operation $+$ satisfying the following properties:
P-0: The operation $+: M \times M \to M$ is both associative and ...
- 11k
4
votes
1
answer
96
views
Can bounded addition and multiplication be computable in a non-standard model of arithmetic?
Let $M = (N, \oplus, \otimes, <_M, 0_M, 1_M)$ be a nonstandard model of peano arithmetic. $\oplus$ and $\otimes$ are uncomputable due to Tennenbaum's theorem.
For $c \in N$, let $\oplus_{<c}, \...
- 9,837
4
votes
0
answers
130
views
Is there a weak set theory that can prove that the natural numbers is a model of PA?
$ZFC$ proves that $\mathbb N$ is a model of $PA$. Even $ZF$ does. How weak can go?
In particular, is there some weak set theory that proves that $\mathbb N$ is a model of $PA$, but does not proof ...
- 9,837
4
votes
0
answers
116
views
Show that there are only $\aleph_0$ many countable models of the following theory.
Consider a language $L$ with $<0,1,S>$, where $S$ is the successor function.
Show that there are only $\aleph_0$ many countable models of Th$(\mathbb{N})$, under $L$.
This is one of the ...
- 2,097
4
votes
0
answers
305
views
Proving there is a unique binary operation we call multiplication
The following is a theorem from the book The Real Numbers and Real Analysis by Bloch which I am currently self-studying. I am pretty sure my proof for uniqueness is correct, but I am wondering is ...
- 201
4
votes
0
answers
736
views
True statements about natural numbers that are undecidable in Peano Arithmetic assuming consistency of PA only
I am looking for statements $P$ of Peano Arithmetic ($\textsf{PA}$) that have the following properties:
They are as concrete and simple as possible.
It is provable by finitistic means that neither $P$...
- 18.4k
4
votes
1
answer
298
views
What is one set of axioms which are sufficient for Calculus?
I am curious to find out what are the "minimum axioms" needed in order to be able to have highschool level math. Another way to explain it: if we were visited by a super intelligent race of aliens (...
- 22.7k
3
votes
0
answers
31
views
In RCA0, Prove that for all n, fⁿ(i) exists
I wanted to prove in RCA0 that:
If f:A→A be a function and i∈A, then for all n, fⁿ(i) exists.
To reach that, I proved another theorem. I wrote my proof but I'm not sure it's rigorous. If you read it, ...
3
votes
0
answers
67
views
non-constructive existence of a number
We have shown in my logic lecture that PA (and even the weaker subsystem Q) are complete with respect to $\Sigma_0^1$-Sätzen. A $\Sigma_0^1$-Satz is a closed formula of the form $\exists v_0\exists ...
- 3,126
3
votes
0
answers
210
views
Which sentences are irreducibly self-referential?
Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers.
Now asked at MO.
Say that a sentence $\varphi$ ...
- 229k
3
votes
0
answers
51
views
Soundness for first order
While reading the book by Peter Smith I came across two different definitions of soundness, the general definition
A theory $T$ is sound iff its axioms are true (on the interpretation built
into T’s ...
- 2,029
3
votes
0
answers
52
views
Proving a result similar to the diagonal lemma/fixed-point theorem
As the title explains, I'm trying to solve the following exercise that was left for the reader in my lecture notes:
Show that for any two formulae $F(v_1)$ and $G(v_1)$ in $L_E$ (language of ...
- 31
3
votes
0
answers
203
views
Does the well ordering principle really implies mathematical induction?
Under the Peano Axioms, I want to prove that if the Axiom of Induction is substituted with the well-ordering principle (every non-empty subset of $
\mathbb N$ has a minimum element), everything will ...
- 280
3
votes
0
answers
239
views
Formalization in PA in the Kritchman-Raz proof
In their paper Kritchman and Raz present a proof of Gödel's second theorem using Kolmogorov complexity. To make it work, they operate in some (weak) formal theory $T$ that incorporates some arithmetic,...
- 1,608
3
votes
0
answers
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 ...
3
votes
0
answers
77
views
Concrete examples of statements not provable in PRA + $\epsilon_0$-induction that are provable in PA?
It is well-known that $\mathbf{PRA}$ plus $\epsilon_0$-induction on bounded formulas cannot prove all $\mathbf{PA}$ theorems (essentially because $I\Sigma_1$ plus $\epsilon_0$-induction on bounded ...
- 1,608
3
votes
1
answer
164
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 ...
- 841
3
votes
0
answers
151
views
Mathematical Induction and Peano Arithmetic
Peano Arithmetic cannot employ Induction for any ε0 ordering. My question is too easy to be interesting and there is a reason obviously for why it has a negative answer. Can you please provide it for ...
- 31
3
votes
0
answers
133
views
Let $m,n \in \mathbb{Z}$. Assume $m < n$. Then $m \leq n-1$.
My question is concerning my proof's validity in the theorem written below. If someone could take a moment and see if there is a flaw in it, I'd appreciate it.
Lemma. There are no natural numbers ...
- 3,082
3
votes
0
answers
217
views
Simple addition definition in ZFC
I have to present about the Peano axioms and the ZFC for my introductory seminar. It's one of the first topics presented, so I can't refer to more advance topics like cardinality, the only things ...
- 157
3
votes
1
answer
57
views
The set $T=\{l\in\mathbb{N}: ml=nl \ \text{implies} \ m=n \}$ is inductive.
I'm trying to prove the following statement:
$ml=nl$ implies $m=n$ for every $m,n,l\in \mathbb{N}$.
So I defined the set $T=\{l\in\mathbb{N}: ml=nl \ \text{implies} \ m=n \}$ and if I prove that $...
- 31
3
votes
0
answers
106
views
Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials
I'm stuck at the following exercise:
I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all $\vec{n}...
- 514
3
votes
0
answers
179
views
Any new axioms for the natural numbers since Peano?
Have any axioms in addition to usual 2nd-order Peano axioms been found to significantly extend the class of derivable propositions about natural numbers?
- 13.8k
3
votes
1
answer
124
views
A subalgebra of $P(M, \Delta)$ is a Peano Algebra
Let $M$ be any set and let $\Delta=(n_i)_{i \in I}$ be an algebraic type. Let $P=P(M, \Delta)$ be the algebra such that the generalized Peano Axioms hold:
(P1) $f_{i}(a_0,\dots,a_{n_i-1}) \notin M$;
...
- 439
3
votes
0
answers
375
views
Why Does Induction Prove Multiplication is Commutative?
Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2).
GA has second order induction and a single successor axiom:
$$\forall x \forall y \forall z\bigr((...
- 1,245
2
votes
0
answers
41
views
What does it mean that we need $𝜖_0$ induction to prove PA consistency?
I have started to learn about Peano Arithmetic, and also about ordinals.
In particular, I have seen that the Goodstein theorem is an example of a statement that can be expressed in PA but that ...
- 399
2
votes
0
answers
53
views
Presburger arithmetic is consistent, but relative to what?
In the Wikipedia article for (the first-order theory of) Presburger arithmetic, it is stated (among other properties) that Presburger arithmetic is consistent. What meta-theory does he rely on in ...
- 65
2
votes
0
answers
51
views
A Peano system with an infinite initial segment
Let $T$ be a binary tree with the lexicographic order. And $f:T→T$ be the successor operation.
We denote the empty sequence in $T$ by $i$.
Also Suppose that:
For all $X⊂T$ if these two conditions hold:...
2
votes
0
answers
100
views
Implications of $Q\vdash \lnot Con(Q)$
By Gödel's incompleteness (which holds even for $Q$ as discussed here) we have that the Robinson arithmetic $Q$ is consistent iff $Q+\lnot Con(Q)$ is consistent.
As I understand it, without further ...
- 322
2
votes
0
answers
66
views
Are there any arithmetic statements where there does not exist a proof proving the statement?
Because of Godel's Incompleteness Theorems, there must exist certain statements about the numbers which have no proof via the Peano axioms. This includes The Strengthened Ramsey Theorem.
However, this ...
- 2,948
2
votes
0
answers
54
views
Is the Laws of Form consistent in relation to PA?
G. Spencer-Brown wrote in his book Laws of Form from 1969, that (as you can see in Chapters 9 and 10) his LoF is complete and independent. In fact this proves, that LoF can't deduce paradoxes of the ...
2
votes
0
answers
57
views
Some questions about the proof of backwards mathematical induction
The backwards mathematical induction is Let $n$ be an natural number and $P(m)$ be a property, and if $P(m+1)$ is true, then $P(m)$ is true. The problem is given that $P(n)$ is true, prove $\forall m\...
- 133
2
votes
0
answers
44
views
Is Peano arithmetic considered to be an algebraic structure?
(Sorry if I'm a imprecise in my formulations, I am new to math.)
I recently discovered algebraic structures and they seem quite fundamental, I'm wondering whether Peano arithmetic could be expressed ...
- 21
2
votes
0
answers
104
views
Did all axiomatic systems face a crisis with the discovery of Russell's paradox?
When Bertrand Russell outlined his paradox to Gottlob Frege just as his Grundgesetze was going to print, it effectively destroyed the consistency of Frege's theory of arithmetic. But was this the ...
- 757
2
votes
0
answers
28
views
Proving $PAE ⊢ (Pr_S(\#(X → Y)) → (Pr_S(\#(X)) → Pr_S(\#(Y))))$, where $Pr_S(n)$ holds iff $n$ is the Gödel number of a formula provable from $S$
I'm trying to solve the following question set by my professor:
Show that if $S$ is a definable set of sentences, and $Pr_S$ is an associated proof
predicate, and $X$ and $Y$ are any formulae, then $...
- 21
2
votes
0
answers
301
views
Proof of commutativity of addition using Peano axioms
I'm studying the proof of commutativity of addition using only Peano axioms (with the distinguished element being 0 rather than 1), the definition of addition, and x+0=0+x=x. The main idea is ...
- 21
2
votes
0
answers
263
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
2
votes
0
answers
50
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 ...
- 4,137
2
votes
0
answers
101
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 ...
- 9,852
2
votes
0
answers
93
views
A property of representable functions?
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}...
- 3,287
2
votes
0
answers
79
views
Induction Can't Prove Complexity?
Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
- 1,245