Questions tagged [incompleteness]

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

Filter by
Sorted by
Tagged with
-2 votes
0 answers
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") ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
1 answer
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,...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 67
0 votes
0 answers
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. "...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 2,545
1 vote
0 answers
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 ...
user avatar
0 votes
1 answer
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-...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 23
0 votes
1 answer
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 ...
user avatar
29 votes
1 answer
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}$) ...
user avatar
  • 4,878
0 votes
1 answer
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 243
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 58.7k
0 votes
3 answers
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, ...
user avatar
  • 3,695
3 votes
0 answers
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-...
user avatar
3 votes
0 answers
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$ ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 2,615
1 vote
0 answers
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 ...
user avatar
  • 493
4 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 6,426
0 votes
1 answer
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 ...
user avatar
  • 45
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 77
3 votes
1 answer
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)$? ...
user avatar
  • 105
0 votes
1 answer
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 ...
user avatar
  • 639
0 votes
0 answers
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 ...
user avatar
  • 105
3 votes
2 answers
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 ...
user avatar
  • 325
0 votes
0 answers
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 ...
user avatar
  • 239
0 votes
2 answers
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 &...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
  • 604
1 vote
0 answers
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:...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 3
0 votes
1 answer
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;...
user avatar
  • 51
0 votes
1 answer
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 53
0 votes
0 answers
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 ...
user avatar
  • 176
1 vote
1 answer
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 ...
user avatar
  • 155
0 votes
1 answer
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
user avatar
-1 votes
1 answer
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 ...
user avatar
  • 3,707
3 votes
2 answers
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 ...
user avatar
2 votes
0 answers
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: "...
user avatar
1 vote
1 answer
202 views

Does Con(ZFC) imply Con(ZFC+Con(ZFC))?

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 ...
user avatar
0 votes
1 answer
74 views

Is there a chess example of True but Not Provable statement?

I am trying to explain to someone (and also to understand better) Godel's Theorems through a chess example. Indeed I found some examples of True but Not Provable math statements, but they are honestly ...
user avatar

1
2 3 4 5
16