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

learn more… | top users | synonyms

30
votes
6answers
1k 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 ...
30
votes
5answers
5k 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 ...
47
votes
13answers
5k views

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

Can you explain it in a fathomable way at high school level?
9
votes
5answers
907 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?
11
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
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 ...
13
votes
6answers
1k 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 ...
7
votes
1answer
373 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; ...
4
votes
3answers
322 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 ...
6
votes
5answers
5k 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 ...
10
votes
2answers
631 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 ...
8
votes
3answers
961 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
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 ...
3
votes
2answers
193 views

Proving and understanding the Fixed point lemma (Diagonal Lemma) in Logic - used in proof of Godel's incompleteness theorem

http://en.wikipedia.org/wiki/Diagonal_lemma I am wondering about the proof of the "Fixed-Point Lemma" $\text{Mod } \Sigma$ is the class of all models of $ \Sigma$. $\text{Th Mod } \Sigma$ is the set ...
5
votes
1answer
91 views

Impossibility of theories proving consistency of each other?

By Godel's second incompleteness theorem, a consistent theory (to which the theorem applies) cannot prove itself consistent. I learned that it's also impossible to have a pair of consistent theories ...
5
votes
3answers
445 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 ...
3
votes
1answer
169 views

System with infinite number of axioms

Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic ...
2
votes
1answer
311 views

Gödel's Incompleteness Theorem - Diagonal Lemma

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $\phi$ that spoke about itself? Can't this formula be built this way: ...
9
votes
1answer
188 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 ...
6
votes
2answers
113 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 ...
5
votes
2answers
117 views

Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
5
votes
3answers
160 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
3
votes
1answer
48 views

The effects of requiring a recursive vs. a recursively enumberable axiomatization in the incompleteness theorem

I believe that the (paraphrased) original statement of Gödels first incompleteness theorem (including Rosser's trick) is If T is a sufficiently strong recursive axiomatization of the natural ...
3
votes
1answer
80 views

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
2
votes
1answer
173 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 ...
2
votes
1answer
416 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 ...