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

learn more… | top users | synonyms

22
votes
7answers
4k 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 ...
0
votes
1answer
34 views

How to show factorial is recursive?

In my textbook Fact : Given recursive $G:\omega^{n}\rightarrow\omega$ and $H:\omega^{2}\times\omega^{n}\rightarrow\omega$ , a function $F:\omega\times\omega^{n}\rightarrow\omega$ defined by $F(a,...
1
vote
1answer
55 views

understanding gödel's 1931 paper - number theoritical formulae

I am reading a translation of Gödel's original paper about in completeness theorem and there are a couple things i don't understand. Here is the document i am using primarily : http://www.research....
1
vote
0answers
23 views

How to show that F is recursive?

In the road to Godel's incompleteness theorem, Problem saying: Show that Frame For $G:\omega\times\omega\times\omega^{n}\rightarrow\omega$ a recursive function, the function $F:\omega\times\omega^{...
11
votes
1answer
373 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
0
votes
1answer
49 views

Can any statement about natural numbers be written in TNT?

I was trying to understand Godel's theorem from here Godel's First Incompleteness theorem. I still do not completely understand the theorem, but have a broad idea about it. As the link mentions Godel'...
1
vote
1answer
31 views

What is the diagonalization of ‘∀x¬Gdl(x,y)'?

Correct me if I am wrong here.‘∀x¬Gdl(x,y)' simply states that There does not exist godel number for a given number y, right? So if we say that there exist a diagonalization of ‘∀x¬Gdl(x,y)', then we ...
3
votes
1answer
180 views

How to show incompleteness of second order logic?

I'm trying to see/show that second order logic (with full semantics) is incomplete - i.e. that there are sentences that are true in all models of some theory $T$, and yet still can not be proved from $...
6
votes
1answer
100 views

How do inconsistent arithmetics get around Gödel incompleteness?

Gödel theorems imply that arithmetic can not be complete under recursive axiomatization and consistency assumptions. Unexpectedly, consistency can be dropped in a meaningful way by switching to a ...
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 ...
4
votes
1answer
101 views

Proving that the existence of strongly inaccessible cardinals is independent from ZFC?

ZFC can't prove that strongly inaccessible cardinals exist, or else it would prove that a model of itself exists and hence $Con(ZFC)$. So this leaves us with two options: ZFC proves there are no ...
5
votes
0answers
62 views

Vaught's essentially undecidable set theory

Today I was reading this paper, which includes discussion of essential undecidability of various weak theories. On page 24, I was surprised to find out that Vaught has showed that set theory with the ...
22
votes
3answers
2k views

Why is Gödel's Second Incompleteness Theorem important?

Given that the consistency of a system can be proven outside of the given formal system, Gödel says, It must be noted that proposition XI... represents no contradiction to the formalities ...
2
votes
2answers
122 views

understanding gödel's 1931 paper - gödel numbers

I am a little confused about gödel numbers and what numbers exactly we are manipulating. are the numbers "real" natural numbers (than we obviously represent as) 1, 2, ... or are we always dealing ...
3
votes
1answer
146 views

understanding gödel's 1931 paper - the undecidability theorem

I am reading a translation of Gödel's original paper about in completeness theorem and there are a couple things i don't understand. Here is the document i am using primarily : http://www.research....
0
votes
1answer
77 views

Concerning the canonical example for Gödel's first incompleteness theorem

Concerning the canonical example for Gödel's first incompleteness theorem: G cannot be proved within the theory T If G were provable under the axioms and rules of inference of T, then T would ...
0
votes
1answer
91 views

understanding gödel's 1931 paper - elementary formulae

I am trying to understand Gödel's first incompleteness theorem from his original 1931 paper. Here is a translation i am using for my studies : http://www.research.ibm.com/people/h/hirzel/papers/...
3
votes
2answers
59 views

Gödel's theorems and nonstandard model of $PA$

According to the Second incompleteness theorem $Con(PA)$ is independent of $PA$. So if $PA$ is consistent $PA + \neg Con(PA)$ is also consistent which means that there exist a number $t$ which codes a ...
0
votes
1answer
67 views

understanding gödel's 1931 paper - proof of theorem / proposition V 5

I am trying to fully understand gödel's proof of the first incompleteness theorem from it's original 1931 paper. Here is the document I am using : http://www.research.ibm.com/people/h/hirzel/papers/...
0
votes
0answers
39 views

Standard model of the Meta theory in the proof of arithmetic incompleteness

I have a question about the incompleteness of arithmetic. I wonder in which meta theory we are reasoning. For example, if we are in ZFC, then there are some non standard models of ZFC. As far as I ...
0
votes
0answers
20 views

Completeness of the space $C_{2\pi} \left ( \mathbb{R} \right )$ [duplicate]

Denote $C_{2\pi} \left ( \mathbb{R} \right )$ is the set of complex-value, continuous on $\mathbb{R}$, periodic functions with period $2\pi$. Fix $p \in \left [1, \infty \right )$. For each $x \in C_{...
11
votes
2answers
138 views

Proportion of true statements that are provable

In an axiomatic system, there are true statements, some but not all of which are provable. Is there any sense in which we can quantify the proportion of those statements that are true? Here's an ...
1
vote
1answer
68 views

Infinitely many nonequivalent unprovable statements in ZFC because of Gödel's incompleteness theorem?

Am I right in thinking that there are countably infinitely many nonequivalent unprovable statements in ZFC due to the Gödel's first incompleteness theorem? If not, why?
1
vote
3answers
170 views

[Paradox]How can Godel prove that Godel sentence is unprovable but true, if such proof itself proves that Godel sentence is true?

Isn't the proof that Godel sentence is unprovable but true a proof itself that Godel sentence is true? Godel in the preface of his proof remarked: “From the remark that [the unprovable statement] ...
3
votes
2answers
97 views

understanding gödel's 1931 paper - primitive recursive functions - projection and equality

I am reading a translation of gödel's original, and i'm a bit confused about the primitive recursive functions. Everywhere on the internet (or some resources like courses/classes i could put my hands ...
4
votes
1answer
186 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 ...
0
votes
1answer
58 views

understanding gödel's 1931 paper - primitive recursive functions “FR(x)” and “n Gl x”

I am trying very hard to fully understand gödel's paper on the incompleteness theorem. I have a slight technical question about one of the 45 primitive recursive functions introduced to build the ...
0
votes
1answer
40 views

Godel's Incompleteness Theorem and Algorithms [closed]

According to Godel's incompleteness theorem, not every problem can be solved using algorithms. How do we know if a problem can be solved using algorithm? How do we know that NP problems are ...
1
vote
1answer
64 views

What's wrong with this proof that ZFC is consistent

If we take ZFC minus all it's axioms, we can easily prove that ZFC's first axiom is independent (because all statements are independent in a formal system without any axioms). We can then prove that ...
1
vote
1answer
31 views

Will assuming an undecidable statement result in a consistent system?

If you assume that an undecidable statement in a consistent axiomatic system is true (or false), will that new system also be consistent? For example, does $\mathsf{ZF}$ being consistent imply that ...
4
votes
2answers
125 views

$L$ models set theory and so does $V_\kappa$ for $\kappa$ inaccessible

Background: I have been reading the 1980 edition of Kunen. Theorem VI.2.1 states it is provable from ZF that $\mathbf L$ (Kunen writes classes in bold) is a model of ZF. Also, it is a well-known ...
-8
votes
2answers
196 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 ...
3
votes
1answer
42 views

Consistency hierarchy between models with many urelements

The axiom of extensionality can be weakened, asking only for non-empty sets with the same elements to be equal. Then there can be many "different empty sets" called urelements. I call this theory ZFU (...
1
vote
1answer
60 views

Does the Law of the Excluded Middle imply syntactical completeness?

The Law of the Excluded Middle (LEM) states that for any proposition $p$, we have $\vdash p \lor \lnot p $. Syntactic completeness (a.k.a negation completeness) states that for any proposition $p$, ...
2
votes
1answer
74 views

$\mathrm{NBG}$ proves its own consistency

In $\mathrm{NBG}$, one can construct a model of $\mathrm{ZFC}$: $V$, the class containing every set. Thus: $\mathrm{NBG}$ can prove "$\mathrm{ZFC}$ is consistent". Furthermore, the following ...
3
votes
2answers
165 views

Could someone show me a simple example of something being proved unprovable?

Could someone show me a simple example of something being proved unprovable? Pretty much what the title says, I want to understand a proof of some statement being proved unprovable. E: Please read ...
8
votes
2answers
308 views

How is the standard model of number theory specified, and why can't we use that specification to prove any number theoretical sentence of interest?

According to Gödel's incompleteness theorem, there exists a sentence $G$ in the vocabulary of number theory ($N$) which is not provable from any (recursively enumerable) consistent set of axioms $T$, ...
0
votes
1answer
54 views

Is there some result that says a theory cannot prove the consistency of any of its extensions?

Is there some result that says a (sufficiently strong) theory cannot prove the consistency of any of its extensions? Or something along these lines?? More generally, is there a result that says a (...
0
votes
1answer
30 views

What does it mean to encode some statement in Theory of Natural Numbers $Th(\mathbb{N})$?

For example Godel's Incompleteness Theorem says "Some statement in $Th(\mathbb{N})$ has no proof". Consider sentence "This sentence is not provable". We can encode this sentence in $Th(\mathbb{N})$. ...
-7
votes
1answer
139 views

Gödel's theorem, un-decidable propositions and axioms of a formal theory [closed]

There was a similar question of mine some time ago (which is now closed, but should not be). Anyway the question is similar, but simplified to avoid (mostly) "pedantic" objections, which bypass the ...
4
votes
3answers
223 views

Gödels incompleteness vs incompleteness

This has been nagging me, and might be an unfit question, but still: I've been taught that completeness of a theory $T$ means that for any sentence $\varphi$ in the language of the theory, we have ...
0
votes
1answer
28 views

Is there any relationship between Gödel numbers associated with proofs of undecidable theorems and infinitesimals?

I recall from my reading of the popular book, Gödel, Escher, Bach some years ago that Hofstadter speculated on the value of Gödel numbers of undecidable theorems. If I recall correctly, he suggested ...
1
vote
3answers
75 views

Godel's incompletness theorem - proving a statement is false

I have two question regarding Godel's incompletness theorem. The theorem says that every axiomatic system is either incomplete or inconsistent. If it's consistent, then there are true statements that ...
10
votes
2answers
601 views

Are the Gödel's incompleteness theorems valid for both classical and intuitionistic logic?

I am studying an undergraduate text about math logic. The proofs of the two Gödel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I ...
4
votes
3answers
259 views

Does Gödel's incompleteness theorem contradict itself?

I have problems understanding Gödel's incompleteness theorem. I presume I have a misunderstanding of some phrase or I have to look closer at the meaning of some detail. Gödel's second incompleteness ...
5
votes
1answer
70 views

Does the foundations of Arithmetic need to be effective?

I was reading about Godel's incompleteness theorem which is true for any formal theory that satisfies certain properties. One of these properties is the following: "The theory is assumed to be ...
3
votes
1answer
82 views

Independence of existence of inaccessible cardinals

Let $I$ be the formula which states that there exists strongly inaccessible cardinals. My question is regarding the proof of $ZFC\nvdash I$ appearing in Jech (part of theorem 12.12). He starts by ...
0
votes
0answers
23 views

Quantitative results on PA completeness?

Are there any results estimating the number of sentences in PA that are not provable together with their negations, as a function of the sentence length or the depth of the sentence parse tree or ...
0
votes
3answers
125 views

Godel's Second Incompleteness and the Assumption of Consistency

As I understand it, Godel's Second Incompleteness Theorem states that given a theory $T$ that is any extension of Robinson Arithmetic, that if that theory is consistent then it cannot prove a given ...
20
votes
6answers
4k 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, ...