# Tagged Questions

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

1answer
94 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 ...
5answers
902 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 ...
6answers
1k views

### Can we prove that a statement cannot be proved?

Is it possible to prove that you can't prove some theorem? For example: Prove that you can't prove the Riemann hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in ...
1answer
111 views

### Analogy between a Gödelian puzzle and Gödel's first incompleteness theorem

I'm studying Gödel's incompleteness theorems. And I have the following slide that defines a version of Gödel's first incompleteness theorem. The point is that one can always follow the math and get ...
2answers
77 views

### How can Godel's theorem apply to every formal system?

How can Godel's theorem apply to any formal system of logic, if the truth of the theorem itself is only relative to the axioms and rule of inference that were used to generate it. In other words ...
1answer
42 views

### Expanding arithmetic to a complete theory by a transfinite sequence of expansions.

We all know that Godel first incompleteness theorem states that any recursive sufficiently strong theory to express arithmetic is incomplete. in particular, arithmetic is not complete. It's common ...
2answers
88 views

### How does Gödel's second incompleteness apply to any theory containing arithmetic?

If I understand correctly, there are two facts proven by Gödel's second incompleteness theorem, for a formal theory containing arithmetic 1) It is possible to express the consistency of the theory ...
4answers
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$ ...
1answer
57 views

### Gödel's Incompleteness theorem in modal logic

I think I once taught that the statement of the Gödel's Incompleteness theorem is equivalent to : $\diamond \neg \square \square p$, if p is a complex enough system. Is this right?
1answer
54 views

### Is there a result for second-order theories analogous to Gödel's second incompleteness theorem?

One formulation of Gödel's second theorem says that, if $T$ is a consistent, axiomatisable extension of $PA$, and then $T$ cannot prove $\neg Prv(\ulcorner 0=1 \urcorner)$, where $Prv(-)$ is a ...
2answers
771 views

### What does Gödel's Incompleteness Theorem prove?

Does Gödel's incompleteness theorem only prove that you can't have a formal system which describes number theory which is both complete and consistent, or is it more general? In other words: does it ...
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 ...
1answer
35 views

1answer
381 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 ...
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'...
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 ...
1answer
196 views

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 ...
1answer
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?
3answers
188 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] ...
2answers
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 ...
1answer
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 ...
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 ...
1answer
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 ...
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 ...
1answer
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 ...
2answers
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 ...
2answers
204 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 ...
1answer
44 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 (...
1answer
62 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$, ...
1answer
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 ...
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 ...
2answers
313 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$, ...
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 (...
1answer
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})$. ...