# Questions tagged [incompleteness]

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

775 questions
Filter by
Sorted by
Tagged with
41 views

### Can Cantor's diagonal argument be used for an informal proof of the internal inconsistency of formal logic systems?

So I've been thinking about how Cantor's diagonalization argument might be analogous to Tarski's theorem on the undefinability of truth ("Arithmetical truth can't be defined in arithmetic") ...
1 vote
46 views

### Why can't we add a self-consistency axiom to an already consistent system?

Gödel's incompleteness tells us no consistent formal system can prove its own consistency. I understand that we can add an axiom to formal system $A$ stating "$A$ is consistent" and get a ...
61 views

### How Gödel's first incompleteness theorem can be used for proving statements true or false

If Gödel's first incompletness theorem states $$\exists S: g(S)=g(\neg P(g(S)))$$ Where $g$ is the Gödel numbering of the statement. Since there is a proof that this statement is true but has no proof,...
• 290
55 views

### Is PA provably definable?

A set of sentences $S$ from the language of arithmetic is called definable if there is a formula $\phi(x)$ such that $\mathbb{N} \models \phi(n)$ iff $n$ is the Gödel number of a formula from $S$. A ...
• 67
26 views

### Is there an equivalent to Godel's theorem that looks like "This statement is provable."? [duplicate]

I've been thinking about Godel's thoerem and the liar's paradox. The liar's paradox, when flipped around, stops being a paradox and becomes valid logically whether the statement is true or not. "...
55 views

### Provable equivalence of two Gödel sentences

Fix a Gödel numbering scheme, and let $\operatorname{Thm}_{\mathsf{PA}}$ be the corresponding numerical provability predicate for Peano arithmetic. Suppose $\theta$ and $\xi$ are two sentences in ...
• 2,545
1 vote
83 views

### Is consistency with the $\omega$-rule absolute to $\omega$-models?

According to Wikipedia, a theory $T$ that interprets arithmetic is consistent with the $\omega$-rule if and only if it has an $\omega$-model. That would mean that consistency with the $\omega$-rule is ...
50 views

### Inconsistency and omega-inconsistency (Godel's Incompleteness Theorems)

I am reading Godel's Incompleteness Theorems by Raymond Smullyan. On page 57 of the book, it says that is a system S is simply inconsistent, then every sentence is provable in S, and thus S is omega-...
• 1
30 views

### Godel-Rosser Thoerem if T proves ¬R.

