# Questions tagged [incompleteness]

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

876 questions
Filter by
Sorted by
Tagged with
1 vote
73 views

### Godel's incompleteness theorem: Question about effective axiomatization

I am studying Godel incompleteness theorems and I am struggling with the definition of effective axiomatization. From Wikipedia: A formal system is said to be effectively axiomatized (also called ...
• 2,432
107 views

### Proof of Gödels first incompleteness theorem (as in Kunen)

On page 40 in Kunens "Set Theory An Introduction to Independence Proofs", we are given the following theorem: Gödel. If $\phi(x)$ is any formula with one free variable, $x$, then there is a ...
• 1,268
586 views

### Busy Beaver argument and Gödel's incompleteness theorem

By Gödel's incompleteness theorem, it should not be possible to prove the consistency of ZFC within ZFC (if it is consistent). It is well known that the Busy Beaver function is uncomputable, and that ...
• 159
112 views

### Gödel theorem as mentionned in Hartshorne's Geometry: Euclid and Beyond

I am reading Geometry: Euclid and Beyond by R. Hartshorne and there is a section discussing the possible axiomatizations for planar geometry. In the following paragraph, Hartshorne mentions Gödel's ...
• 785
134 views

### Interpretation of Godel's incompleteness theorem [closed]

Godel's incompleteness theorem states "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e. there are statements of the ...
• 2,280
1 vote
96 views

### Arithmetic content of proofs [closed]

Using some variant of Gödel numbering, we can turn mathematical propositions into integers (say $m$). The existence of a proof of such a statement can then be formulated in an arithmetic way, ...
• 785
142 views

### Does this correctly describe how Gödel's First Incompleteness Theorem is proved?

One encounters in books and YouTube videos various ways of describing Gödel's Incompleteness Theorems and their proof. My background is not at all in formal logic, and I want to check if my ...
174 views

### Why is Gödel's Incompleteness Theorem relevant to anything beyond self-referential statements?

I feel like I understand the general idea behind how Gödel used self-reference to prove that there will always be holes in logical systems, even if you add the self-referential statement to the axioms ...
53 views

### Peano Arithmetic can prove any finite subset of its axioms is consistent

Timothy Chow writes in a MathOverflow answer [...] here is a classical fact: for any finite subset of the axioms of PA (remember that PA contains an axiom schema and hence has infinitely many axioms),...
• 4,886
53 views

### Contradiction and Godel's incompleteness theorems

If T is a recursively axiomatizable formal system containing peano arithmetic and is able to carry out the proof for the Godel's incompleteness theorems (so according to Wikipedia includes primitive ...
140 views

### Is Gödels second incompleteness theorem provable within peano arithmetic?

All following notation and assumptions follow Gödel's Theorems and Zermelo's Axioms by Halbeisen and Krapf. Exercise 11.4 c) states "Conclude that the Second Incompleteness Theorem is provable ...
• 171
423 views

### PA + "(PA + this axiom) is consistent"

By Gödel's second incompleteness theorem, no sufficiently powerful formal system can prove its own consistency. I was wondering what happens if one tries to manually append an axiom stating a formal ...
• 3,054
98 views

• 20.7k
41 views

### Predicate logic equivalence

I have been reading this article about Tarski's undefinability theorem: https://qubd.github.io/files/TarskiUndefinability.pdf It has a very interesting section on page 4: This does not really make ...
• 521
1k views

### In his 1931 incompleteness proof, how does Godel's definition of "immediate consequence" work?

Necessary in order to define a provabilty predicate, Godel defined the relation, $Fl(x,y,z)$ ("$x$ is an immediate consquence of $y$ and $z$"). But the definition leaves me flat. I ...
89 views

### What are the consequences of negating the Godel sentence in a formal system? [duplicate]

What is wrong with the following argument? Let $F = T + ¬G_T$, where $T$ is an effectively generated formal system and $G_T$ is its Godel sentence. Then, it is possible to prove within $F$ the First ...
1 vote
113 views

### Is there a sequence $\mathbb{N}^*\to\mathbb{N}^*$, not depending on the model of $\mathsf{ZFC}$, whose convergence is independent of $\mathsf{ZFC}$?

I think this is rather a naive question, so please forgive me for asking this. In the Wikipedia page List of statements independent of ZFC, it is stated that "One can write down a concrete ...
• 1,923
1 vote
85 views

### What is decidability and completeness?

A formal system comes with both a syntactic component, which determines the notion of provability ($\vdash$), and a semantic component, which determines the notion of truth ($\vDash$). For this ...
209 views

### meaning of ɷ-consistency......

i was going through the original statement of ɷ-consistency as stated in godel's 1st incompleteness proof, but i saw this pararaph on wikipedia here - https://en.wikipedia.org/wiki/%CE%A9-...
85 views

### Gödel's theorems, Löb's theorem, difference between "proves" and "implies"

Layman reading up on Gödel's theorems. I think I have some basic idea of how it all works in the abstract, but I'm still having a hard time distinguishing between (or even counting) the concepts ...
• 601
170 views

### Gödel’s Incompleteness Theorems Simple Wikipedia

