All Questions
Tagged with peano-axioms logic
436
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
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
-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
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
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
0
votes
2
answers
143
views
Help me check my proof of the cancellation law for natural numbers (without trichotomy)
can you guys help me check the fleshed out logic of 'my' proof of the cancellation law for the natural numbers? It's in Peano's system of the natural numbers with the recursive definitions of addition ...
- 171