# Questions tagged [incompleteness]

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

814 questions
Filter by
Sorted by
Tagged with
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,...
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
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
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-...
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
106 views

• 1,215
1 vote
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
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 ...
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
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
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
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
46 views

• 117
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
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
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
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 ...
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
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 ...
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
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
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
53 views

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
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
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 ...
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
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
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. "...
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
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
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 ...