# Questions tagged [incompleteness]

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

638 questions
Filter by
Sorted by
Tagged with
71 views

### While using the method of proof by contradiction, are we “assuming” consistency?

I am aware of threads here and here which asks something similar. However, I had something very specific to ask under the same context. I have a very elementary question about the connection between ...
38 views

### To what extent does Goedel's 2nd incompleteness theorem extend?

In chapter 8 of Shoenfield's matheamtical logic, He proves that The formula of P which states that P is consistent is not a theorem of P, where P stands for Peano Arithmetic. And then He says, ...
43 views

### Why doesn't the incompleteness theorem answer the decision problem?

The answer (or impossibility of an answer) to Hilbert's Entscheidungsproblem or decision problem is generally attributed to Alan Turing and also independently to Church. My question is why Gödel's ...
29 views

### Is PA complete when multiplication is bounded?

Working in PA. Fix some natural number "$n"$. Is PA complete for sentences that do not use the symbol $\times"$ unless all of their variables are bounded $< n$.
41 views

### Relative completeness of first order arithmetic

Gödel's incompleteness theorem tells us that the language of first order arithmetic $PA_1$ is strong enough to express a statement about its own consistency, which cannot be proved in $PA_1$. More ...
56 views

### For any statement independent of $\mathsf{ZFC}$, can we prove it is independent of $\mathsf{ZFC}$? [duplicate]

Gödel's famous incompleteness theorem implies, in particular, that there are statements unprovable in $\mathsf{ZFC}$. This implies that we could never hope to settle the truth of every mathematical ...
59 views

### Circular logic in the concept of Godel numbers

I am interested in understanding how Godel was able to prove his two celebrated theorems. I usually start with the most elementary book (something that perhaps a high school kid can understand) in ...
43 views

### Godel's Incompleteness Theorems & the Laws of Thought [closed]

If Godel showed that a sufficiently powerful formal system can be consistent or complete but not both, is this equivalent to saying that the law of non-contradiction or the law of excluded middle ...
55 views

### Is Halting problem an example of a problem which is true but unprovable?

I have a difficulty understanding Gödel's incompleteness theorems. If it is proven semantically that some problem is undecidable (such as Halting problem), does it means that such a statement is "true ...
42 views

### If PA is consistent, for any $n$, does PA prove “$n$ does not code a proof of an inconsistency”?

I am still struggling with the distinction between what is proven where. I think I have a good understanding of the theory and the meta-theory, but then I'm stumped every once in a while, so I fear ...
26 views

### How does Rosser's Theorem actually show that a system is inconsistent if it's complete?

So I was reading this article: https://www.scottaaronson.com/blog/?p=710 and I had an issue with the way he described Rosser's Theorem. He starts by describing Gödel's Incompleteness Theorems, and ...
24 views

### Was Frege's 2nd-order logic a complete system?

Frege's system was found to be inconsistent due to Russell's paradox, due to his Basic Law V, but was Frege's logic complete in any sense? Godel showed that no consistent formal system can be ...
68 views

### Proving Unprovability: Is Compactness Used in the Metathory?

I am reading Halbeisen's "Combinatorial Set Theory", and it certainly provides a great exposition of forcing (bar its notation conventions for forcing...). The very short chapter 16 is dedicated to ...
36 views

### Proving Parallel Postulate by showing that it is undecidable

In the Numberphile video "Gödel's Incompleteness Theorem" (via YouTube), Professor Marcus Du Sautoy mentions that the Riemann hypothesis could be proved true by proving that it was undecidable, ...
69 views

### Proving a statement is true by proving it is undecidable.

https://www.youtube.com/watch?v=O4ndIDcDSGc I was watching this numberphile video in which Professor Du Sautoy mentions that if the Riemann hypothesis is undecidable, it must be true. Let's say we ...
41 views

### How to prove the diagonal Lemma

I am interested in understanding the proof of Gödel’s Incompleteness theorems. The diagonal Lemma is used to prove the existence of self-referential statements. But as I read the proof of the Diagonal ...
30 views

### Is $\omega$ -consistency, soundess, or completeness expressible in the language of arithmetic? [closed]

