Questions tagged [incompleteness]

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

Filter by
Sorted by
Tagged with
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 } ...

1
2 3 4 5
13