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

learn more… | top users | synonyms

3
votes
2answers
214 views

The Penrose–Lucas argument

I was looking at the Penrose–Lucas argument as discussed on Wikipedia. It states: In 1931, the mathematician and logician Kurt Gödel proved that any effectively generated theory capable of ...
1
vote
1answer
161 views

Definition and meaning of “Proof Schema”, “Class Sign”

I'm a newbie in advanced mathematics, and I'm trying to understand Godel's theorem. I came across these two words which I couldn't understand clearly. "Proof Schema" and "Class-Sign" Can anybody ...
5
votes
1answer
395 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 ...
9
votes
1answer
276 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 ...
2
votes
1answer
347 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: ...
0
votes
1answer
484 views

Gödel Incompleteness Theorem - Primitive Recursive Functions

I'm currently studying Gödel's Incompleteness Theorem and I am in doubt about his use of primitive recursive functions. To study it, i'm in the point of view of a system of predicate logic with the ...
1
vote
1answer
183 views

Consequences of Incompleteness.

Suppose that I'm a working mathematician that has just proved a Theorem, say, in Number Theory. Does Gödel's Incompleteness Theorem imply that I can't know for sure if there exists a proof of the ...
0
votes
1answer
348 views

Consistent but incomplete formal axiomatic systems

Is there any known consistent but incomplete formal axiomatic system apart of and simpler than one "capable of doing arithmetic"? Is it even possible? Even if this capability of arithmetic were a ...
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 ...
4
votes
0answers
86 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 ...
1
vote
2answers
204 views

Is this incompleteness result easier to get than incompleteness of PA?

Gödel's theorem for Peano Arithmetic shows that (under consistency hypothesis on PA) there is a statement which cannot be proved or disproved within PA that is true under the standard model ...
1
vote
2answers
161 views

How can you add 'not G' to a formal system without introducing omega inconsistency?

In any formal system S that is susceptible to Godel's proof, we can make a formula G which is undecidable. That should mean that we can add either $G$ or $\neg G$ as an axiom to S and still end up ...
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 ...
2
votes
1answer
171 views

Differences between between concepts related to Gödel's Incompleteness theorems: self-referencing, diagonalization and fixed point theorem?

I am studying the proof of Gödel's first Incompleteness theorem at the moment and I don't understand the differences between self-referencing, diagonalization and fixed point related to Gödel's proof. ...
0
votes
1answer
132 views

Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$

Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this ...
6
votes
2answers
243 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 ...
1
vote
1answer
113 views

Relationship between $\Sigma_{1}$ and $\Pi_{1}$ functions (Logic)

I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked. Is the converse of Theorem $13.1$ true? Explain. Theorem ...
5
votes
1answer
165 views

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?

There is a recursive definition of the set of squares which uses only addition: $CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$ $IS(x)⇔ x=0 ...
7
votes
3answers
317 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 ...
2
votes
2answers
375 views

How it is posible that $\omega$-inconsistency does not lead to inconsistency

After wikipedia: Theory is $\omega$-inconsistent if, for some property P of natural numbers, T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) ...
1
vote
4answers
885 views

Consistency VS Inconsistency , semantics and syntactics

What does it mean when we say that a set of formulas , Sigma , is Consistent , or Inconsistent ? Is ...
6
votes
5answers
6k 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 ...
3
votes
1answer
302 views

About Godel Incompleteness and Multiplication

Godel proved that every system strong enough to include standard arithmetic with multiplication is incomplete. But I've read that systems that do not include multiplication are complete. But ...
1
vote
1answer
256 views

Use of undecidability

Suppose someone proved that the Goldbach conjecture was undecidable in an axiomatic system that is consistent as far as we know. Then in some sense we know that Goldbach conjecture must be "true", ...
5
votes
1answer
285 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 ...
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 ...
2
votes
1answer
155 views

Why does the existence of independent statements not prove consistency?

I've read before that, by the Principle of Explosion, if a theory is inconsistent, then absolutely any statement can be proven within it. Obviously, there are statements which are independent of ZFC ...
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 ...
4
votes
1answer
163 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 ...
2
votes
1answer
232 views

How to express Con(PA) as a first-order statement?

I read from somewhere that Fact 1. PA, which refers to the first-order version, is not finitely axiomatizable. At the same time, the second incompleteness theorem says that there is no proof in ...
1
vote
1answer
164 views

Quantitative version of Godel's incompleteness theorem

Let $A$ be a list of axioms which we assume to be sound (for example, PA or ZFC). Godel's incompleteness theorems imply that if we add only finitely many (true) axioms to $A$, the new list $B$ will ...
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 ...
2
votes
2answers
1k views

Explanation of proof of Gödel's Second Incompleteness Theorem

I am looking for a simple explanation/outline of the proof of Gödel's Second Incompleteness Theorem, and I haven't yet been able to find anything that is within my grasp. I'm looking for something ...
4
votes
3answers
603 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 ...
6
votes
1answer
222 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 ...
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 ...
6
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
681 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
643 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
425 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
296 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 ...
35
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
438 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
393 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; ...