Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
697
questions
1
vote
1answer
37 views
Relation between Halting problem and Godel's incompleteness Theorem
I've heard that these are closely related to each other.
However, while the former looks totally trivial to me, the latter still puzzles me even after I read the proof of it. So I made up a scenario ...
2
votes
0answers
21 views
Proving $PAE ⊢ (Pr_S(\#(X → Y)) → (Pr_S(\#(X)) → Pr_S(\#(Y))))$, where $Pr_S(n)$ holds iff $n$ is the Gödel number of a formula provable from $S$
I'm trying to solve the following question set by my professor:
Show that if $S$ is a definable set of sentences, and $Pr_S$ is an associated proof
predicate, and $X$ and $Y$ are any formulae, then $...
3
votes
0answers
35 views
Proving a result similar to the diagonal lemma/fixed-point theorem
As the title explains, I'm trying to solve the following exercise that was left for the reader in my lecture notes:
Show that for any two formulae $F(v_1)$ and $G(v_1)$ in $L_E$ (language of ...
0
votes
1answer
43 views
Prove that ever $\Sigma_0$ sentence is provable from PA (Peano Arithmetic, with exponentiation)
I am trying to study the intuition and steps leading up to proving Godel's Incompleteness theorems. In a text I am studying it asserts that every true $\Sigma_0$ sentence is provable from PAE (where ...
0
votes
1answer
75 views
Is there any way to avoid Gödel incompleteness theorem?
I was wondering whether there have been successful attempts to avoid somehow the incompleteness theorem.
Many point out that every language that is powerful enough to model natural numbers can produce ...
0
votes
1answer
26 views
Showing that formulae which are provably $Σ_n$ and $Π_n$ ($n > 0$) in the arithmetical hierarchy are closed under $∃$ and $∀$ respectively
As the title explains, I'm trying to solve the following problem:
Show that for $n > 0$, formulae provably $Σ_n$ with respect to PA are closed under existential
quantification, and formulae ...
0
votes
0answers
36 views
Can a finite Turing machine model itself?
Given the following constraints, can a finite Turing machine (FTM) model itself?
An FTM receives only data initially stored on its tape;
The amount of initial data on the tape is limited to $D_{m}$ ...
1
vote
1answer
49 views
On the Possibility of Godel Numbering
I've gotten to the point of the book Godel, Escher, Bach which really gets into demonstrating the mechanisms of Godel's incompleteness proof. I've had to go back ...
0
votes
0answers
31 views
Axioms which are used to prove Gödel's second incompleteness theorem [duplicate]
Gödel's second incompleteness theorem concerns the question of proving consistency of certain axiomatic systems.
But what set of axioms is used to prove Gödel's second incompleteness theorem itself? ...
0
votes
0answers
39 views
Defining a consistent complete system in terms of decidable statements.
Say we take a consistent but incomplete formal system such as ZFC, which has theorems (provably true statements) and negated-theorems (provably false statements).
I want to define a system, T, the ...
1
vote
1answer
38 views
Can the existence of some positive integers satisfying some equations ever be independent of ZFC?
In a subject like number theory there are often open questions along the lines of 'Are there positive integers $a_1 , \ldots , a_n $ satisfying the following (finite number of) equations'. For example ...
0
votes
1answer
50 views
Why doesn't the Continuum Hypothesis show that $\text{ZFC}$ is simply consistent? [duplicate]
Where is my error?
A system is simply inconsistent is every formula is provable (if $\text{A} \wedge\neg \text{A}$ were provable for some formula $\text{A}$, then by $\neg$-introduction, any formula ...
1
vote
1answer
34 views
How does Ramsey Theory relate to Godel Incompleteness theorem?
My knowledge in math is not too advanced but I am super interested in this topic and although I think I know part of the answer, I do not know for sure how these two theories are related.
Also, if ...
4
votes
1answer
96 views
In what formal system is Godel's Incompleteness Theorem (or similar statements of undecidability) proven?
For example, consider the proof using Rosser's trick as shown on wikipedia.
https://en.wikipedia.org/wiki/Rosser%27s_trick#The_Rosser_sentence
That proof isn't inside the arithmetical theory T, but in ...
0
votes
1answer
66 views
Existence of proof of consistency of stronger axiomatic systems
Assume $\mathsf{ZFC}$ is consistent. Are there axioms $\mathsf{P}$ and $\mathsf{Q}$ independent from $\mathsf{ZFC}$ such that?:
$\mathsf{Q}$ is a stronger axiom than $\mathsf{P}$
There is a proof ...
1
vote
1answer
80 views
Peano Arithmetic - Decidability
I need to show that if Peano Arithmetic does not decide a sentence $\varphi$ then the standard model
of Peano Arithmetic satisfies the negation of $\varphi$.
I know this partly has to do with Godel's ...
0
votes
1answer
45 views
Godel Escher Bach: Why is a Godel proof-pair representable in TNT?
On page 441, fundamental fact 2 asserts that:
The property of forming a proof-pair is testable in BlooP, and consequently, it is represented in TNT by some formula having two free variables.
Why is ...
1
vote
1answer
53 views
Question about a proof of Gödel's 1st incompleteness theorem
I am confused about one of the standard proofs of this theorem that I've seen. I believe it's a small thing that I missing as authors seem to skip straight through it. The proof I am referring to is ...
0
votes
0answers
38 views
Could mathematics be based on CWA?
https://en.wikipedia.org/wiki/Closed-world_assumption
Would proposition with free variables still be writable in such a system ? If not, would it be a problem since theorems are usually closed ...
-1
votes
1answer
77 views
Does Godel 1st theorem make sense?
It seems to me that there is 2 family of statements that I call "logically undecidable" (to distinguish with computationally undecidable which is define by turing machines), i.e. of ...
1
vote
1answer
39 views
Proving a theorem in GL modal logic
I'm trying to prove a number of theorems in the system GL using the basic axioms of system K and the following axiom schema from GL: $\vdash_G \Box A \rightarrow \Box\Box A$ for every A.
One of ...
1
vote
1answer
72 views
Can't understand definition of system $P$ given by Kurt Godel in his “On formally undecidable propositions…”
I am reading On formally undecidable propositions of Principia Mathematica and related systems by Kurt Godel. And I am not quite sure I am getting his definitions right. See the screenshot beneath:
.....
2
votes
1answer
54 views
Incompleteness Theorems for Limit-Computable Formal Systems
Godel’s First and Second Inconpleteness Theorems are about Peano Arithmetic, but their punchlines are respectively that “Any sufficiently expressive computable formal system cannot be complete and ...
-1
votes
1answer
34 views
Boolos’s proof of the first incompleteness theorem. Predicate $C(x,y)$ and assumption of completeness.
I am trying really hard to understand how Boolos’s proof works, but I keep having doubts about it. Can you spot any logical flaws in my reasoning? This question arose from a previous question of mine, ...
2
votes
1answer
91 views
Why does math work if there are too many paradoxes?
I'm a newbie that studies applied maths and I have been learning about measure theory for the past few weeks and I came across things like Banach–Tarski paradox, Gödel's incompleteness theorems, axiom ...
1
vote
0answers
33 views
Avoiding self reference and proving incompleteness via elementary means.
I am in process of reading Logic and Godel incomplete proof (not completed) when the following two thought pop up in my head.
I think I can show incompleteness through elementary reasoning
A Proof ...
0
votes
1answer
286 views
Boolos’s proof of Gödel’s first incompleteness theorem. What am I getting wrong?
Sorry in advance, the following is quite messy, I didn’t find a way to express myself more clearly and rigorously. I would appreciate suggestions on how to make the following better and try to act ...
-6
votes
1answer
165 views
Gödel's first incompleteness theorem. What did I get wrong? [closed]
I'd like to point out that obviously I don't claim the following to be right, and I now recognise that the way my question was phrased before editing could have been interpreted as very arrogant, and ...
2
votes
0answers
53 views
How can I prove that primitive recursion “preserves” representability in Peano Arithmetic?
I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.
By recursive function ...
0
votes
0answers
55 views
Constructive nature of Gödel's Incompleteness Theorem
Let $E_n$ be an expression with Godel number $n\in\mathbb{N}$. Then we denote the Gödel number of $E_n(n)$ as $d(n)$. Now for a set of natural numbers $A$, we define a set $A^{\ast}$ as follows:
$$\...
0
votes
0answers
31 views
Proving a correct system satisfying certain conditions is incomplete
I was reading R. Smullyan's book, Gödel's Incompleteness Theorems and got stuck at an exercise:
In the following problem $P$ denotes the set of Gödel numbers of provable statements in system $\mathcal{...
5
votes
1answer
128 views
How do “we” know the incompleteness of second-order logic?
The incompleteness of first-order arithmetic is relatively easy to wrap your head around -- there are non-standard models of PA in which Godel's sentence has a non-standard Godel number and so is &...
1
vote
0answers
36 views
How are the Hilbert-Bernays-Löb derivability conditions checked for the modus ponens condition?
To recall, the Hilbert-Bernays-Löb derivability conditions state that $\operatorname{Bew}$ is a derivability predicate if for any pair of sentences $S, T$:
If $S$ is provable, so is $\operatorname{...
3
votes
2answers
138 views
How to universalize $\text{Prov}(\ulcorner y < K(x)\urcorner) \to y < K(x)$ in a paper of Kikuchi
In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem he defines for $\Sigma_1$ binary predicates $R(x, y)$ the condition
$$ \Gamma_{1}(R) \Leftrightarrow \forall x\forall y(R(...
5
votes
0answers
194 views
The philosophical significance of Chaitin's Theorem
In a book review of Torkel Franzén's "Gödel’s Theorem:
An Incomplete Guide to Its Use and Abuse" in the Notices the reviewer (Raatikainen) writes:
Franzén also devotes a brief chapter to ...
5
votes
1answer
187 views
Gödel: If a statement of existence is neither provable nor refutable, doesn‘t that imply that the statement is false? [duplicate]
I‘m not very versed in Gödel‘s incompleteness theorem but in a naive way: If a statement of existence is not provable, there you cannot find an example which fulfills the statement (otherwise the ...
-1
votes
2answers
107 views
Does Gödel’s theorem preclude the existence of all means of proving all statements in a formal system, or preclude only computable means?
It is necessarily the case that you can eventually generate all possible finite proofs on a UTM. It also necessarily the case that you can eventually generate all possible theorems on a UTM. This ...
0
votes
0answers
37 views
Construct Gödel sentence with diagonalisation function?
In How is a Godel sentence constructed? and here, we construct a Gödel sentence $G$ by using the diagonalisation lemma to find a sentence $G$ such that
$$G \leftrightarrow \lnot\mathop{Prov}(\...
2
votes
0answers
67 views
Proof of Separation Lemma by Raymond Smullyan in Gödel's Incompleteness Theorems
In Gödel's Incompleteness Theorems book, Smullyan presents a proof of the Separation Lemma for sets.
Let be S a system, where all formulas of $\Omega_4$ and $\Omega_5$ (axiom schemes of (R)) are ...
1
vote
0answers
44 views
What subsystem of second-order arithmetic proves the weak Godel’s Theorem?
Godel’s Incompleteness Theorem states that any omega-consistent recursive theory in the language of first-order arithmetic is incomplete. But there is a weaker version of Godel’s Theorem that is ...
2
votes
1answer
77 views
The arithmetized completeness theorem
In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem he states the "arithmetized completeness theorem" as follows:
Let $T$ be a recursively axiomatizable theory in ...
5
votes
1answer
344 views
Can inconsistent systems be mathematically interesting/useful?
According to the top answer to this question:
Doing mathematics we often have an idea of an object that we wish to represent formally, this is a notion. We then write axioms to describe this notion ...
2
votes
1answer
139 views
Is there any metric on R with which it is incomplete.
I read the definition of complete metric space. A metric space (X,d) is complete if every cauchy sequence in X converges in X.
So, from this definition it looks like if a metric space is not complete ...
5
votes
4answers
393 views
Does the independence of the axiom of choice imply Gödel's incompleteness theorem?
I recently wrote this answer describing Gödel's completeness and incompleteness theorems, in which I came to the conclusion that a theory is (syntactically) complete if and only if all its models are ...
0
votes
0answers
59 views
The set of Godel numbers of axioms of Robinson arithmetic is recursive
Prove that the set of Godel numbers of axioms of Robinson arithmetic is recursive.
I'm studying Godel incompleteness theorems and I want to prove The set of Godel numbers of axioms of Robinson ...
1
vote
0answers
47 views
Recursive essentially for Godel incompleteness theorem
I'm reading Godel incompleteness theorem from A mathematical introduction to logic by Enderton.
GÖDEL INCOMPLETENESS THEOREM (1931)
If A ⊆ Th N and #A is recursive( the set of Godel number of ...
6
votes
0answers
81 views
What is it about natural numbers that makes them a prerequisite for Godel's Incompleteness Theorem to hold?
I came across an old question on here asking about Gödel's Incompleteness Theorem and the theory of Real Closed Fields, specifically about why the former doesn't apply to the latter. The top answer ...
1
vote
0answers
82 views
Proof of the theorem “Any recursive relation is representable in Cn A$_E$.”
I'm reading Godel incompleteness theorem from Mathematical introduction to logic by Enderton. There is something about recursive functions I don't get.
In the text it first says:
"DEFINITION. A ...
2
votes
1answer
46 views
Does it make sense to define the length of a line segment in terms of addition of infinite points?
Since a point has zero length, how can a line segment of, say, 1-unit length—which is a collection (addition) of infinite points, that is $0 + 0 + \cdots$—have 1-unit length? Does it make sense to say ...
1
vote
0answers
146 views
How important is first-order logic to Gödel's incompleteness theorem?
I'm trying to understand Gödel's incompleteness theorem, and I'm not sure if the theorem only applies to cases where the syntactic logic is first-order logic, or more generally.
On one hand, I've seen ...
