Questions tagged [incompleteness]
Questions about Gödel's incompleteness theorems and related topics.
638
questions
0
votes
1answer
71 views
While using the method of proof by contradiction, are we “assuming” consistency?
I am aware of threads here and here which asks something similar. However, I had something very specific to ask under the same context.
I have a very elementary question about the connection between ...
0
votes
1answer
38 views
To what extent does Goedel's 2nd incompleteness theorem extend?
In chapter 8 of Shoenfield's matheamtical logic[1967], He proves that The formula of P which states that P is consistent is not a theorem of P, where P stands for Peano Arithmetic. And then He says, ...
0
votes
1answer
43 views
Why doesn't the incompleteness theorem answer the decision problem?
The answer (or impossibility of an answer) to Hilbert's Entscheidungsproblem or decision problem is generally attributed to Alan Turing and also independently to Church. My question is why Gödel's ...
1
vote
1answer
29 views
Is PA complete when multiplication is bounded?
Working in PA.
Fix some natural number "$n"$.
Is PA complete for sentences that do not use the symbol $``\times"$ unless all of their variables are bounded $< n$.
0
votes
1answer
41 views
Relative completeness of first order arithmetic
Gödel's incompleteness theorem tells us that the language of first order arithmetic $PA_1$ is strong enough to express a statement about its own consistency, which cannot be proved in $PA_1$.
More ...
4
votes
1answer
56 views
For any statement independent of $\mathsf{ZFC}$, can we prove it is independent of $\mathsf{ZFC}$? [duplicate]
Gödel's famous incompleteness theorem implies, in particular, that there are statements unprovable in $\mathsf{ZFC}$. This implies that we could never hope to settle the truth of every mathematical ...
1
vote
0answers
59 views
Circular logic in the concept of Godel numbers
I am interested in understanding how Godel was able to prove his two celebrated theorems. I usually start with the most elementary book (something that perhaps a high school kid can understand) in ...
-1
votes
1answer
43 views
Godel's Incompleteness Theorems & the Laws of Thought [closed]
If Godel showed that a sufficiently powerful formal system can be consistent or complete but not both, is this equivalent to saying that the law of non-contradiction or the law of excluded middle ...
1
vote
1answer
55 views
Is Halting problem an example of a problem which is true but unprovable?
I have a difficulty understanding Gödel's incompleteness theorems. If it is proven semantically that some problem is undecidable (such as Halting problem), does it means that such a statement is "true ...
1
vote
1answer
42 views
If PA is consistent, for any $n$, does PA prove “$n$ does not code a proof of an inconsistency”?
I am still struggling with the distinction between what is proven where. I think I have a good understanding of the theory and the meta-theory, but then I'm stumped every once in a while, so I fear ...
1
vote
1answer
26 views
How does Rosser's Theorem actually show that a system is inconsistent if it's complete?
So I was reading this article: https://www.scottaaronson.com/blog/?p=710 and I had an issue with the way he described Rosser's Theorem.
He starts by describing Gödel's Incompleteness Theorems, and ...
0
votes
0answers
24 views
Was Frege's 2nd-order logic a complete system?
Frege's system was found to be inconsistent due to Russell's paradox, due to his Basic Law V, but was Frege's logic complete in any sense?
Godel showed that no consistent formal system can be ...
1
vote
1answer
68 views
Proving Unprovability: Is Compactness Used in the Metathory?
I am reading Halbeisen's "Combinatorial Set Theory", and it certainly provides a great exposition of forcing (bar its notation conventions for forcing...). The very short chapter 16 is dedicated to ...
0
votes
1answer
36 views
Proving Parallel Postulate by showing that it is undecidable
In the Numberphile video "Gödel's Incompleteness Theorem" (via YouTube), Professor Marcus Du Sautoy mentions that the Riemann hypothesis could be proved true by proving that it was undecidable, ...
0
votes
1answer
69 views
Proving a statement is true by proving it is undecidable.
https://www.youtube.com/watch?v=O4ndIDcDSGc
I was watching this numberphile video in which Professor Du Sautoy mentions that if the Riemann hypothesis is undecidable, it must be true.
Let's say we ...
0
votes
1answer
41 views
How to prove the diagonal Lemma
I am interested in understanding the proof of Gödel’s Incompleteness theorems. The diagonal Lemma is used to prove the existence of self-referential statements. But as I read the proof of the Diagonal ...
0
votes
1answer
30 views
Is $\omega$ -consistency, soundess, or completeness expressible in the language of arithmetic? [closed]
Obviously through the second incompleteness theorem consistency is expressible in La, I was wondering if $\omega$ -consistency and completeness were the same and how so. I know soundness is not but I ...
0
votes
0answers
66 views
About First Order Logic an Godel incompleness theory.
There's something I'm failing to grasp: Are Gödel's theorems of incompleteness a first order logic result or a second order logic result? What confuses me is the fact that in Gödel's original work, he ...
2
votes
1answer
115 views
Confused about $\mathsf{ZFC} \nvdash \mathrm{Con}(\mathsf{ZFC}) \to \mathrm{Con}(\mathsf{ZFC} + \mathsf{I})$
I am studying with Jech's book. He claims that
The existence of inaccessible cardinals is not provable
in $\mathsf{ZFC}$. Moreover, it cannot be shown that the existence of inaccessible cardinals ...
0
votes
0answers
28 views
Is it possible to prove Gödel’s 1st Incompleteness theorem without the use of self referential statements [duplicate]
Is it possible to prove Gödel’s 1st Incompleteness theorem without the use of self referential statements?
I have searched for various proofs of the first incompleteness theorem and all of them use ...
3
votes
1answer
62 views
Truth Predicate in Models of ZFC
I have been trying to reconcile this for a while now, but I'm failing miserably.
I know of Tarski's Undefinability of Truth, that states that there is no formula in the standard model $\overline{\...
1
vote
1answer
67 views
Understanding the role of Metatheories through an example
I've been studying for a course in set theory and I still have some problems in understading clearly the relation metatheory\theory. Being more specific, I'll present an example:
If we choose $\...
-1
votes
2answers
59 views
In the 1st incompleteness theorem proof, how do we assume that everything in arithmetic language can be mapped to naturals?
Consider the following set of arithmetic functions,
$a_0,a_1,a_2.....a_m(n)=a_0+a_1n+a_2n^2+...a_mn^m$
$a_0,a_1,a_2.....a_n$ can be any subset of naturals. So clearly, the number of these arithmetic ...
0
votes
4answers
105 views
Does Godel's Incompleteness theorem only prove that some self referential sentences are unprovable?
It shows that the sentences of the form $\forall x, \neg Dem(x,sub(n,y,n))$ are true but unprovable, where $y$ is the Godel number mapped to the symbol $Y$ in arithmetic language, and $n$ is the Godel ...
1
vote
1answer
46 views
Confusion with the predicate $Dem(x,z)$ in Godel's incompleteness theorem proof
I'm reading http://www.math.mcgill.ca/rags/JAC/124/GodelsProof.pdf
Near the final pages, they prove it.
Here's the proof as I understand it:
All symbols in the language of arithmetic are given a ...
3
votes
1answer
55 views
Proof of consistency of propositional logic
Here's how they proved it in the source I was reading:
Assume both sentences $S$ and $\lnot S$ are derivable from the axioms (where $\lnot S$ is the negation of $S$).
We notice that $p\rightarrow (\...
3
votes
0answers
71 views
Riemann hypothesis cannot be proved to be unprovable?
I'm coming off the numberphile video: https://youtu.be/O4ndIDcDSGc
In the very end, they say that 'Proving that Riemann hypothesis is unprovable would be a proof of the truth of Riemann hypothesis'
...
1
vote
2answers
270 views
Making sense of Goedel's First Incompleteness Theorem
In Stanford Encyclopedia of Philosophy they say that (for a formal system F) by the Diagonalization Lemma a sentence G can be constructed: $F \vdash G_F$ $\leftrightarrow$ $\lnot Prov(⌈G_F⌉)$. This ...
0
votes
1answer
42 views
The set of tuths depends on our assumptions of the world, so how can 'truth' be more fundamental than assumptions?
For example, we define 'what a set is' or 'what natural numbers are' using a bunch of assumptions about how they should behave. Those assumptions are all there is to the 'world or sets' or 'world of ...
2
votes
0answers
36 views
What are some good expositions of the Hilbert-Bernays-Löb derivability conditions for PA?
The Hilbert-Bernays-Löb derivability conditions state that for $P$ to be a provability predicate it must obey the following for all sentences $A, B$:
If $A$ is provable, so is $P(\ulcorner A\urcorner)...
1
vote
1answer
121 views
Constructive proof of Gödel's incompleteness theorem
Gödel's first incompleteness theorem states that if a consistent theory $T$ extends Peano arithmetic, then there is an explicit formula $\Delta_T$ in the language of arithmetic, that is true in $\...
1
vote
2answers
41 views
Existential arithmetical formula independent of ZFC
In Gödel's incompleteness theorem, the Gödel formula is in the language of arithmetic, so adding it as an axiom changes the properties of $\mathbb{N}$. To me that's already difficult to grasp, because ...
0
votes
1answer
101 views
What kind of relation is Godel talking about in Proposition V of his Incompleteness theorem?
Proposition V in Gödel's 1931 Incompleteness theorem is stated as follows:
For every recursive relation $ R(x_{1},...,x_{n})$ there is an n-ary "predicate" $r$ (with "free variables" $u_1,...,u_n$) ...
8
votes
1answer
298 views
Is an ultrafinitist way around Gödel incompleteness theorems?
I know that a similar question has been asked regarding finitism, but I'm interested in ultafinitism. That is, we define a set of numbers that has a specific upper limit. For argument's sake - let's ...
1
vote
1answer
50 views
Sentence S (similar to a Godel sentence) where S iff the negation of S is provable?
The diagonal lemma can be used to generate the Godel sentence, where G is true iff G is not provable in theory T. Can we use the lemma to construct a sentence (call it S) where S is true iff the ...
-5
votes
1answer
163 views
Has Gödel’s second incompleteness theorem been formalized?
I have great trouble accepting Gödel's second incompleteness theorem. I think it's claiming too much. One way to convince me of its validity is to show me a computer-verified version of the proof. Has ...
1
vote
1answer
34 views
How does one prove that Peano Arithmetic can represent all partially computable functions?
I'm interested in establishing that for any partially computable $k$-ary function $f$ there exists a formula $\Phi$ with $k+1$ free variables such that
If $f(x_1, \dots, x_k) = y$, then $\Phi(x_1, \...
1
vote
1answer
65 views
A question about the proof of Godel's Incompleteness Theorem
The article A Computability Proof of Gödel’s First Incompleteness Theorem, by Jørgen Veisdal on Cantor's Paradise contains the following passage:
The second property regards the complement of a set ...
2
votes
1answer
81 views
A finitist Gödel second incompleteness theorem
Can we prove by finitist means (such as with $\text{Con}(\text{ZFC}) \to \text{Con}(\text{ZFC + CH})$; see Kunen's Set Theory, p.8) that $\text{ZFC} \vdash \text{Con}(\text{ZFC}) \Rightarrow \text{ZFC}...
0
votes
1answer
94 views
Gödel's Incompleteness Theorem and the Millennial Problems
Disclaimer: I am not an expert in logic nor in mathematics in general, so please feel free to correct me in any of my assumptions or statements below.
Gödel's Incompleteness Theorem states that "any ...
0
votes
2answers
98 views
If a system is complete, must it be inconsistent?
Godel's incompleteness theorem basically says that a set of axioms cannot prove everything. But you can add those unprovable truths to your set of axioms to expand it. Suppose you keep expanding your ...
1
vote
1answer
55 views
Consistency hierarchies and Gödel’s theorem
We know that for any theory $T$ that can interpret arithmetic, the recursive theory $T_{bad} = T + \mathop{Con}(T_{bad})$ is inconsistent, by Godel’s second incompleteness theorem. However, $T_{okay} ...
6
votes
1answer
91 views
Why can't we prove the consistency of ZFC by proving its axioms is satisfiable?
We can prove the consistency of Peano Arithmetics by given a model of natural numbers, within this model, PA's axioms are satisfiable，thus PA is consistent. Why can't we do the same thing to ZFC
1
vote
1answer
108 views
False Σ1-sound theories
I was wondering how Σ1-sound theories in the language of first-order arithmetic can go wrong. As far as I can tell, they cannot prove false claims about consistency, since such claims (e.g., that ...
1
vote
1answer
38 views
Quantifying the “Complexity” or “Strength” of Axiomatic Systems
The halting Problem states that there is no Turing Maschine that is able to decide whether an arbitrary other Turing Machine will halt.
In 2016 Adam Yedidia and Scott Aaronson presented a turing ...
0
votes
0answers
57 views
Completeness of Logic versus completeness of a theory
It's my understanding that First-Order-Logic is complete, but that not all logical theories are complete (for example, Russel's Arithmetic) - both these results having been shown by Godel.
I'm trying ...
5
votes
1answer
86 views
Does $\omega$-consistency of ZF imply $\omega$-consistency of ZFC
Does $\omega$-consistency of ZF imply $\omega$-consistency of ZFC?
Are there any related results where $\omega$-consistency of some intuitionistic logic implies $\omega$-consistency of ZFC?
Does ...
2
votes
1answer
75 views
Proof of Gödel's Incompleteness Theorem by modal logic
I watched Undefined Behavior's videos (on YouTube) regarding Gödel's Incompleteness Theorem, and the last video slightly confuses me.
Let $\square P$ denote "There is a proof of the statement $P$." ...
0
votes
1answer
104 views
Rosser's trick practice exam question
A practice exam in recursion theory has the following question about Rosser's trick (I guess this is the correct name):
I use the following notion of representability:
The only theorem I need ...
4
votes
1answer
69 views
What is a valid function definition?
Consider the famous Collatz sequence
$$
x_{n+1} = c(x_n) = \left\{ \matrix{x_n/2 & {\rm if \; x_n \; even} \hfil \cr
3x_n+1 & {\rm if \; x_n \; odd} \hfil \cr }
...