I report here the Rosser trick as presented on Mendelson book: $$(∀x2(Pr(x1,x2) → neg(x1,x3) → (∃x4 ≤ x2 (Pr(x3,x4)))$$ this has one free variable $x1$, and for diag lemma $R ⟷ φ([R])$. The case ...
64 views

### Is type theory complete by definition?

From my understanding, type theory is its own deductive system, meaning that types have propositional meanings. Therefore, an element of a type appears to be an evidence of the truth of the ...
• 23
58 views

### Primitive Recursion representation in first order PA (Gödel theorems)

I'm a bit confused on the reasons why when proving that primitive recursion rule is representable in a PA first order theory one has to utilize ways such as the Gödel function to encode finite ...
2k views

### Can Peano arithmetic prove the consistency of "baby arithmetic"?

I am reading Peter Smith's An Introduction to Gödel's Theorems. In chapter 10, he defines "baby arithmetic" $\mathsf{BA}$ to be the zeroth-order version of Peano arithmetic ($\mathsf{PA}$) ...
• 4,878
90 views

### Why was it important for Peano arithmetic to prove ITS OWN consistency?

A paraphrase of Gödel's Second Incompleteness Theorem into non-technical language states that, if a formal system is powerful enough to express Peano arithmetic, that system is unable to prove its own ...
• 145
114 views

### ZFC and Con(MK)

ZFC is a common axiomatic system, and so is MK. The latter is significantly stronger since it can deal with proper classes. Definition: A cardinal $\kappa$ is inaccessible if it is regular and the ...
• 243
62 views

### How are truth tables used in math?

I am studying symbolic logic, and the textbook I am using Understanding Symbolic Logic by Virginia Klenk says that the proof method and the truth table method will always yield the same results, for ...
1 vote
41 views

### Can Peano arithmetic be completed using only atomic $\omega$-completions?

Say we have an axiomatizable theory $T$ extending $Th(A_E)$ where $A_E$ are the axioms of arithmetic. What I call an atomic $\omega$-completion of $T$ (I am not sure if there is a more standard ...
• 58.7k
121 views

### Does this proof of Godel's incompleteness theorem rely on soundness?

The proof of Godel's first incompleteness theorem is often paraphrased like this. First, find a sentence $\phi$ which is true exactly if it is not provable. If $\phi$ is false, it must be provable, ...
• 3,695
56 views

### Would a proof-search for a contradiction halt in non-standard models of PA arithmetic?

I recently came across the following claim in Eliezer Yudkowsky's post about the limits of first-order logic “ Suppose I build a Turing machine that looks for proofs of a contradiction from first-...
194 views

### Which sentences are irreducibly self-referential?

Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers. Now asked at MO. Say that a sentence $\varphi$ ...
• 218k
1 vote
56 views

### Are there any arithmetic statements where there does not exist a proof proving the statement?

Because of Godel's Incompleteness Theorems, there must exist certain statements about the numbers which have no proof via the Peano axioms. This includes The Strengthened Ramsey Theorem. However, this ...
• 2,615
1 vote
137 views

### Why do we care about PA proving itself consistent?

"No first-order theory containing a sufficient amount of arithmetic can prove its own consistency". It's the "prove its own" part of Godel's theorem that always confused me. Why do ...
• 493
67 views

### Is incompleteness preserved by interpretations?

Let $T$ be an incomplete theory, in the sense that there is a formula $\phi$ of the language of $T$ and there are two models of $T$, $M$ and $M'$, such that $\phi$ is true in $M$ and $\neg \phi$ is ...
98 views

### Is there a mathematical system that is: complete, consistent, and decidable?

I know very little about modal logic (only some set theory) in mathematics, but I am aware that there exists a completeness theorem, incompleteness theorem, and the axiom choice, and that maths is not ...
1 vote
70 views

### Is there a way to state the (in)completeness theorem for an arbitrary deductive system?

Is there a way to state the content of completeness theorems "in general" that a) treats logics like FOL and SOL and theories like arithmetic the same way and b) does not make explicit ...
• 6,426
109 views

### Gödel's Incompleteness Theorem - question

Could someone correct me on the below logic. If a statement cannot be proved then I cannot find a contradiction to said statement. If I cannot find a contradiction to said statement then that ...
• 45
1 vote
57 views

### Enumerating axioms of PA in nonstandard models: trouble in the Kripke-Putnam proof of Gödel's incompleteness theorem

I'm trying to understand the Kripke-Putnam proof of Gödel's incompleteness theorem, somewhat recently cited in this MO question, and can't figure out how to close a gap in the argument. I apologize ...
• 6,912
1 vote
42 views

### Proving incompleteness without unbound quantifiers

I am reading An Introduction to Godel's theorems. On page 113, the author aims to prove that the language of Peano arithmetic can express every primitive recursive function, and later proves that it ...
• 81
1 vote
39 views

### Russel's antiparadox and Godel's incompleteness [duplicate]

In the famous paradox Russell tries to construct the set of all sets not containing itself. Then the question whether this whole set contains itself leads to a contradiction - if it does not contain ...
125 views

### Is the Godel sentence considered true intuitionistically?

In classical logic, Godel shows that there are true statements undecidable for arithmetic, and consequently, that truth goes beyond a system of axioms ability for proof. My question is, given that ...
• 77
84 views

### PA├ ∃xP(x) but PA$\nvdash$ P(n) for any n?

Problem : Let P(x) be a wff with one free variable x in the language of PA and $PA\vdash \exists P(x)$. And let PA be $\omega$-consistent. Then, is there a natural number $n$ s.t. $PA\vdash P(n)$? ...
• 105
182 views

### Gödel's Incompleteness Theorem and Theories which are not recursively axiomatizable

I'm trying to understand the full extent of Gödel's Incompleteness Theorem with regards to what types of consistent and complete theories it rules out. Does it only prove that number theory/ZFC cannot ...
• 639
38 views

### How to prove the 3rd HBL derivability condition in PA?

How $PA\vdash (x=y \rightarrow Prov(\overline{x=y}))$ holds, where $\overline{x=y}$ means a Godel number of x=y? I'm studying ch.35 of the book "An Introduction to Gödel's Theorems" by Peter ...
• 105
272 views

### What is the author trying to explain here?

From Aaronson's 2006 lecture notes for PHYS$771$: ... Why the Incompleteness Theorem doesn't contradict the Completeness Theorem? The easiest way to do this is probably through an example. Consider ...
• 325
50 views

### Incompleteness of Herbrand/Functional-logic

The following is an excerpt from the course CS-157, Introduction to Logic, Lesson 12.2. ... that Herbrand Logic is inherently incomplete, it is not surprising that Herbrand Logic is not compact. What ...
• 239
83 views

### why Gödel use $[R(n);n]$ in his introduction?

in "on formally undecidable propositions of principia mathematica and related systems"'s introduction, Gödel used the notation $R(n)$ and $[R(n); n]$ to state the unprovable formula meaning &...
• 67
26 views

### Analogy between incompleteness theorem and infinite primes

I am self-learning about Godel's incompleteness theorems and think that this analogy is good: When trying to prove that infinite primes exist we assume finite number of them exist and then we arrive ...
• 101
201 views

### Incompleteness theorem: Peano arithmetic vs. standard model of arithmetic

Context (from https://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic#From_the_incompleteness_theorems): The incompleteness theorems show that a particular sentence G, the Gödel sentence of ...
• 604
1 vote
82 views

### Characterization for unprovable formulas for first-order logic

Is there any existing work on characterizations of the unprovable formulas in (general) first-order logic? i.e. Gödel's incompletness result constructs an explicit formula that is valid but unprovable:...
149 views

### An effective procedure to disproof Church-Turing thesis?

Suppose that an effectively axiomatized consistent formal system P that contains enough arithmetic for Gödel's Incompleteness theorems to apply, proves for any undecidable formula φ in the language of ...
• 3
52 views

### How does Godel's Incompleteness Theorem generalise to some Mathematical Theorem/Conjecture [duplicate]

So I was recently reading the proof of the incompleteness theorem (again), and there is one thing thats bugging me. I understood everything until the point that you create a self referential statement;...
• 51
99 views

### Is this an example of the incompleteness of first-order PA?

Although the usual natural numbers satisfy the axioms of PA, there are other models as well (called "non-standard models"); the compactness theorem implies that the existence of nonstandard ...
• 13.2k
290 views

### Why is it accepted that Gödel uses a self-referential statement in his incompleteness theorems?

(I have only read second-hand about Gödel's incompleteness theorems, so I hope that there is nothing I have missed by doing that which would render my questions easily clarified.) Gödel's first ...
• 53
41 views

### If a statement implies an undecidable statement, does that make it undecidable itself?

Wikipedia writes that in every consistent formal system that satisfies Gödel's first incompleteness theorem there exist statements about natural numbers that are true, but that are unprovable within ...
• 176
1 vote
160 views

### what are prerequisites for understanding Godel's incompleteness theorem??

I want to fully understand Godel's incompleteness theorem. my background knowledge are these: analysis1, linear algebra1,2 , abstract algebra1, topology1 and I studied logic by myself while reading ...
• 155
73 views

### A question from Enderton's Mathematical Introduction to logic [closed]

Why we can't deduce S3 from AE? This is from Enderton's Mathematical Introduction to logic page 203 enter image description here
141 views

### What is the exact, formal statement of Gödel's first incompleteness theorem?

I am looking for the explicit formal statement of Gödel's first incompleteness theorem in a formal language (which I assume is the language of first-order Peano arithmetic), permitting only the ...
• 3,707
135 views

### What does Gödel’s First Theorem mean? [duplicate]

From Wikipedia, Gödel’s first incompleteness theorem states that “no consistent system of axioms whose theorems can be listed by an effective procedure (i.e. an algorithm) is capable of proving all ...
103 views

### Completeness of the Reals (Tarski's Theorem)

I have a few questions about Tarski's theorem on the field of real numbers. The theorem states that $$\{\mathbb{R}:0, 1, +, ·, <\}$$ with the ordered field axioms augmented with the axioms: "...
1 vote
Assume that the consistency of ZFC set theory implies the consistency of ZFC+Con(ZFC), where the latter adds the axiom that ZFC is consistent. $ZFC+Con(ZFC) \vdash Con(ZFC)$, because it took it as an ...