# Tagged Questions

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

179 views

### Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?

I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me. In discussing matters around and about the ...
30k views

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

Can you explain it in a fathomable way at high school level?
230 views

### Can one have a theory that includes its own consistency as an axiom?

Consider the theory with the following axioms: The axioms of ZFC The "axiom of consistency": "This theory, including this axiom and all of the theory's other axioms, is consistent." Phrased ...
59 views

### Why a Riemannian manifold minus one point is not complete? [closed]

Could you give me a proof that a Riemannian manifold minus one point is ever complete? Thanks!!
36 views

### Gödel numbering for sequences Using the Chinese remainder theorem [closed]

I looked into some youtube videos and got a simple idea about Gödel numbering and Chinese remainder theorem separately.... But can't see how to use them as one. Wikipedia giving a way or may be its an ...
220 views

### In Godel's first incompleteness theorem the Godel sentence G is true otherwise it contradicts itself, however its truth implies it is not provable .

How can this be? I understand there are two basic definitions of truth in mathematics, one being the formalist definition which includes excluded middle and the second form being the intuitionist in ...
272 views

### Are Godel's incompleteness theorems proven non-trivial?

Godel's incompleteness theorem states there will be unprovable statements in some language. Can it be proven that the unprovable statements in some language $F$ are necessarily not just "trivially ...
118 views

### How can logic talk about itself? [closed]

How can there exist theorems like Goedel's Completeness theorem or Incompleteness theorem? They all make some statements about logical theories, but don't we need a certain logical scheme first to be ...
28 views

### Isn't it problematic to cite the Gödel sentence as a proposition asserting 'This sentence is unprovable' since it isn't really on point?

In the proof of Gödel's incompleteness theorem the Diagonalization Lemma is applied to the negated provability predicate $¬Prov_F(x)$: this gives a sentence $G_F$ such that $F ⊢ G_F ↔ ¬Prov_F(⌈G_F⌉)$...
31 views

### What is the significance of Gödel's incompleteness theorems? [duplicate]

I have been trying to wrap my head around this for a couple of months now, it seems to me that a short informal stating would be this: You have the first incompleteness theorem, which proves that ...
260 views

### I have read that complex axiomatics are Gödel complete, while naturals aren't. Why?

I have read in a book:(G. Martínez, G. Piñieiro: "Gödel para todos") that complex axiomatics are Gödel complete, while naturals aren't. How can this be if Naturals are a subset of Complexes, (or at ...
421 views

### What would be the consequences if ZFC proved its own inconsistency, nonconstructively? [closed]

Let's say a nonconstructive proof was given in ZFC that ZFC was inconsistent. Note that this doesn't automatically make ZFC inconsistent. Given a consistent theory $X$, $X + \neg \text{Con}(X)$ is ...
73 views

### Why is the proof of Gödel's first incompleteness theorem no contradiction?

I consider the following version of Gödel's first incompleteness theorem: Assume $F$ is a formalized system which contains Robinson arithmetic $Q$. Then a sentence $G_F$ of the language of $F$ can ...
72 views

### Arithmoquine function in Gödel's proof