I recently wrote the outline of the proof of Gödel’s incompleteness theorems for Simple Wikipedia. I would like to get feedback on its clarity and logical validity so that I can make further ...
• 19
1 vote
155 views

### Confusion about the consistency of $\mathsf{ZFC}+\neg\mathsf{Con}(\mathsf{ZFC})$

I know that this question may look foolish because $\mathsf{Con}(\mathsf{ZFC})$ is independent of $\mathsf{ZFC}$, but still I have some problems understanding this. "If $\mathsf{ZFC}$ is not ...
• 1,923
193 views

### Why Godel have chosen $\omega$-consistency of a theory instead of it proving it's own consistency?

Godel assumed $\omega$-consistency for his proof of the first incompleteness theorem to run. But, isn't it the case that if we assume that a theory $T$ is effective, complete and $\omega$-consistent, ...
• 4,631
103 views

### Does inconsistency imply incompleteness?

I'm self-studying the book Incompleteness and Computability but I'm having troubles understanding the relation between consistency and completeness. I'm working with the following definitions: A ...
1 vote
125 views

### About Gödel's completeness and incompleteness theorems

I am using ZFC as a tool to demonstrate my problematic logic. In zfc we construct a proof system for zfc in zfc (a simulation of a proof is what I mean); we will call it inner proof system. We ...
1 vote
112 views

### Is someone trying to solve problems by building all possible proofs using all possible rules of inference? [closed]

We obviously can construct a program that, starting with ZFC (or any other theory) axioms, would use all possible rules of inference to get all possible proofs constructible in ZFC. (There would be ...
1 vote
95 views

### Gödels incompleteness theorem false for natural numbers

Do I understand it correctly that in an axiomatic system that includes the natual numbers defined by using Peano's axiom, where the 9th axiom (induction) is formulated using 2nd-order logic, then ...
92 views

### Is the function sending a sentence to the diagonal of a sentence form extended over it, computable?

Is, the following function $h$ computable? Let $h: \mathbb N \to \mathbb N$ be the function defined by:$$h(\ulcorner s \urcorner) = \ulcorner D(E_s(v)) \urcorner$$ for each sentence $s$ in the ...
• 4,631
99 views

### Is truth outrunning provability equivalent to undecidability of some statement in a theory?

The Wikipedia exposition of Boolos's proof of Godel's first incompleteness theorem assumes that the first incompleteness theorem is equivalent to non-existence of an algorithm that outputs all true ...
• 4,631
1 vote
179 views

### Can this serve as an alternative proof of Gödel's first incompleteness theorem?

let $s$ be a standard sentence in the language of $T$. Let $E(s)$, called extension of $s$, be the sentence form:  \forall x \forall y \, (\operatorname {Proof}_T(x,v) \land y= \min z: \operatorname ...
• 4,631
1 vote
65 views

### What exactly does "a sufficiently expressive procedure for enumerating theorems" mean in the context of the incompleteness theorems?

Whenever I Google to try to find an actual formal statement of the first incompleteness theorem (as opposed to all the oversimplified explanations that talk about "true but unprovable theorems&...
1 vote
81 views

Suppose we have a formal system, F, in which the second incompleteness theorem can be applied. If we were able to prove, using some higher level system, F’, that F is consistent, do we not have the ...
• 305
54 views

### Is a proof through undecidability contradictory?

I'm reading Fermat's Last Theorem by Simon Singh and in it he writes the following: ... if Fermat's Last Theorem turned out to be undecidable, then this would imply that it must be true. The reason ...
1 vote
114 views

### Are the natural numbers definable in ZFC-Inf

While reading up on the incompleteness theorems on this page, I came upon the statement that the incompletess theorems hold in ZFC-Inf. According to the page ZFC-Inf is 'proof-theoretically equivalent'...
194 views

### If Goldbach's conjecture G is undecidable in PA, then can we prove $\mathbb N\models G$?

Suppose Goldbach's conjecture $G$ is undecidable in first-order Peano arithmetic, $\sf{PA}$. That would mean there are models in which $G$ is true and other in which it is false. But intuitively, this ...
• 6,672
93 views

### What does "by finitary methods" actually mean, in regards to Hilbert's proof of consistency program?

David Hilbert wanted to establish the consistency of mathematics, and in particular Peano Arithmetic, using finitary methods. This program is widely thought to have completely failed, due to Kurt ...
• 21.4k
115 views

### Does this argument simplify the proof of the diagonal lemma? Is it restricted?

Reading through the proof of the diagonal lemma related to Gödel incompleteness theorem on wikipedia, I feel its a little bit complex. As far as this lemma relates to proving Gödel incompleteness ...
• 4,631
1 vote
89 views

### Are there Gödel sentences in Euclidean geometry?

I understand that Godel's theorems apply to formal systems and it seems possible to treat Euclidean geometry as a formal system. My question is more focused on this: let's take Goodstein's theorem as ...
• 135
311 views

### How does Eq (8.1) mean in the English translation of Godel's original paper?

I have doubt with Eq. (8.1) in [1] with the item "subst(y,19,number(y))" . The 1st parameter of subst(), i.e. y, is the Godel number of some formula, and the 2nd parameter, i.e. 19, means ...