Questions tagged [incompleteness]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
87 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,467
1 vote
1 answer
121 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
95 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
30 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
264 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
  • 473
0 votes
1 answer
167 views

How can one show that arithmetic is consistent? [duplicate]

I have recently came across this article https://www.mathpages.com/home/kmath347/kmath347.htm, which talks about whether arithmetic is consistent. I believe that what I intuitionally know about ...
keska_learning's user avatar
0 votes
2 answers
127 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,713
3 votes
1 answer
196 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
  • 19.4k
0 votes
0 answers
38 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
85 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
112 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,528
1 vote
0 answers
70 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
194 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
76 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
162 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
126 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,528
0 votes
1 answer
174 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,525
0 votes
0 answers
93 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
105 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
103 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
83 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
90 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,525
1 vote
1 answer
93 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,525
1 vote
0 answers
177 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,525
1 vote
0 answers
61 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
78 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
53 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
106 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
174 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,467
0 votes
1 answer
79 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
  • 20.1k
2 votes
1 answer
113 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,525
1 vote
1 answer
78 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
288 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
202 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 vote
0 answers
41 views

Proof of Incompleteness - Existence of Gödel number $g$ [duplicate]

I was watching a video: https://youtu.be/HeQX2HjkcNo?t=1171 and had a quesion on the incompleteness proof. In the video, he introduces us to the statement: "There is no proof for the statement ...
B2VSi's user avatar
  • 1,005
0 votes
1 answer
49 views

Godel Theorem proof in algorithm theory

I am currently reading the Gödel's Incompleteness Theorem explained by Vladimir A. Uspensky. And I came across the following theorem which I think has contradiction with itself. Since I am a physics ...
Kid A's user avatar
  • 43
6 votes
0 answers
101 views

Who is the "$\Pi_2$-soundness" version of the first incompleteness theorem due to?

I'm trying to remember who is responsible for the following well-known weak version of the first incompleteness theorem: Suppose $T$ is a c.e. consistent $\Pi_2$ extension of Robinson's $\mathsf{Q}$ (...
Noah Schweber's user avatar
2 votes
1 answer
82 views

Are there "Godel encodings" for non-arithmetic theories?

This is probably a very naive question, but is there something about Godel encoding that is essentially arithmetical, or is it possible to construct analogous mappings between the objects studied in a ...
Rando McRandom's user avatar
2 votes
0 answers
32 views

Gödel's first incompleteness theorem from halting problem using soundness. Is it possible to use semantic consistency?

Here is my proof of a variation of Gödel's first incompleteness theorem (Theorem 1). It uses soundness as one of the hypothesis. I would like to know if it would be possible to prove Theorem 2. ...
mianfg's user avatar
  • 31
1 vote
0 answers
61 views

Gödel's incompleteness theorems for soundness or semantic consistency

I am learning about Gödel's incompleteness theorems, and I want to prove them using the undecidability of the halting problem. So far, here is the result I have been able to prove: Theorem 1 (First ...
mianfg's user avatar
  • 31
0 votes
0 answers
50 views

How to prove the Gödel sentence is true (in the metalanguage), assuming only consistency of a theory.

Let $T$ be a consistent, axiomatizable extension of $Q$ (Robinson or Minimal arithemthic shouldn't matter). We construct the Gödel sentence by using the diagonal lemma as: $\vdash_T G_T \...
Andrew Bayer's user avatar
3 votes
0 answers
167 views

Prove the Gödel theorem using the Busy Beaver function

Assume we know the following for a fact: $L$ is an arithmetic language and contains a formula (abbreviated “$BB(x_i, x_j)$”) expressing the Busy Beaver function, i.e. $BB(k, n)$ is true if and only ...
ASA's user avatar
  • 400
0 votes
1 answer
83 views

Is the sublanguage immune from Gödel theorem

Let $L^{{10}^{100}}$ be the sublanguage of an arithmetic language $L$ consisting of formulas of $L$ with ${{10}^{100}}$ symbols or fewer. is there a Turing Machine M that when run on an empty input ...
ASA's user avatar
  • 400
0 votes
0 answers
47 views

Negation completeness and maximally consistent

Hello I have been struggeling with the following questions: We here introduce a notion of completeness slightly different from the one discussed in the lecture. A set of formulas $\Gamma$ is complete ...
Allison's user avatar
  • 111
3 votes
1 answer
392 views

How do mathematicians know if they are extending the theory of natural numbers in the right direction?

According to Godel's incompleteness theorem, any formal system can never deduce all the truths about the set of natural numbers. Hence, to deduce more truths than we were able to before, we extend our ...
Ryder Rude's user avatar
  • 1,417
2 votes
0 answers
55 views

Is Robinson arithmetic the weakest incompletable system of arithmetic?

Robinson arithmetic (Q) is weaker than PA. We know that any theory that interpret Robinson arithmetic will be incomplete as well. It seems Robinson found his axioms noting what was necessary to ...
Lost definition's user avatar
1 vote
1 answer
91 views

Are there Nonstandard Models of Arithmetic that don't Add Additional Axioms?

Apologies if this is an elementary question that should have been obvious to me. I am learning about these topics very much from the perspective of an outside hobbyist, and am not a wizard of logic. ...
Noam Hudson's user avatar
0 votes
0 answers
100 views

"Proof" that "ZFC + there exists an inaccessible cardinal" is consistent

I have a proof that this theory is consistent using this theory itself. I want to know what's wrong with this proof: "ZFC + there exists an inaccessible caridnal" proves that "ZFC is ...
Ryder Rude's user avatar
  • 1,417

1
2 3 4 5
18