Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
775
questions
-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") ...
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 ...
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,...
- 290
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 ...
- 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. "...
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 ...
- 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 ...
- 763
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-...
- 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 ...
- 9
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 ...
- 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 ...
- 9
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}$) ...
- 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 ...
- 145
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 ...
- 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 ...
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 ...
- 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, ...
- 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-...
- 305
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$ ...
- 218k
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 ...
- 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 ...
- 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 ...
- 73
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 ...
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 ...
- 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 ...
- 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 ...
- 6,912
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 ...
- 81
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 ...
- 21
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 ...
- 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)$?
...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 &...
- 67
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 ...
- 101
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 ...
- 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:...
user375735
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 ...
- 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;...
- 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 ...
- 13.2k
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 ...
- 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 ...
- 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 ...
- 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
- 13
-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 ...
- 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 ...
- 133
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: "...
- 125
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 ...
- 909
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 ...