Questions about Gödel's incompleteness theorems and related topics.
28
votes
5answers
4k 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 ...
21
votes
6answers
779 views
Why is the Continuum Hypothesis (not) true?
I'm making my way through Peter J. Cameron's seminal text "Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not exist a set with a cardinality less ...
13
votes
7answers
1k 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 ...
12
votes
4answers
611 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, ...
11
votes
6answers
972 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 ...
11
votes
1answer
342 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 ...
10
votes
6answers
2k 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 ...
10
votes
5answers
720 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 ...
10
votes
3answers
436 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 ...
9
votes
2answers
940 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
572 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
242 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
1answer
135 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
101 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 ...
8
votes
2answers
179 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 ...
7
votes
2answers
674 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 ...
7
votes
3answers
274 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
201 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 ...
7
votes
2answers
175 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
0answers
140 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 ...
6
votes
3answers
919 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
4answers
104 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
1answer
197 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
3answers
130 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 ...
6
votes
1answer
320 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; ...
6
votes
2answers
75 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 ...
5
votes
2answers
197 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 ...
5
votes
1answer
259 views
Is there any direct application of Gödel's Theorems outside of logic?
Gödel's incompleteness theorems was a major achievement with ramifications outside the field of mathematics itself. Are there any direct applications of the theorem(s), or any of the methods pioneered ...
5
votes
3answers
299 views
Is the negation of the Gödel sentence always unprovable too?
The incompleteness theorem says that certain theories+deduction system contain at least one sentence (the Gödel sentence "$G$"), which can't be proven (in the system in which it holds).
(i) Is ...
5
votes
4answers
539 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) ...
5
votes
3answers
210 views
An ignorant question about the incompleteness theorem
Let me preface this by saying that I have essentially no background in logic, an I apologize in advance if this question is unintelligent. Perhaps the correct answer to my question is "go look it up ...
5
votes
1answer
62 views
How many digits of Chaitin's $\Omega$ constant would we know if we had a $\Sigma_1$-Oracle?
According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this ...
5
votes
1answer
136 views
Is every φ above the second level of the arithmetical hierarchy independent of PA?
If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
5
votes
1answer
193 views
Completeness of Real Number Arithmetic?
I've recently read that, although Godel Incompleteness holds for the theory of natural numbers, the theory of the real numbers is actually complete. So, why is Godel's Theorem still
considered ...
4
votes
6answers
440 views
prove that it's not provable
Is it possible to prove that you can't prove some theorem? For example: Prove that you can't prove the rieman hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in ...
4
votes
4answers
2k 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 ...
4
votes
3answers
405 views
P vs NP and Goedel
I apologize for the, perhaps, silly question. My impression, as a layman, is that Godel Incompleteness Theorem should rule out the possibility that P=NP. Is that true or there are deeper technical ...
4
votes
3answers
627 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 ...
4
votes
2answers
115 views
Sequent calculus and first incompletness theorem
Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
4
votes
1answer
91 views
Understanding the syntactical completeness
A formal system is syntactically complete if for each sentence
(closed formula) $\varphi$ either $\varphi$ or $\lnot \varphi$ is
provable.
A formal system is semantically complete if every ...
4
votes
1answer
53 views
Special undecidability situation
Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). Can one construct two
statements $\phi_1$ and $\phi_2$ such that
$$
ZFC' \vdash ((ZFC \vdash \phi_1) \ \text{or} \ (ZFC \vdash \phi_2))
$$
...
4
votes
1answer
103 views
Question about $\Sigma_n$-soundness
According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
4
votes
1answer
136 views
Does robinson arithmetic satisfy modal logic's “axiom 4”?
Does Robinson arithmetic prove the theorem "if sigma is provable then 'sigma is provable' is provable' for a fixed sentence sigma?
It's clear to me that you can get a primitive recursive function f ...
4
votes
0answers
118 views
Freeman Dyson's example of an unproveable truth
Freeman Dyson has claimed that
$\not \exists m,n Reversed(2^n) = m ^ 5 $
(where Reversed(l) just is the reverse of the digits of l in base 10), is probably an example of an unproveable truth ...
4
votes
0answers
68 views
An “internal” condition on $T$ so that for the standard provability predicate, $T$ proves $\text{Pf}(\underline S)$ implies $T$ proves $S$?
This is probably quite basic, but I'd like to make sure I got this right. Regarding the proof of Goedel's first incompleteness theorem, say that we have $T$ containing $PA$ effectively axiomatizable ...
3
votes
1answer
142 views
Are Real Numbers axioms a consistent or complete system?
Do we know if the axioms of the real numbers are consistent, complete or neither of both?
And if so, is it a consequence of Godel's theorem or of something else?
3
votes
3answers
251 views
Aftermath of the incompletness theorem proof
This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure:
So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at ...
3
votes
4answers
597 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 ...
3
votes
2answers
86 views
Does $\Sigma_1 \cup \Pi_1$ generate the complete first order theory of arithmetic?
If a set $T$ of sentences in the language of arithmetic
is deductively closed under the usual inference rules of first order logic, and
includes all true $\Sigma_1$ sentences and all true $\Pi_1$ ...
3
votes
5answers
241 views
Gödel says: countable proofs, uncountable conjectures?
I thought I understood Gödel's Incompleteness Theorem to say:
Starting from ZF, there only a countable number of proofs you can write
The number of possible conjectures is uncountable.
Thus, ...
