Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
967
questions
-2
votes
2
answers
280
views
Can we modify the Peano axioms like this? [closed]
I am wondering if the following modifications of the Peano axioms result in a set of axioms equivalent to the Peano axioms, in the sense that any set of numbers satisfies these modified axioms if and ...
1
vote
0
answers
25
views
Order type of cuts satisfying $\mathsf I\Sigma_n$
When $M$ is a model of Peano arithmetic, a cut of $M$ is an initial segment $I$ of $M$ such that $I$ is closed under successor. There is some work on cuts that satisfy $\mathsf I\Sigma_n$, Peano ...
2
votes
0
answers
76
views
Are the models of PA recursively enumerable?
Is there a Turing machine (TM from now on) which lists every model of PA (without the induction axiom schema, so just addition and multiplication)? More specifically, can such a TM list all infinite ...
0
votes
1
answer
71
views
Proving that the set of non-negative half-integers satisfies Peano's axioms
I postulate that the following set $\{0,0.5,1,1.5,...\}$ represents the natural numbers. Of course, intuitively, this isn't true. But let me try to show this using Peano's axioms. I'll first define ...
1
vote
1
answer
53
views
Using Peano's axioms to disprove the existence of self-looping tendencies in natural numbers
Let me clarify by what I mean by "self-looping". So, we know that Peano's axioms use primitive terms like zero, natural number and the successor operation. Now, I want to prove that the ...
2
votes
1
answer
53
views
Peano Arithmetic can prove any finite subset of its axioms is consistent
Timothy Chow writes in a MathOverflow answer
[...] here is a classical fact: for any finite subset of the axioms of PA (remember that PA contains an axiom schema and hence has infinitely many axioms),...
0
votes
2
answers
37
views
Confusion about the validity of the proof of Trichotomy of order for natural numbers in Tao's Analysis
It's well-known that in Tao's Analysis I P28, he provides a provement of Trichotomy of order for natural numbers as follows.
Denote the number of correct propositions among the three (i.e. $a<b,\ ...
-2
votes
1
answer
53
views
Contradiction and Godel's incompleteness theorems
If T is a recursively axiomatizable formal system containing peano arithmetic and is able to carry out the proof for the Godel's incompleteness theorems (so according to Wikipedia includes primitive ...
3
votes
1
answer
140
views
Is Gödels second incompleteness theorem provable within peano arithmetic?
All following notation and assumptions follow Gödel's Theorems and Zermelo's Axioms by Halbeisen and Krapf.
Exercise 11.4 c) states "Conclude that the Second Incompleteness Theorem is provable ...
1
vote
1
answer
161
views
Understanding the Arithmetical Hierarchy
I am trying to get acquainted with the arithmetical hierarchy, and as I wrote down some examples, I got a bit confused.
Consider the language $L=\{+\cdot,<,=,0,1\}$ of $\mathsf{PA}$.
For example, ...
1
vote
1
answer
74
views
Why doesn't $RCA_0$ prove $\Sigma^0_1$-comprehension?
Answer: because that's $ACA_0$, alright, but:
Friedman et al.'s 1983 "Countable algebra and set existence axioms" has [verbatim, including old terminology and dubious notation]:
Lemma 1.6 ($...
0
votes
1
answer
78
views
Is it possible to construct a real number theory on Peano arithmetic?
I know how to construct $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$ from $\mathbb{N}$ in set theory. For example, the construction of $\mathbb{Z}$ is,
$$\mathbb{Z}=\mathbb{N}^2/\sim$$
$$(a, b)\sim(c, d)\...
2
votes
1
answer
72
views
Is there a problem if I don't use $0$ in Peano arithmetic?
Peano arithmetic is the following list of axioms (along with the usual axioms of equality) plus induction schema.
$\forall x \ (0 \neq S ( x ))$
$\forall x, y \ (S( x ) = S( y ) \Rightarrow x = y)$
...
0
votes
3
answers
241
views
Allegedly: the existence of a natural number and successors does not imply, without the Axiom of Infinity, the existence of an infinite set.
The Claim:
From a conversation on Twitter, from someone whom I shall keep anonymous (pronouns he/him though), it was claimed:
[T]he existence of natural numbers and the fact that given a natural ...
3
votes
1
answer
423
views
PA + "(PA + this axiom) is consistent"
By Gödel's second incompleteness theorem, no sufficiently powerful formal system can prove its own consistency.
I was wondering what happens if one tries to manually append an axiom stating a formal ...