Obviously through the second incompleteness theorem consistency is expressible in La, I was wondering if $\omega$ -consistency and completeness were the same and how so. I know soundness is not but I ...
66 views

### About First Order Logic an Godel incompleness theory.

There's something I'm failing to grasp: Are Gödel's theorems of incompleteness a first order logic result or a second order logic result? What confuses me is the fact that in Gödel's original work, he ...
115 views

### Confused about $\mathsf{ZFC} \nvdash \mathrm{Con}(\mathsf{ZFC}) \to \mathrm{Con}(\mathsf{ZFC} + \mathsf{I})$

I am studying with Jech's book. He claims that The existence of inaccessible cardinals is not provable in $\mathsf{ZFC}$. Moreover, it cannot be shown that the existence of inaccessible cardinals ...
28 views

### Is it possible to prove Gödel’s 1st Incompleteness theorem without the use of self referential statements [duplicate]

Is it possible to prove Gödel’s 1st Incompleteness theorem without the use of self referential statements? I have searched for various proofs of the first incompleteness theorem and all of them use ...
62 views

59 views

### In the 1st incompleteness theorem proof, how do we assume that everything in arithmetic language can be mapped to naturals?

Consider the following set of arithmetic functions, $a_0,a_1,a_2.....a_m(n)=a_0+a_1n+a_2n^2+...a_mn^m$ $a_0,a_1,a_2.....a_n$ can be any subset of naturals. So clearly, the number of these arithmetic ...
105 views

### Does Godel's Incompleteness theorem only prove that some self referential sentences are unprovable?

It shows that the sentences of the form $\forall x, \neg Dem(x,sub(n,y,n))$ are true but unprovable, where $y$ is the Godel number mapped to the symbol $Y$ in arithmetic language, and $n$ is the Godel ...
46 views

### Confusion with the predicate $Dem(x,z)$ in Godel's incompleteness theorem proof

I'm reading http://www.math.mcgill.ca/rags/JAC/124/GodelsProof.pdf Near the final pages, they prove it. Here's the proof as I understand it: All symbols in the language of arithmetic are given a ...
55 views

121 views

65 views

### A question about the proof of Godel's Incompleteness Theorem

The article A Computability Proof of Gödel’s First Incompleteness Theorem, by Jørgen Veisdal on Cantor's Paradise contains the following passage: The second property regards the complement of a set ...
81 views

91 views

### Why can't we prove the consistency of ZFC by proving its axioms is satisfiable?

We can prove the consistency of Peano Arithmetics by given a model of natural numbers, within this model, PA's axioms are satisfiable，thus PA is consistent. Why can't we do the same thing to ZFC
108 views

### False Σ1-sound theories

I was wondering how Σ1-sound theories in the language of first-order arithmetic can go wrong. As far as I can tell, they cannot prove false claims about consistency, since such claims (e.g., that ...
38 views

### Quantifying the “Complexity” or “Strength” of Axiomatic Systems

The halting Problem states that there is no Turing Maschine that is able to decide whether an arbitrary other Turing Machine will halt. In 2016 Adam Yedidia and Scott Aaronson presented a turing ...
57 views

### Completeness of Logic versus completeness of a theory

It's my understanding that First-Order-Logic is complete, but that not all logical theories are complete (for example, Russel's Arithmetic) - both these results having been shown by Godel. I'm trying ...
86 views

### Does $\omega$-consistency of ZF imply $\omega$-consistency of ZFC

Does $\omega$-consistency of ZF imply $\omega$-consistency of ZFC? Are there any related results where $\omega$-consistency of some intuitionistic logic implies $\omega$-consistency of ZFC? Does ...
75 views

### Proof of Gödel's Incompleteness Theorem by modal logic

I watched Undefined Behavior's videos (on YouTube) regarding Gödel's Incompleteness Theorem, and the last video slightly confuses me. Let $\square P$ denote "There is a proof of the statement $P$." ...
Consider the famous Collatz sequence  x_{n+1} = c(x_n) = \left\{ \matrix{x_n/2 & {\rm if \; x_n \; even} \hfil \cr 3x_n+1 & {\rm if \; x_n \; odd} \hfil \cr } ...