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

learn more… | top users | synonyms

0
votes
1answer
36 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
3
votes
1answer
120 views

What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...
6
votes
2answers
378 views

Gödel's (in)completeness theorems and the axiomatization of Euclidean geometry

In David Hilbert's 1899 Grundlagen der Geometrie, Hilbert gives a rigorous axiomatization of Euclidean geometry. As I understand it, some of Hilbert's axioms must be expressed in second order logic ...
9
votes
1answer
181 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 ...
4
votes
3answers
560 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 ...
1
vote
2answers
124 views

Question about computability of true/provable formulas

I would like to clarify some things related to the computability of the sets of all theorems and true formulas for the formal arithmetic. Consider the theory $T$ of formal arithmetic (the theory of ...
5
votes
3answers
1k 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 ...
2
votes
2answers
150 views

What does the completeness of a system mean for the provability of certain statments?

Through the 16th to 19th centuries mathematicians tried to prove the Euclids parallel postulate from Euclid's other four postulates. In the beginning of the 19th century the mathematics community ...
11
votes
2answers
738 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 ...
0
votes
1answer
82 views

How can a statement be known to be undecidable in ZFC without ZFC being inconsistent?

I'm attempting to understand the answer to the question, Is there a statement whose undecidability is undecidable (as in independent, not a decision problem)? The answer appears to be "Yes". However, ...
7
votes
0answers
118 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 ...
2
votes
1answer
135 views

Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
1
vote
2answers
74 views

Is this possibility ruled out by Godel's Incompleteness Theorem?

From Wikipedia: "The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any ...
1
vote
1answer
137 views

Questions on a sentence in ZFC asserting that ZFC has a model

Question 1. Let $\operatorname{con}(\mathsf{ZFC})$ be a sentence in $\mathsf{ZFC}$ asserting that $\mathsf{ZFC}$ has a model. Let $S$ be the theory $\mathsf{ZFC}+\operatorname{con}(\mathsf{ZFC})$. ...
2
votes
1answer
79 views

Expressibility; Incompleteness of Peano Arithmetic

I'm working through Peter Smith's book, 'An Introduction to Godel's Theorems'. One small issue I've encountered is how the notion of expressibility is used to prove the incompleteness of Peano ...
8
votes
1answer
306 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
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 ...
5
votes
1answer
167 views

Explain/illustrate Goedel's theorems and possible implications to non-mathematicians

I am asked to give a talk about (a) mathematical practice, (b) axiomatization, (c) Gödel's theorems and (d) possible antimechanist arguments based on the incompleteness theorems (as mentioned in P ...
15
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, ...
6
votes
2answers
139 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 ...
1
vote
1answer
42 views

Can we determine which statements are incomplete due to Godel?

Due to Godel's incompleteness theorems we know that there are true statements in a system that cannot be proven with that system. My questions are 1) can we tell which statements in a system are the ...
49
votes
13answers
8k views

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

Can you explain it in a fathomable way at high school level?
5
votes
1answer
103 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
618 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 ...
5
votes
4answers
147 views

Is every theorem of PA true in the standard model of number theory $N$?

My understanding is that every theorem $\phi$ of $PA$ is true in $N$ because $N$ is a model for $PA$, $N\models PA$. By completeness of first order logic, "$PA\vdash\phi$" implies that "if $N\models ...
2
votes
2answers
81 views

Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately ...
9
votes
1answer
271 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 ...
0
votes
1answer
42 views

Are there complete formal systems?

I am relatively new to logic, so forgive my ignorance. My question is: Are there any formal systems that are deemed complete? If so, how did we prove they were complete and which are they?
2
votes
1answer
42 views

Completeness of a Sub Theory of Number Theory

When I was an undergraduate I had a philosophy professor tell me that if you took the axioms of number theory with only addition or only multiplication then the resulting theory was decidable. It is ...
0
votes
1answer
91 views

differentiate the terms deductive system, model/structure, formal system, first-order logic

I can not bring the terms deductive system, model/structure, formal system, first-order logic into order in my head ;-) It seems to me that they are not overly used in a consistent manner and ...
2
votes
0answers
83 views

Minimal number of variables in a ZFC-undecidable sentence?

Let $\phi$ be a sentence of set theory. In Prenex form, $\phi$ can be written $$ {\bf Q}_1 x_1 {\bf Q}_2 x_2 \ldots {\bf Q}_n x_n \ \ \psi(x_1,x_2, \ldots ,x_n) $$ where each ${\mathbf Q}_i$ 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 ...
2
votes
5answers
739 views

Are (some) axioms “unprovable truths” of Godel's Incompleteness Theorem?

Like any math newbie, Godel's Incompleteness Theorems are easy to understand in general layman's terms, but difficult to understand beyond the typical "liar's paradox" and "barber's paradox" type ...
10
votes
1answer
160 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 ...
2
votes
1answer
55 views

Are forcing techniques possible to automate for mechanized reasoning?

Looking at Cohen's success at proving independence of the Axiom of Choice and the Continuum Hypothesis, I was wondering if it was possible to mechanize forcing techniques for the purpose of proving ...
6
votes
2answers
178 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 ...
2
votes
2answers
71 views

Completeness condition in Gödel first incompleteness theorem superflous

Wikipedia says: Theory is complete if it is a maximal consistent set of sentences. Than it says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both ...
3
votes
1answer
83 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 ...
1
vote
1answer
178 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 ...
5
votes
2answers
280 views

$\omega$-consistency and related terms

We know that a theory $T$ is $\omega$-inconsistent if there is a formula $\psi$ such that $T$ proves $(\exists x)\psi(x)$, and $T$ also proves $\lnot \psi(n)$ separately for each standard natural ...
1
vote
1answer
81 views

Have I understood the whole Incompleteness business correctly?

I am reading Gödel-Escher-Bach and a good dialogue by Eliezer Yudkowsky and I think I might have understood the nature of the Completeness and Incompleteness theorems (at least regarding Peano ...
2
votes
1answer
76 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 ...
5
votes
2answers
123 views

Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
9
votes
2answers
466 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 ...
1
vote
3answers
107 views

On consistency of axiomatic systems

Can an axiomatic system (which is capable of expressing arithmetic) be complete and consistent? Let me explain my motivation a little bit (though it can be a kind of a mess...) I'm aware of Goedel's ...
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 ...
6
votes
1answer
206 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 ...
3
votes
2answers
307 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 ...
0
votes
1answer
49 views

Definability of Kolmogorov Complexity?

This paper claims to have a proof of Godel's Second Incompleteness Theorem using Kolmogorov Complexity: http://www.ams.org/notices/201011/rtx101101454p.pdf As far as I can tell, it seems to assume ...
4
votes
1answer
190 views

How to prove primitive recursive functions are definable in Peano Arithmetic?

Background: I'm working on a talk that presents Godel's first Incompleteness Theorem from a computability-theoretic perspective. The idea is to show that the first incompleteness theorem follows from ...