Could someone explain as detailed as possible how the Arithmoquine{a,a'} function works or is the defined in Gödel's proof of the incompleteness theorem? To describe my question better... In this ...
51 views

37 views

### Rosser Sentences and Theories

Let T be any theory extending Q. Let R be the Rosser sentence of T. Let T0 be T + {R} and T1 be T + {∼ R}. Show that T0 and T1 are both consistent. Show that T0 ∪T1 is inconsistent. Show that for each ...
42 views

### If a theory is 1-consistent then it is consistent

I am attempting to back two claims in this problem: I use $\textbf{Q}$ to denote minimal arithmetic for this post. I use the term 'rudimentary sentence' to denote formulas built using only negation, ...
476 views

### Can unprovability unprovable? Is there an $\omega$-fold unprovability?

I was just thinking about unprovability. I just wanted to know if it is possible to make a concrete boundary between provable problems and unprovable problems in a certain axiomatic system. We know ...
101 views

### Does Gödel’s theorem affect anything but the arithmetic of the natural numbers? [closed]

Влияют ли теоремы Гёделя на что-нибудь кроме арифметики натуральных чисел? Существуют ли интересные независимые от ZFC утверждения ,которые рождены теоремами Гёделя о неполноте, и которые не ...
27 views

### Why is it impossible to prove absolute consistency of a theory falling prey to Godel's theorems?

Why is it impossible to prove absolute consistency of a theory T falling prey to Godel's theorems? I understand that a theory falling prey to Godel's second incompleteness theorem cannot prove its own ...
98 views

### Why can't we keep adding axioms forever?

Let F be a formal system falling prey to Gödel's incompleteness theorems, implyng there is a true but unprovable statement, call it $G_1$. Of course, adding $G_1$ to the axioms of F doesn't solve the ...
23 views

### Can there be true but unprovable statements about object other than numbers?

In ZFC, everything is a pure set, and because the necessary amount of arithmetic for the Gödel's incompleteness theorems to go through is interpretable within ZFC, there are undecidable statements ...
56 views

### Impossibility of proving a foundation to be consistent

An argument came to my mind that seems really mind-blowing and I haven't found it anywhere. Here's how it goes: We call a formal system F embodied in classical logic a foundation of mathematics when ...
206 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 (...
28 views

### Can we prove undefinability theorem first (using techniques that are different from Godel's) and then deduce Incompleteness from it?

I asked a related question about the matter here in philosophy platform where it was suggested to ask a modified version of the question on Math.se My question is, Is there any known way to prove ...
36 views

### Any foundational theory of math falls prey to the incompleteness theorems - true or false?

I heard somewhere on the internet once something along the following lines: Any conceivable foundational theory of mathematics (be it ZFC or, if ZFC was found to be inconsistent, some modification ...
61 views

### What is the simplest formal system falling prey to Gödel's incompleteness theorems?

What is the the simplest formal system falling prey to Gödel's incompleteness theorems? Is the answer different for the first and second theorems? Is the answer Q for the first theorem and PRA for ...
24 views

### Exercise Henkin Theory

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. I have to do this excercise: Assume that Γ is a theory satisfying the following: Γ is a Henkin ...
15 views

### Same number of provable as unprovable statements?

Building on this question: Infinitely many nonequivalent unprovable statements in ZFC because of Gödel's incompleteness theorem? is the infinity of provable statements the same infinity of ...
305 views

### Sequent calculus and first incompletness theorem

Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
5k views

### Is linear algebra more “fully understood” than other maths disciplines?

In a recent question, it was discussed how LA is a foundation to other branches of mathematics, be they pure or applied. One answer argued that linear problems are fully understood, and hence a ...
40 views

### First Incompleteness Theorem: Does the limit of $\mathsf{T}_n\cup\{\rho_{\mathsf{T}_n}\}$ exist?

Suppose $\mathsf{T}$ is a consistent, computably axiomatizable theory extending $\mathsf{Q}$, Robinson arithmetic. Then by the First Incompleteness theorem there is a sentence $\rho_\mathsf{T}$ such ...
192 views

### Informal proof of Godel's second incompleteness theorem

This relates to two previous threads: Question about Godel's first incompleteness theorem and the theory within which it is proved Explanation of proof of Gödel's Second Incompleteness ...
71 views

### Help understanding Gödel's theorems?

What are the prerequisites to even begin to understand Gödel's theorems? I'm reading Hofstadter's book but would like a more fundamental approach to understanding these theorems. I have no knowledge ...
82 views

### Godel's proof for dummies [closed]

Can someone give me as simple-a-proof as possible for Godel's Incompleteness Theorem? I'd love to understand it more.
576 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 ...
8k views

### What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
68 views

### Is there a consistent arithmetically definable extension of PA that proves its own consistency?

Gödel's second incompleteness applies, for instance, to r.e. extensions of PA. I am wondering if it applies more generally to arithmetically definable extensions of PA. I see that there is a complete ...
72 views

### Gödel's Incompleteness Theorem and Numerical Analysis

I am no expert in Mathematical Logic so I can't really express my question formally but I do hope that it will make sense. As far as I know the implication of Gödel's incompleteness theorem for ...
86 views

### Is there a difference between induction in Peano Arithmetic and Presburger Arithmetic

Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics I was thinking ...
38 views

### Does the existence of uncomputable functions imply that a theory is incomplete?

For example Kolmogorov complexity is uncomputable and Chaitin used that fact to prove incompleteness. If this is not the case, can you give me a counter example? Set of axioms is countable.
88 views

### What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my "proof" of "ZF is inconsistent" was that I was not considering that there are models with non-standard integers. However now I think I ...