Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
879
questions
2
votes
1
answer
67
views
$\omega$-consistency in Goedel's completeness
To prove $PA\not\vdash \lnot \Delta$, where $\Delta$ is the Goedel's sentence, satisfying:
$$PA\vdash \Delta\leftrightarrow \lnot Prv(\overline{\Delta})$$
Why cannot we say: If $PA\vdash \lnot \Delta$,...
- 4,223
-1
votes
0
answers
48
views
Gödel Incompleteness theorems - gap between first order logic and arithmetic
I have a doubt concerning Gödel's incompleteness theorem which might be stupid but that makes me uneasy. If I'm not mistaken, Gödels proof is broadly undertaken using first order formulas, numbering ...
5
votes
1
answer
81
views
Decidable but incomplete arithmetical theories?
There are celebrated examples of theories that are both decidable and incomplete (the theory of algebraically closed fields, various toy theories with only finite models). But are there any examples ...
- 93
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
2
answers
109
views
Proof of Gödels first incompleteness theorem (as in Kunen)
On page 40 in Kunens "Set Theory An Introduction to Independence Proofs", we are given the following theorem:
Gödel. If $\phi(x)$ is any formula with one free variable, $x$, then there is a ...
- 1,286
4
votes
1
answer
587
views
Busy Beaver argument and Gödel's incompleteness theorem
By Gödel's incompleteness theorem, it should not be possible to prove the consistency of ZFC within ZFC (if it is consistent).
It is well known that the Busy Beaver function is uncomputable, and that ...
- 159
3
votes
1
answer
112
views
Gödel theorem as mentionned in Hartshorne's Geometry: Euclid and Beyond
I am reading Geometry: Euclid and Beyond by R. Hartshorne and there is a section discussing the possible axiomatizations for planar geometry. In the following paragraph, Hartshorne mentions Gödel's ...
- 785
0
votes
1
answer
134
views
Interpretation of Godel's incompleteness theorem [closed]
Godel's incompleteness theorem states "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e. there are statements of the ...
- 2,280
1
vote
1
answer
96
views
Arithmetic content of proofs [closed]
Using some variant of Gödel numbering, we can turn mathematical propositions into integers (say $m$). The existence of a proof of such a statement can then be formulated in an arithmetic way, ...
- 785
2
votes
1
answer
142
views
Does this correctly describe how Gödel's First Incompleteness Theorem is proved?
One encounters in books and YouTube videos various ways of describing Gödel's Incompleteness Theorems and their proof. My background is not at all in formal logic, and I want to check if my ...
- 337
2
votes
1
answer
175
views
Why is Gödel's Incompleteness Theorem relevant to anything beyond self-referential statements?
I feel like I understand the general idea behind how Gödel used self-reference to prove that there will always be holes in logical systems, even if you add the self-referential statement to the axioms ...
- 29
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
-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
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