Questions tagged [peano-axioms]
For questions on Peano axioms, a set of axioms for the natural numbers.
967
questions
1
vote
0
answers
82
views
Godel's incompleteness theorem: Question about effective axiomatization
I am studying Godel incompleteness theorems and I am struggling with the definition of effective axiomatization.
From Wikipedia:
A formal system is said to be effectively axiomatized (also called
...
- 2,452
0
votes
0
answers
41
views
Understanding Peano Arithmatic and Axioms
I am new to analysis and started reading a PDF I found on Reddit, the link is here.
I stumbled on a few question about basic Peano axioms and the definitions that the PDF derived from it.
In case ...
- 151
0
votes
0
answers
28
views
Proving the existence of hyperoperations in a Peano system
In Mendelson's "Number Systems" he defines and subsequently proves the existence and uniqueness of binary operators $+$ and $\times$, as well as exponentiation, in $P$ using the so-called ...
1
vote
0
answers
35
views
Why is the material conditional treated like logical entailment in second order quantification? [closed]
According to this Wikipedia article the second order axiom of induction is: $$\forall P(P(0)\land \forall k(P(k) \to P(k+1)) \to \forall x(N(x) \to P(x))$$
Where N(x) means x is a natural number. That ...
- 301
0
votes
0
answers
31
views
Finite axiomatization of EFA
According to the paper Fragments of Peano's Arithmetic and the MRDP theorem (Section 6), elementary function arithmetic (EFA) is finitely axiomatizable.
Is there a known explicite finite ...
user1343124
-3
votes
1
answer
64
views
Naive Set Theory - proof of commutativity of products
I am working through Halmos's Naive Set Theory on my own and trying to do all the exercises, including what are merely suggestions in the text. I am right now in section 13, which shows a derivation ...
0
votes
1
answer
37
views
Ability of Peano axiom with integer set?
Axioms:
Peano Axioms (defines natural number, introducing 0 and ')
For each predicate φ, there exist exactly one set X, s.t. forall x, φ(x) <=> x∈X.
So, it's possible to define less-than in ...
- 229
0
votes
2
answers
77
views
Axiomatic reason why $a=4 \implies a>1$ for $a \in \mathbb{N}$
This is a trivial task:
Given $a \in \mathbb{N}$ and $$a=4$$
Show $$a > 1$$
Part of the challenge for newcomers like me is that "easy" tasks actually make it harder to think about the ...
- 3,325
0
votes
1
answer
47
views
not precisely understanding what is asked by ex 3.5.13 Tao Analysis I (only one natural number system)
I am failing to understand the intent of the question posed by exercise 3.5.13 of Tao's Analysis I 4th ed.
The purpose of this exercise is to show that there is essentially only one version of the ...
- 3,325
2
votes
2
answers
76
views
Proof that each natural number has a unique successor
I've proven that every positive natural number has a unique predecessor using Peano's axioms. But now, I was wondering how I could prove that every natural number has a unique successor using the same ...
- 283
-1
votes
2
answers
159
views
How to justify why succession and addition cannot be circularly defined like this?
I am reading Tao's Analysis I, in which he states:
One
may be tempted to [define the successor of $n$ as] $n + 1$. . . but this would introduce a circularity in our foundations, since the notion of ...
- 3,019
-2
votes
2
answers
152
views
Why is addition not completely defined here?
Say for the natural numbers, we define addition this way:
$0 + 0 = 0$, and if $n+m = x$, then $S(n) + m = n+S(m) = S(x) $
Say we have the regular Peano axioms, except we delete the axiom of ...
- 3,019
0
votes
0
answers
30
views
Question about the Peano axioms + linear order axioms
The signature consists of $S$, $0$ & $<$ and the axioms are:
I - $\forall x (S(x) \not= 0)$
II - $\forall x \forall y (S(x) = S(y) \to x = y)$
III - First-order Induction schema
IV - $<$ is ...
- 446
2
votes
2
answers
134
views
Is it circular to include reachability from $0$ like this as a Peano axiom?
I am wondering whether it makes logical and semantic sense to include, as an axiom to define the natural numbers, that "every natural number is either $0$ or the result of potentially repeated ...
- 3,019
3
votes
1
answer
60
views
Specific example of a property $P$ that Peano arithmetic proves holds true for every specific number, but not for all numbers.
Can someone give a specific example, if there is any, of a predicate $P(x)$ expressible in the language of Peano arithmetic, such that the first-order theory of Peano Arithmetic proves $P(0)$, $P(1)$, ...
- 21.4k
-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 ...
- 3,019
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 ...
- 1,311
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 ...
- 283
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 ...
- 283
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),...
- 4,886
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 ...
- 171
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, ...
- 4,432
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 ($...
- 1,084
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)\...
- 103
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)$
...
- 103
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 ...
- 45.7k
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 ...
- 3,054