Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
814
questions
0
votes
0
answers
22
views
How to understand Godel's Theorems [duplicate]
Can someone with close to zero knowledge of higher mathematics understand Godel's Theorems or does he first have to learn some mathematics? If the answer to the first part of the question above is yes,...
2
votes
0
answers
54
views
Can Gödel's theorem be proved within PA?
Gödel proves his theorem informally by using natural languages. However, is there a way to carry out his proof in PA itself? (so that maybe PA could prove that itself could not prove its own ...
- 21
0
votes
1
answer
41
views
Gödel's second incompleteness theorem and Consistency.
According to Gödel's second incompleteness theorem, no consistent axiomatic system which includes Peano arithmetic can prove its own consistency. As I understand it, this result contributed to spark a ...
- 1,261
0
votes
1
answer
44
views
How valid are the statements of ZFC being consistent up to very extreme ordinals?
By Gödel's incompleteness theorem, we can't prove ZFC consistent in ZFC. But "naturally" we believe so. So we could add the axiom "ZFC is consistent" and call the new axiom set ZFC-...
- 99
2
votes
1
answer
107
views
What is the mathematical definition of "standard arithmetic/standard natural numbers"?
As a consequence of Godel's incompleteness theorem, no axiomatic system can be the definition of standard natural numbers because any axiomatic system of arithmetic will always be satisfied by non-...
- 1,215
1
vote
1
answer
106
views
What really is the content of Godel's incompleteness theorem: absolute or relative truths?
I've been getting extremely conflicting answers about this. Please help me. A summary of the different viewpoints:
It seems like most people are taking the Platonic viewpoint : that natural numbers ...
- 1,215
1
vote
0
answers
52
views
Making statements about natural numbers using real number system using trigonometric functions
I read that the reason Godel's incompleteness theorem doesn't apply to reals is that the axioms of real numbers aren't strong enough to produce statements about natural numbers arithmetic. And if you ...
- 1,215
1
vote
1
answer
69
views
Does the following intuition about incompleteness makes sense
does this intuition regarding Godel incompleteness theorem makes sense?
Without diving into the details of the formal proof, I had the following intuition why math would be incomplete:
Take any known ...
- 311
3
votes
1
answer
115
views
How does independence play with LEM
I've been thinking recently about how logic interplays with independence results. I should preface this by saying I have essentially no background in logic or set theory, so apologies if these are not ...
- 41
2
votes
0
answers
68
views
Do incompleteness theorems require circular referencing?
Across many fields of math, and related fields like logic and computer science, there are incompleteness theorems that state a system cannot be both consistent and complete. Some examples include (...
- 397
7
votes
1
answer
108
views
Extending a Model of $ T + \operatorname {Con} ( T ) $ to a model of $ T + \neg \operatorname {Con} ( T ) $
Let $ T $ be a recursively axiomatizable extension of $ \mathsf {PA} $ and $ \mathfrak M $ be a model of $ T + \operatorname {Con} ( T ) $. Is it true that there must exist a model $ \mathfrak N $ ...
- 6,539
1
vote
1
answer
77
views
Why is it specified in the 2nd incompleteness theorem that a system of arithmetic cannot prove its own consistency?
I have seen in places I have read about Godel's incompleteness theorem that the second incompleteness theorem can be summarized as saying:
No axiomatic system with sufficiently strong arithmetic can ...
1
vote
1
answer
46
views
Arithmetic theory $T$ such that $U = T + \operatorname{Con}_{T}$ is consistent, but $T + \operatorname{Con}_{U}$ is not.
I have the following problem:
Give an example of arithmetic theory $T$ (i.e $T$ contains $\operatorname{PA}$
and has recursively enumerable set of axioms), such that theory $U = T + \operatorname{Con}...
- 1,113
0
votes
0
answers
45
views
How does consistency PA+¬Con(PA) implies consistency of PA?
There is a question on stack overflow showing that if PA is consistent then PA+¬Con(PA) is also consistent.
The thing is, that it should also work vice versa, that if PA+¬Con(PA) is consistent, then ...
1
vote
0
answers
58
views
Incompletness and infinite induction
I'm currently reading about Inferentialism and proof theoretic semantics. I read in Peregrin's "Inferentialism: Why rules matter" and Baker's "Aspects of the Constructive Omega Rule ...
- 11
-1
votes
3
answers
148
views
Is "$X$ is finite" decidable (in ZFC)?
Disclaimer: This question is about formalizing the idea that a particular set is "finite" in strict first-order ZFC, without any extensions or informal statements, except where otherwise ...
- 4,440
0
votes
0
answers
37
views
Theory of real numbers is decidable but Peano arithmetic is undecidable? [duplicate]
How can the theory of real numbers be decidable while Peano arithmetic is not? Why can't Godel numbering be used to demonstrate a true but unprovable sentence given that the natural numbers that are ...
- 1,374
4
votes
1
answer
49
views
The word problem for groups preceded PH Theorem as a practical undecidability result
The Paris-Harrington theorem is often cited as the first practical instance of an undecidable problem since it doesn't depend on self-reference or diagonalization and is an interesting mathematical ...
- 1,374
0
votes
0
answers
29
views
Are many generalized formula unprovable (related to Godel's first incompleteness theorem)?
Context: I've been reading through the Dover English translation of Godel's paper "On Formally Undecidable Propositions of Principia Mathematica and Related Systems".
It seems the key to ...
- 35
8
votes
1
answer
174
views
Is there a formal definition of a number theoretical statement which is self-referential?
Let our structure be $(\mathbb{N};+,\times,0,1,<)$. From that structure, Kurt Godel constructed a sentence which has two meanings, a straight-forward number-theoretical meaning, and a higher-level ...
- 16.8k
0
votes
0
answers
19
views
Is there a formal system that proves its consistency while proving the existence of a stronger formal system that can interpret general recursion too?
So looking at theorems like incompleteness, it is clear that such properties cannot be found from within. But when we take a more vague approach like simply requiring existence, do these restrictions ...
- 513
2
votes
1
answer
53
views
Godel's incompleteness theorem and proof by contradiction
This is a naive question and I haven't actually read the paper itself (I've read this). But from my understanding he demonstrated that it is possible to encode the statement "This statement ...
- 317
0
votes
0
answers
46
views
Is there any version of arithmetic based on quantum logic? If so are they complete?
I know that there are versions of arithmetic that are complete and self-consistent but they all miss some aspects of numbers as we know : Systems which contain arithmetic
If so, have there been any ...
- 119
3
votes
1
answer
83
views
Identifying the original Godel sentence in his 1931 paper
I've been exploring Godel's original 1931 paper On Formally Undecidable Propositions of Principia Mathematica and Related Systems (I'm using an English-translated version found here). And to pre-empt ...
- 181
0
votes
1
answer
106
views
Have a question regarding this introduction to Gödel foundations of mathematics/incompleteness theorem.
I am a math noob. These questions will likely sound dumb so I apologize ahead of time. But I like to code, and I've been getting into lisp languages. Someone wrote an introductory summary to Gödel ...
- 101
0
votes
0
answers
26
views
How do we find mathematical equation of any statement which is not about mathematics with Gödel numbering?
I have 3 questions and they are closely related so I asked them in same post.
With Gödel numbering we can encode statements like "0 = 0" or maybe "a then b". And this is basically ...
- 1
3
votes
1
answer
71
views
Confused about Logic Machine in The Lady or the Tiger by Smullyan
In The Lady or the Tiger by Raymond Smullyan, on p.172, it says: "I am working in a language that contains names of various sets of numbers--specifically, positive integers. There are infinitely ...
0
votes
1
answer
43
views
Do any of you see any problems re the following reasoning about (1) Gödel’s first incompleteness theorem and (2) the Gödel-Penrose conjecture?
Gödel’s first incompleteness theorem (GT1) states that for every algorithmic set of axioms (AlgoS) capable of expressing basic arithmetic, there exists a true arithmetical statement GS (the Gödel ...
0
votes
0
answers
45
views
How is first order logic complete but not decidable?
I know that there are two different notions of completeness and that we shouldn't be surprised that a theory might be complete (in the sense of the theorem of completeness) but undecidable (so ...
- 53
0
votes
1
answer
92
views
Completeness of real closed fields within ZFC
Tarski proved that the theory of real closed fields (RCF) is complete. But does this theory stay complete when interpreted within ZFC? We know that ZFC can't be complete because it can interpret ...
- 605
1
vote
1
answer
62
views
A true but unprovable sentence $\theta$ that is not a $\Pi$-sentence
Question $4$ from Section $7.7.3$ in "A Friendly Introduction to Mathematical Logic" (Christopher C. Leary and Lars Kristiansen; $2$nd edition):
Let $A = \{\phi \mid \phi \text{ is a } \Pi\...
- 117
0
votes
0
answers
70
views
Is Smullyans Axiom System P.E. correct?
Raymond Smullyan in his book on Gödel's incompleteness theorems introduces a certain axiom system for Peano arithmetic with exponentiation (PE, see below). He then shows that under the assumption that ...
- 2,034
0
votes
1
answer
73
views
Examples of using model existence theorem to show inconsistency
I have seen the model existence theorem many times used to show the consistency of a theory. It works as follows. Let $T$ be a theory. A model $\mathcal{M}$ is given for $T$ and therefore, by the ...
- 369
1
vote
0
answers
50
views
I am looking for some ternary logic with values True/False/Meaningless
I am looking for some alternative logic where a sentence p could not only be True or False but also Meaningless, which is different of false in such a logic.
I see that there is some content about ...
- 237
0
votes
1
answer
62
views
Godelian sentences in other first order languages
I've been asked to teach an intro to logic and computation course. This is not a field that I am particularly familiar with, but I am happy to have the chance to learn it - hopefully - properly.
Since ...
- 65
0
votes
1
answer
56
views
Is Godel's G statement an arbitrary construction or is it derived by rules?
Godel's proof involves a statement G. I undestand that it is losely arranged to look like "This statement G is not provable in this sytem". My question is how this statement was created ...
- 103
1
vote
1
answer
75
views
Regarding Godel's arithmetic technique in Incompleteness Theorem.
This question is about the number system Godel used in his Incompleteness Theorem. It seems that the result of his theorem is that somethings (in mathematics) may never be provable, although they ...
- 103
2
votes
1
answer
35
views
What happens to provability of consistency if we restrict semantics to $\omega$-models?
If we restrict the semantics of a first order theory to only $\omega$-models of it, then if a theory doesn't have an $\omega$-model, then its $\omega$-inconsistent, now an $\omega$-model only have ...
- 4,137
0
votes
1
answer
62
views
Using Gödel's incompleteness theorems to strengthen a proof system
I've recently been looking at Gödel's incompleteness theorems from a very different angle. I'm not new to these theorems at all, but this is a different perspective which I haven't seen posted here ...
- 7,082
1
vote
2
answers
67
views
Is the Goedel sentence of Peano arithmetic provable in true arithmetic?
I'm struggling to answer the following past paper question, which does not have any solution.
It asks simply whether $TA \vdash \gamma_{PA}$, where $TA$ is true arithmetic and $\gamma_{PA}$ is the ...
- 21
0
votes
1
answer
53
views
Can someone please help my differentiate Gödel’s 2 Incompleteness Theorems
Just a small note: I’m taking High School Geometry, so in no way am I advanced in mathematics.
Recently I’ve started a project attempting to explain Gödel’s incompleteness theorems. However I can’t ...
1
vote
1
answer
144
views
Incompleteness Theorem and Proof by Contradiction. [duplicate]
Let me begin first by saying that I have no real background in formal logic, so this question may end up being an ignorant one.
I have recently been to a talk which concerned Godel's Incompleteness ...
- 73
1
vote
0
answers
61
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
67
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,...
- 300
0
votes
1
answer
78
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 ...
- 85
1
vote
0
answers
39
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. "...
- 103
3
votes
1
answer
92
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,707
2
votes
0
answers
141
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 ...
- 802
1
vote
1
answer
75
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-...
- 21
0
votes
0
answers
39
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