Skip to main content

Questions tagged [incompleteness]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
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 ...
Tereza Tizkova's user avatar
0 votes
2 answers
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 ...
Ben123's user avatar
  • 1,268
4 votes
1 answer
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 ...
user22476690's user avatar
3 votes
1 answer
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 ...
Weier's user avatar
  • 785
0 votes
1 answer
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 ...
MathTrain's user avatar
  • 2,280
1 vote
1 answer
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, ...
Weier's user avatar
  • 785
2 votes
1 answer
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 ...
Julian Newman's user avatar
2 votes
1 answer
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 ...
user34140's user avatar
2 votes
1 answer
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),...
Christian Chapman's user avatar
-2 votes
1 answer
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 ...
Nikolai riber skånstrøm's user avatar
3 votes
1 answer
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 ...
Lassadar's user avatar
  • 171
3 votes
1 answer
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 ...
volcanrb's user avatar
  • 3,054
0 votes
0 answers
98 views

Does Peano's axioms axiomize true arithmetic?

Let $\mathcal{M}_A=\langle\mathbb N, 0^{\mathcal{M}_A}, s^{\mathcal{M}_A}, +^{\mathcal{M}_A}, \times^{\mathcal{M}_A}, <^{\mathcal{M}_A}\rangle$ be the standard model for the language of arithmetic $...
John Davies's user avatar
0 votes
0 answers
66 views

Decoding Gödel's number inside Gödel's number

Since Gödel's numbering maps formulas into numbers, how would a number inside a number that represents a formula be decoded? Let's say I have the following formula of a formal system called TNT (from ...
spacemonkey's user avatar
1 vote
1 answer
170 views

Precise statement of Gödel's Incompleteness Theorems [duplicate]

I have seen the following statements of Gödel's Incompleteness Theorems: Gödel's First Incompleteness Theorem (v1) If $T$ is a recursively axiomatized consistent theory extending PA, then $T$ is ...
Gavin Dooley's user avatar
  • 1,122
0 votes
1 answer
109 views

Confusion about $\mathsf{PA}$'s self-provable consistency sentences

Edit: This long question was basically answered by a quick comment! I'll accept an answer if someone posts one, but it's basically answered already. Background: In Peter Smith's Introduction to Gödel'...
WillG's user avatar
  • 6,672
1 vote
1 answer
144 views

Infinite statements from finite axioms

I want to know if a given finite subset of axioms of PA1 ( 1st order peano arithmetic ) can prove infinite sentences in PA1 such that those proofs need no other axioms except those in the given finite ...
jason's user avatar
  • 1
0 votes
1 answer
113 views

is arithmetic finitely consistent? [duplicate]

Let's take PA1( First order axioms of peano arithmetic ) for example. From godel's 2nd incompleteness theorem, PA1 can't prove its own consistency, more specifically it can't prove that the largest ...
jason's user avatar
  • 1
0 votes
1 answer
33 views

Can a second-order theory that contains the first-order theory of the structure (N,+,x,1) have a decidable axiomatization?

Hedman in his "A First Course in Logic" (2004) says, in p.359, "... we now demonstrate a second-order theory containing $T_N$ that does have a decidable axiomatization." where $T_N$...
Ozgur Demir's user avatar
7 votes
1 answer
289 views

Is there a theory stronger than ZFC in consistency but does not prove its consistency?

A theory $T$ in the language of set theory is stronger than another theory $T'$ in consistency if consistency of $T$ implies consistency of $T'$. If $T$ is able to formalize finite arguments, proves ...
Noiril's user avatar
  • 590
1 vote
2 answers
159 views

Circularity in the argument that Gödel's incompleteness theorems undermine Hilbert's program

I'm only familiar with the very basics of mathematical logic, but over the last few days I have been looking into Gödel's incompleteness theorems and it seems to me (but I might simply be grossly ...
Inzinity's user avatar
  • 1,773
3 votes
1 answer
221 views

Consistent theories $T$ such that $T+\mathrm{Con}(T+\mathrm{Con}(T))$ is inconsistent

In this question, it is asked whether there is a theory $T$ such that $T$ is consistent but $T+\mathrm{Con}(T)$ is inconsistent. The answer is yes: for instance, $T=\mathsf{PA}+\neg\mathrm{Con}(\...
Joe's user avatar
  • 20.7k
0 votes
0 answers
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 ...
ampersander's user avatar
8 votes
1 answer
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 ...
James King's user avatar
0 votes
1 answer
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 ...
Rojus Lukauskas's user avatar
1 vote
1 answer
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 ...
Jianing Song's user avatar
  • 1,923
1 vote
0 answers
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 ...
user avatar
2 votes
1 answer
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-...
user avatar
2 votes
1 answer
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 ...
Quuxplusone's user avatar
0 votes
0 answers
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 ...
Caleb's user avatar
  • 19
1 vote
1 answer
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 ...
Jianing Song's user avatar
  • 1,923
0 votes
1 answer
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, ...
Zuhair's user avatar
  • 4,631
0 votes
0 answers
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 ...
Tullia Lupino's user avatar
1 vote
1 answer
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 ...
Anonymous's user avatar
1 vote
2 answers
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 ...
ThePhilosopher's user avatar
1 vote
0 answers
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 ...
Axel Bregnsbo's user avatar
2 votes
0 answers
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 ...
Zuhair's user avatar
  • 4,631
2 votes
1 answer
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 ...
Zuhair's user avatar
  • 4,631
1 vote
0 answers
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 ...
Zuhair's user avatar
  • 4,631
1 vote
0 answers
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&...
Mikayla Eckel Cifrese's user avatar
1 vote
1 answer
81 views

Questions about incompleteness theorems

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 ...
Teddy Astor's user avatar
2 votes
0 answers
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 ...
Griffin Staples's user avatar
1 vote
1 answer
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'...
leon.fuchsler's user avatar
3 votes
3 answers
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 ...
WillG's user avatar
  • 6,672
0 votes
1 answer
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 ...
user107952's user avatar
  • 21.4k
2 votes
1 answer
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 ...
Zuhair's user avatar
  • 4,631
1 vote
1 answer
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 ...
user19872448's user avatar
-2 votes
1 answer
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 ...
Yang Xuezhi's user avatar
38 votes
6 answers
6k views

Are there more truths than proofs?

Noson Yanofsky is a theoretical computer scientist at Brooklyn College. He presents the following argument on pages 329-330 of his book The Outer Limits of Reason, published by the MIT Press. The set ...
simple jack's user avatar
8 votes
2 answers
206 views

Is it possible to construct proof systems that look consistent for short proofs, but are actually inconsistent?

What's the shortest axiom you can add to a system like ZFC to make it inconsistent such that the shortest proof of a contradiction has length n? Is the length of the axiom lower-bounded by Ω(n), or is ...
Taylor Hornby's user avatar

1
2 3 4 5
18