Questions tagged [incompleteness]

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

Filter by
Sorted by
Tagged with
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 ...
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-...
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 ...
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 (...
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 $ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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. "...
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 ...
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 ...

1
2 3 4 5
17