# Tagged Questions

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

25 views

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....
69 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?
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 ...
186 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] ...
98 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 ...
126 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 ...
42 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 ...
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 ...
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 ...
32 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 ...
191 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 ...
126 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 ...
1k views

### How does Gödel Completeness fail in second-order logic?

So a while ago I saw a proof of the Completeness Theorem, and the hard part of it (all logically valid formulae have a proof) went thusly: Take a theory $K$ as your base theory. Suppose $\varphi$ ...
61 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$, ...
77 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 ...
43 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 (...
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 ...
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 (...
31 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})$. ...
141 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 ...
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 ...
76 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 ...
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 ...
83 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 ...
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 ...
127 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 ...