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

learn more… | top users | synonyms

36
votes
7answers
3k 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 ...
43
votes
5answers
8k 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 ...
53
votes
12answers
6k views

What is a simple example of an unprovable statement?

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

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

Can you explain it in a fathomable way at high school level?
19
votes
7answers
3k 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 ...
6
votes
1answer
278 views

Can unprovability unprovable? Is there an $\omega$-fold unprovability?

I was just thinking about unprovability. I just wanted to know if it is possible to make a concrete boundary between provable problems and unprovable problems in a certain axiomatic system. We know ...
14
votes
1answer
549 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 ...
18
votes
6answers
4k 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 ...
14
votes
2answers
2k 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 ...
6
votes
2answers
221 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
417 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 ...
4
votes
3answers
291 views

Concrete example for diagonal lemma

Diagonal lemma says that in a theory with enough assumption for any formula $A(x)$ there exist a sentence $B$ such that $B$ $\iff$ $A(\#(B))$ is a theorem in that theory, in which $\#(B)$ represents ...
14
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 ...
11
votes
2answers
339 views

How to prove that Gödel's Incompleteness Theorems apply to ZFC?

Let us denote Robinson Arithmetic as Q and Primitive Recursive Arithmetic as PRA. Let $T$ be a formal theory formulated in the language of arithmetic. According to this page on the Stanford ...
5
votes
3answers
729 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 ...
-9
votes
2answers
176 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory [closed]

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
7
votes
1answer
80 views

What's wrong with this proof of ZF being inconsistent?

I'm studying (independently) mathematical logic and in investigating self-referential statements I developed a result which I don't know how to interpret. I'll use the notation from Enderton's "A ...
7
votes
1answer
448 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; ...
2
votes
2answers
228 views

clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

I am not quite sure what really is meant when talking about "arithmetics" in context of Gödel's incompleteness theorems. How I so far understand it: Gödel proved that every sufficiently powerful ...
4
votes
3answers
935 views

Classifying Types of Paradoxes: Liar's Paradox, Et Alia

The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false ...
0
votes
2answers
254 views

Undecidable sentence in Godel's incompleteness theorem

In Godel's incompleteness theorem, the undecidable sentence is g: I am not provable. Ok. I accepted it and realized that in satandard interpretation it is true. So we found a true sentence which ...
11
votes
6answers
13k 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 ...
12
votes
2answers
724 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 ...
19
votes
6answers
3k 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, ...
9
votes
3answers
2k 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 ...
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 ...
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
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 ...
3
votes
2answers
776 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 ...
6
votes
5answers
748 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 ...
6
votes
2answers
283 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 ...
4
votes
1answer
324 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 ...
1
vote
1answer
112 views

Reference request for the independence of $ \text{Con}(\mathsf{ZFC}) $.

Gödel’s Second Incompleteness Theorem says that if $ \mathsf{ZFC} $ is consistent, then $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) $, i.e., $ \text{Con}(\mathsf{ZFC}) $ is not provable in $ ...
8
votes
2answers
325 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, ...
5
votes
1answer
129 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 ...
4
votes
1answer
91 views

Integer induction without infinity

In ZFC minus infinity (let us call this T), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals. I am looking for a formula $\psi$ ...
4
votes
3answers
141 views

Why can PA + $\neg G_{PA}$ be consistent?

Wikipedia and other sources claim that $PA +\neg G_{PA}$ can be consistent, where $\neg G_{PA}$ is the Gödel statement for PA. So what is the error in my reasoning? $G_{PA}$ = "$G_{PA}$ is ...
3
votes
1answer
79 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 ...
2
votes
2answers
60 views

Trying to understand self-reference as it relates to Godel's Second Incompleteness Theorem

As noted in this post, I'm trying to understand how a sufficiently powerful consistent theory $T$ can prove statements about itself without contradicting Godel's Second Incompleteness Theorem. Let ...
2
votes
1answer
148 views

What does a Godel sentence actually look like?

My understanding is that Godel's first theorem says that there is a sentence that is in a sense true in a formal system F but cannot be derived in that system. I then hear that Godel actually goes on ...
2
votes
1answer
148 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
2
votes
1answer
92 views

In Godel's first incompleteness theorem, what is the appropriate notion of interpretation function?

Wikipedia states Godel's first incompleteness as follows. Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for ...
2
votes
1answer
455 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: ...
2
votes
1answer
192 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
1answer
219 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
202 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 ...
3
votes
2answers
80 views

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my "proof" of "ZF is inconsistent" was that I was not considering that there are models with non-standard integers. However now I think I ...
3
votes
1answer
148 views

Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
3
votes
1answer
112 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 ...