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

learn more… | top users | synonyms

56
votes
13answers
11k views

Can someone explain Gödel's incompleteness theorems in layman terms?

Can you explain it in a fathomable way at high school level?
43
votes
11answers
5k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Godel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
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 ...
34
votes
7answers
2k views

Why is the Continuum Hypothesis (not) true?

I'm making my way through Thomas W Hungerfords's seminal text "Abstract Algebra 2nd Edition w/ Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not ...
20
votes
2answers
1k views

What is the prerequisite knowledge for learning Godel's incompleteness theorem

I am very interested in learning the incompleteness theorem and its proof. But first I must know what things I need to learn first. My current knowledge consists of basic high school education and the ...
16
votes
6answers
2k views

Does Gödel's Incompleteness Theorem really say anything about the limitations of theoretical physics?

Stephen Hawking believes that Gödel's Incompleteness Theorem makes the search for a 'Theory of Everything' impossible. He reasons that because there exist mathematical results that cannot be proven, ...
15
votes
7answers
2k views

True vs. Provable

Gödel's first incompleteness theorem states that "...For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system". What ...
15
votes
1answer
306 views

Could it be that Goldbach conjecture is undecidable?

The result closest to Goldbach conjecture is Chen's theorem [Sci. Sinica 16 157–176], the proposition ``1+2''. It is natural to ask if it is likely that under our arithmetic axioms the Goldbach ...
13
votes
6answers
3k views

Why bother with Mathematics, if Gödel's Incompleteness Theorem is true?

OK, maybe the title is exaggerated, but is it true that the rest of math is just "good enough", or a good approximation of absolute truth - like Newtonian physics compared to general relativity? How ...
13
votes
6answers
2k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
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 ...
11
votes
5answers
1k views

Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?

For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements. My question is, what if one argues that Gödel's Incompleteness Theorem only matters ...
11
votes
2answers
1k views

Examples of statements which are true but not provable

Speaking informally and working, for example, in Peano Arithmetic (PA), we know that the essence of the Gödel's first incompleteness theorem is that there are true statements (in our model PA), which ...
10
votes
2answers
441 views

Is Gödel's incompleteness theorem provable without any model-theoretic notion?

The entry on Gödel's incompletenss theorem in Wikipedia says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, ...
10
votes
1answer
179 views

Problem with completeness theorem and $\mathsf{Con(ZFC)}$

Using the reflection theorem we can prove in $\mathsf{ZFC}$ that for any finite $\Lambda\subseteq\mathsf{ZFC}$ there is some limit ordinal $\gamma$ such that $R(\gamma)\models\Lambda$. Then by the ...
10
votes
1answer
134 views

Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?

I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me. In discussing matters around and about the ...
9
votes
2answers
1k views

Gödel's incompleteness theorem can't be proven?

I have a very simple question, that I still haven't found an answer to yet: Gödel is said to have proven that Peano Arithmetic (or any system capable of expressing it) can't prove its own ...
9
votes
5answers
1k views

What does it mean for something to be true but not provable in peano arithmetic?

Specifically, the Paris-Harrington theorem. In what sense is it true? True in Peano arithmetic but not provable in Peano arithmetic, or true in some other sense?
9
votes
2answers
506 views

Where, specifically, did Principia Mathematica fail?

I'm very fascinated by the book Principia Mathematica. From what I've learned so far, Principia Mathematica set out to be, essentially, the bible of mathematics and logic, from which all mathematical ...
9
votes
3answers
1k views

