Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
2
votes
1answer
43 views
Decidability of Gödel sentences.
Letting $\text{Pr}(x)$ be a formula that weakly represents the set $\{x:x\text{ is a Gödel code of a provable sentence in PA}\}$, where PA means Peano Arithmetic.
Gödel's first incompleteness theorem ...
0
votes
0answers
17 views
gödel 2. theorem
Is it correct that Gödels 2. theorem says that it is impossible to check if some formulas are sound(aka not contradicting aka consistent)?
What does consistency mean in this context?
Which ...
5
votes
3answers
301 views
Statement true because not provable
It is my understanding that Gödel's second incompleteness theorem says roughly that
there exists a sentence $\varphi$ such that neither $\varphi$ nor $\neg\varphi$ is provable in Peano's arithmetic....
2
votes
1answer
39 views
Consistent theories that proves their own consistence
Restrict the whole question to first order logic only. Gödel second incompleteness theorem tell us that, if, for example, we are working with Peano language, every T (recursively axiomatized, ...
3
votes
2answers
136 views
Question about Goedel's incompleteness Proof
There is only one problem I have with Goedel's proof as explained in Nagel & Newman's book.
It assumes that you can actually construct a G statement along the lines described in the proof in PM, ...
1
vote
2answers
34 views
Variation on Lob's Theorem
Lob's theorem is, of course, if $P(y)$ is a provability predicate for $S$, $S$ diagonalisable, then if $(P(A) \rightarrow A)$ is provable in $S$ then $A$ is provable in $S$. I understand the proof of ...
1
vote
2answers
85 views
Model Theoretical Interpretation of the Incompleteness of Number Theory
This question was sparked by this Numberphile video: https://www.youtube.com/watch?v=O4ndIDcDSGc. Near the end, (12:05), he speaks about the Riemann Hypothesis. He describes that if Riemann is shown ...
4
votes
1answer
128 views
An example of incompleteness?
Is it fair to suggest that the fact a base's symbol which would exist in a higher base but is never truly reflected in the base itself is an example(see below) of incompleteness along the ideas of the ...
9
votes
3answers
3k views
Why doesn't Gödel's incompleteness theorem apply to false statements?
I've read and heard in lectures that
A way to prove that the Riemann hypothesis is true is to show that its negation is not provable.
The argument (informally) usually goes like
If a ...
4
votes
1answer
89 views
Did Gödel's First Incompleteness Theorem ever led to number theoretical insights?
Gödel's First Incompleteness Theorem is based on the construction of a formula - a so-called Gödel formula - stating its own unprovability. Has ever such a formula led to novel insights in number ...
2
votes
1answer
58 views
FOL and Gödel's Incompleteness Theorem 1
My teacher presented Gödel's first incompleteness theorem as follows:
(1) First Incompleteness theorem (Gödel [Rosser]):
Every [$\omega$-]consistent and reasonably expressive system of arithmetic ...
1
vote
0answers
32 views
Theorem for some structure that it cannot be axiomatized in any language?
Godel’s theorem states that there cannot be an enumerable axiomatization of arithmetic $(\mathbb N,0,1,+)$ in first order logic. By implication, there cannot be any axiomatization in any language that ...
1
vote
1answer
54 views
A question on $\omega$-consistency and representable sets
I'm working through Raymond Smullyan's books "Goedel's Incompleteness Theorems" and I can't for the life of me figure this exercise out:
Prove that if all true $\Sigma_0$-sentences are provable in $...
-2
votes
1answer
262 views
Exercise of “Gödel's Incompleteness Theorems” by Raymond Smullyan
Is there a correct solution to Exercise 1 of Chapter 1 of the book "Gödel's Incompleteness Theorems" by Raymond Smullyan? I think it's impossible to find one.
The exercise:
Suppose L is a correct ...
3
votes
1answer
74 views
Is there a computable and complete “probabilistic” theory of arithmetic?
Let $\mathbb T$ be a probability distribution over complete and consistent theories of first order arithmetic that contain $PA$. Additionally, we will require that for any sentence $\phi$ in the ...
4
votes
3answers
117 views
Why does Gödel's Second Incompleteness Theorem undermine Hilbert's program?
Recall that Gödel's First Incompleteness Theorem (denote GIT1) states, roughly, any axiomatic system $S$ stronger than Peano Arithmetic (PA) cannot be "covered" by finitely many axioms.
GIT2 states, ...
0
votes
2answers
74 views
Can sets be constructed in ZFC using possibly undecidable conditions?
Let $P$ denote the set of all prime numbers, $E$ the set of even numbers greater than 2, and $$X:=\{e\in E \,\,|\,\, \exists x,y\in P: x+y=e \}.$$
Note that if Goldbach’s conjecture (that all even ...
0
votes
1answer
43 views
Are there alternative formalizations of consistency that bypass the Second Incompleteness Theorem?
Gödel's Second Incompleteness Theorem expresses the consistency of a formal system within the system itself using a rather carefully designed proof checking predicate. The conclusion of Gödel's ...
1
vote
0answers
47 views
Incompleteness of Robinson's Arithmetic
In Smith's book about Godel's Theorems a proof is given of incompleteness of Robinson Arithmetic. It's done by producing a special interpretation of the theory:
Domain is $N^* = N \cup \{a,b\}$, a ...
0
votes
1answer
62 views
Consistency and Gödel's Incompleteness theorem.
In Mathematical Logic, Kleene states a string of implications that are a result of Gödel's completeness theorem of predicate logic;
$$\{E_1,...,E_k \vdash P\&\neg{P}\} \rightarrow \{E_1,...,E_k \...
0
votes
1answer
109 views
Why doesn't the construction of $\mathbb{N}$ through ordinals in ZFC violate Gödel's Incompleteness Theorem?
The title kind of says it all. I've been working through Axiomatic Set Theory, Suppes and Mathematical Logic, Kleene. And I haven't thoroughly studied ordinals and incompleteness yet. But, ...
0
votes
0answers
9 views
Can completeness due to adding $\omega$-rule be extended to all recursive ordinals?
Is completeness due to $\omega$-rule effected by restricting matters to what the meta-theoretic indices confer? I mean in the case of the ordinary $\omega$-rule, we can do it over the world of finite ...
0
votes
1answer
23 views
Using the halting problem to create statement independent of ZFC
The proof of the halting problem gives us a way to create, for any halting algorithm, a program that the halting algorithm does not decide.
One possible halting algorithm would be enumerating all ...
0
votes
1answer
73 views
How does Godel use diagonalization to prove the 1st incompleteness theorem?
I'm looking for an intuitive explanation of this without too much jargon as I am new to set theory. I understand Cantor's diagonal proof as well as the basic idea of 'this statement cannot be proved ...
-1
votes
1answer
61 views
What decides completability of a first order theory?
[EDIT]: To make the question (the original posting presenting it I've put in a separate section below) non trivial a definition of "inference rule" needs to be given [Noah Schweber] as clearly ...
2
votes
0answers
91 views
Does probability theory suffer from Gödel's incompleteness theorem?
Let us consider the following two theorems by Gödel:
1) Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are ...
-1
votes
2answers
151 views
Proof of Godel's Incompleteness Theorem based on Recursion Theorem
I'm looking for a proof of Godel's Incompleteness Problems based on the recursion theorem in computability theory. I've skimmed lots of textbooks but I haven't found such proof. Can you name some ...
0
votes
0answers
122 views
A Growing Tree of Theories
Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, ...
1
vote
1answer
132 views
Legitimacy of Consistency Proofs
In this question I asked yesterday I put forward two interpretations of a statements such as "System X is consistent". (a) we can think of it as saying no finite sequence of applications of logical ...
3
votes
1answer
109 views
Consistency of PA from a Formalist Perspective
In this lengthy thread there's people bickering back and forth about the consistency of PA (Peano Arithmetic) and misunderstandings abound. In reading it I came to an understanding I found useful, ...
3
votes
0answers
76 views
Godel's theorem incompleteness, truth vs.provability
I know this question has been investigated in other threads, but I would like to pose yet another question on Gödel's theorem incompleteness, and truth in 'the standard model' compared with ...
3
votes
1answer
54 views
Several questions about the incompleteness theorem
I’ve read quite a few pop math books over the years with descriptions of the incompleteness theorem and I think I understand most of the broad details, but some still elude me. Specifically, these ...
2
votes
1answer
130 views
What is the purpose of Semantics/Model theory in Mathematical Foundations?
First off I know very little model theory so apologies if I say anything very dumb or offensive to logicians/model theorists. Second I should note that a lot of what I am saying here is motivated by ...
3
votes
1answer
60 views
Why is $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ a recursive set?
Let $\mathcal{N}=(\mathbb{N},+,\cdot,0,1)$. I want to show that $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ is a recursive set. Here $\#F$ is the Gödel number of $F$ and ...
2
votes
1answer
39 views
Gödel diagonalization and formulas not holding for themselves
Is there a formula $\varphi (n)$ in one free variable $n$ in ZFC (PA etc.) such that for every formula $\psi(n)$ in one variable the equivalence
$$ \varphi ( \ulcorner\psi\urcorner) \leftrightarrow \...
1
vote
1answer
70 views
What was the exact form of Gödel's original Second Incompleteness Theorem?
Gödel's second incompleteness theorem is usually stated as:
Any consistent formal system $F$ capable of elementary arithmetic can't prove its own consistency.
I'm having trouble deducing this ...
2
votes
0answers
112 views
n-consistency - provability/truth of $\Sigma^0_n$ and $\Pi^0_{n+1}$ -formulas; n-consistent extensions, etc.
I am facing difficulties with the following exercise.
(It is 1.5.9. from 'proof theory and logical complexity', Girard, '87)
(i) T is $\textbf{n-consistent} \ (n>0)$ if any $\Sigma^0_n$ - theorem ...
0
votes
1answer
103 views
Undecidable statement that doesn't involve infinity
All statements independent of ZFC I'm aware of involve infinity.
Do we know any statement independent of ZFC of the form $\forall n \in \mathbb{N}: P(n)$ where $P(n)$ is disprovable if false? (In ...
2
votes
1answer
69 views
Ordering between formal theories by provability of consistency
I am studying proof theory with Girard's monograph from '87 ('proof theory and logical complexity').
1.5.6. is an exercise called 'ordering between theories'.
It reads as follows:
" (i) Let $\...
1
vote
0answers
48 views
Are the HBL derivability conditions necessary for Gödel's incompleteness theorems? (For Löb's theorem?)
I am currently working with 'proof theory and logical complexity', a monograph on proof theory.
In the exercises of the first chapter one was asked to prove Löb's theorem (https://en.wikipedia.org/...
1
vote
1answer
116 views
An alternative formulation (or corollary) of Tarski's theorem? [Or just a typo?]
In my proof theory monograph (proof theory and logical complexity, Girard from '87) there is an exercise 1.5.4. on page 78 called 'Tarski's theorem'.
It says:
"Show that there is no truth predicate ...
1
vote
0answers
111 views
Why the 'natural' consistency proof of PA cannot be carried out $\textbf{in}$ PA
In my proof theory monograph there is this exercise:
"The natural proof of PA cannot be carried out in PA. Why?
(This proof consists in showing that all theorems of PA are ture.)"
Apparently, by '...
2
votes
0answers
64 views
Is every theory meeting Gödels incompleteness, also incomplete below its consistency level?
Is it always the case that for any theory $T$ that meets Godel's criteria for incompleteness, there is a sentence $P$ such that neither $T \vdash P$, nor $T\vdash \neg P$; and such that $T+P$ is equi-...
3
votes
1answer
110 views
Example of incomplete, but decidable theory, and of complete and undecidable theory, question
On wikipedia it is written that
Decidability should not be confused with completeness. For example, the theory of algebraically closed fields is decidable but incomplete, whereas the set of all ...
3
votes
2answers
132 views
How can a formal system ever be non-obviously unsound?
When reading about formal systems one is often warned that, even assuming the system is consistent, one can't be sure that any theorem proved in the system is actually true. For instance, if one can ...
15
votes
2answers
827 views
Gödel's completeness theorem and the undecidability of first-order logic
I'm working through this module, "Undecidability of First-Order Logic" and would love to talk about the two exercises given immediately after the statement of Godel's completeness theorem.
First, ...
3
votes
0answers
96 views
Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas $\{\varphi$ $\mid$ for every $M$-assignment $\...
2
votes
1answer
79 views
Why is $\forall x (x = x)$ an example of a first order sentence that is neither provable nor disprovable?
In the first answer to this question:
What is the difference between syntactic and semantic completeness?
the sentence $\forall x (x = x)$ is given as an example of something that is neither ...
17
votes
4answers
2k views
Why can't we prove consistency of ZFC like we can for PA?
this might be a silly question, but I was wondering: PA cannot prove its consistency by the incompleteness theorems, but we can "step outside" and exhibit a model of it, namely $\mathbb{N}$, so we ...
3
votes
2answers
98 views
Gödel's incompleteness 1: construction of the formula relating Gödel number of proof to Gödel number of proven statement
I'm trying to understand the proof sketch of Gödel's Incompleteness Theorem 1 on Wikipedia (https://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem)
In particular, ...
