Questions about Gödel's incompleteness theorems and related topics.

learn more… | top users | synonyms

7
votes
3answers
1k views

Prove Gödel's incompleteness theorem using halting problem

How can you prove Gödel's incompleteness theorem from the halting problem? Is it really possible to prove the full theorem? If so, what are the differences between original proof and proof by ...
6
votes
4answers
698 views

A naive inquiry of Godel's incompleteness--or why does mathematics need proofs of unprovability?

My question stems from reading Swetz, 1994 (mostly excerpts from the journal Mathematics Teacher) and Berlinski, 2005 (a popular book on 10 most important mathematical breakthroughs in history). 1) ...
2
votes
1answer
183 views

Construction of a sequence of theorems with increasing and unbounded “difficulty”?

Let's define the "difficulty" of a theorem as the logarithm of the size of its shortest proof divided by the logarithm of the size of the theorem itself. For example, if a theorem has difficulty less ...
9
votes
2answers
263 views

How to show the existence of an infinite set of independent undecidable sentences?

How to show the existence of an infinite set of independent undecidable sentences? By "independent" I mean that no implication between any two elements is provable. A finite set that satisfies the ...
5
votes
3answers
663 views

P vs NP and Gödel

I apologize for the, perhaps, silly question. My impression, as a layman, is that Gödel Incompleteness Theorem should rule out the possibility that P=NP. Is that true or there are deeper technical ...
12
votes
1answer
427 views

What's the theory in which incompleteness of PA is proved?

Maybe this is a dumb question, but I have to admit that it is not really clear to me what the theory is, in which incompleteness of PA and stronger theories is proved. The texts I did study so far are ...
1
vote
1answer
300 views

Why is Godel's first theorem not a proof from the inside?

Why is Godel's first theorem not a proof for the truth of the so called undecidable proposition? You may say it's a proof from the outside, but if not all proofs from the outside be formalized inside ...
36
votes
5answers
6k views

Understanding Gödel's Incompleteness Theorem

I am trying very hard to understand Gödel's Incompleteness Theorem. I am really interested in what it says about axiomatic languages, but I have some questions: Gödel's theorem is proved based on ...
3
votes
1answer
444 views

Is Robinson Arithmetic complete and not-complete?

Is Robinson Arithmetic complete in the sense of Gödels completeness theorem? And is Robinson Arithmetic incomplete in the sense of Gödels first incompleteness theorem? If RA is both it would be a good ...
7
votes
1answer
396 views

Can Robinson's Q prove Presburger arithmetic consistent?

I made an assertion in What are some examples of theories stronger than Presburger Arithmetic but weaker than Peano Arithmetic? that Q has higher consistency strength than Pres, Presburger arithmetic; ...