Consistency of Peano axioms (Hilbert's second problem)?

(Putting aside for the moment that Wikipedia might not be the best source of knowledge.) I just came across this Wikipedia paragraph on the Peano-Axioms: The vast majority of contemporary ...
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 ...
9
votes
3answers
378 views

“The set of all true statements of first order logic”

In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
9
votes
1answer
193 views

Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
9
votes
1answer
208 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
9
votes
1answer
188 views

What was the planned topic of Gödel's second paper on incompleteness?

Gödel's incompleteness theorems first appeared together in a paper titled (translated to English) "On formally undecidable propositions of Principia Mathematica and related systems I," with the Roman ...
9
votes
1answer
285 views

Freeman Dyson's example of an unprovable truth

Freeman Dyson has claimed that $$\nexists m,n \operatorname{Reversed}(2^n) = m ^ 5 $$ (where $\operatorname{Reversed}(l)$ just is the reverse of the digits of $l$ in base 10), is probably an ...
8
votes
6answers
7k views

What is the difference between Completeness and Soundness in first order logic?

Completeness is defined as if given $\Sigma\models\Phi$ then $\Sigma\vdash\Phi$. Meaning if for every truth placement $Z$ in $\Sigma$ we would get $T$, then $\Phi$ also would get $T$. If the previous ...
8
votes
3answers
1k views

Why Euclidean geometry cannot be proved incomplete by Gödel's incompleteness theorems?

Wikipedia mentioned the limitation of Gödel's theorems. According to it, Euclidean geometry doesn't satisfy the hypotheses of Gödel's incompleteness theorems, that is, it cannot define natural ...
8
votes
2answers
633 views

Godel Incompleteness Theorem

Is there any mechanism or algorithm where one can generate mathematical statements/problems that are undecidable, i.e their proof is independent, from a certain set of axioms ?
8
votes
2answers
270 views

Axiomatic system and Hilbert's 2nd problem

Hilbert's second problem asks if the axioms of arithmetic are consistent. Has this problem been resolved? Shouldn't an axiomatic system ideally be consistent and complete(given that we have the ...
8
votes
1answer
314 views

Gödelian incompleteness; Smullyan's Puzzle

I am currently doing exercises on the Gödelian theorems; and we are confronted with the introductory puzzle of R. Smullyan's book, which is as follows: Suppose we have a machine which prints strings ...
8
votes
1answer
165 views

How did Kurt Gödel's Incompleteness Theorem affect the mathematical world?

Hi I am looking not to understand the Incompleteness Theorem, but to find out more about how and what this has effected the mathematics world. I am in high school, in Honors Algebra II, and I am ...
8
votes
0answers
125 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
7
votes
3answers
322 views

Can ZFC decide number theory?

Among the versions of the Incompleteness Theorem that I've seen are the following: Assuming the Peano axioms are consistent (which they are, if we accept the existence of the natural numbers), there ...
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 ...
7
votes
2answers
204 views

How is the standard model of number theory specified, and why can't we use that specification to prove any number theoretical sentence of interest?

According to Gödel's incompleteness theorem, there exists a sentence $G$ in the vocabulary of number theory ($N$) which is not provable from any (recursively enumerable) consistent set of axioms $T$, ...
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; ...
7
votes
2answers
246 views

Proof of Proposition/Theorem V in Gödel's 1931 paper?

Proposition V in Gödel's famous 1931 paper is stated as follows: For every recursive relation $ R(x_{1},...,x_{n})$ there is an n-ary "predicate" $r$ (with "free variables" $u_1,...,u_n$) such that, ...
7
votes
2answers
107 views

Is Goedel term (in incomleteness theorem) both true and unproveable?

In Goedel incompleteness theorem is Goedel term both true and unproveable, or just unproveable and truth neutral? Can we add Goedel term to the theory as axiom and get new theory? Can we add Goedel ...
7
votes
0answers
114 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
6
votes
2answers
246 views

“Completeness modulo Godel sentences”?

So this has been bugging me for roughly four years. When I was an undergraduate, I attended a colloquium in which the speaker was a 'cheerleader' for AD (the axiom of determinacy- an alternative to ...
6
votes
3answers
2k views

are there non-standard models of arithmetic in second order arithmetic?

non-standard models of arithmetic in second order arithmetic? Background: According to Godel's theorem, if we have, in a given consistent system S, a non-provable wff. A, then we can extend the ...
6
votes
1answer
227 views

Are the Godel's incompleteness theorems valid for both classical and intuitionistic logic?

I am studying an undergraduate text about math logic. The proofs of the two Godel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I ...
6
votes
2answers
186 views

What is the notion of truth used in Godels incompleteness theorem?

First-order logic is complete & sound. The notion of truth used here is model-theoretic. Informally Godels incompleteness theorem says that for a sufficiently strong formal language there are ...
6
votes
2answers
313 views

Can an unprovable statement be interpreted as being generally true in some cases?

For example, let's say that Goldbach's conjecture turns out to be unprovable. This would mean that a program cannot devise a way to check whether any counterexample exists. This seems to mean that ...
6
votes
4answers
222 views

Second order logic question.

I'm reading Michael Potter's book "Set Theory and its Philosophy" and where he's explaining why he chose to use first-order predicate calculus with identity instead of second order logic to reason ...
6
votes
2answers
152 views

Formalizing proof of Godel sentence's non-provability?

In the question What does it mean for something to be true but not provable in peano arithmetic? Henning Makholm states, "...he [Godel] gave a (formalizable, with a few additional technical ...
6
votes
1answer
223 views

Best known theory for proving statements about natural numbers

Gödel's incompleteness theorems imply that there is no consistent theory that can be effectively generated and contains all true statements about the natural numbers. Well, what known consistent ...
6
votes
4answers
697 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) ...
6
votes
3answers
149 views

If $T$ proves $\operatorname{Con}(ZFC)$, is $T$ at least as strong as set theory?

I am looking for either a proof of counterexample of this: Lemma: Let $\pi$ be a faithful interpretation of $PA$ into $ZFC$, and let $PA'$ be the image of $PA$ under $\pi$. If there is a $T$ with ...