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

learn more… | top users | synonyms

2
votes
1answer
66 views

Why is the proof of Gödel's first incompleteness theorem no contradiction?

I consider the following version of Gödel's first incompleteness theorem: Assume $F$ is a formalized system which contains Robinson arithmetic $ Q$. Then a sentence $G_F$ of the language of $F$ can ...
-4
votes
1answer
113 views

Are Godel's incompleteness theorems proven non-trivial?

Does somebody have a deep enough understanding of Godel's incompleteness theorem to confirm that the unprovable statements in some language $F$ are necessarily not just: The axioms themselves (...
1
vote
1answer
67 views

Arithmoquine function in Gödel's proof

Could someone explain as detailed as possible how the Arithmoquine{a,a'} function works or is the defined in Gödel's proof of the incompleteness theorem? To describe my question better... In this ...
0
votes
1answer
51 views

Does Gödel sentence depend on numbering?

If we change Gödel's numbering definition of the $Prov$ predicate will change as well, but the meaning won't. How is that going to affect $G$? It seems to me like it will change as it is actually $\...
1
vote
1answer
70 views

Showing a metric space is not complete.

Consider the metric space $$B = \{ f \in C[0,1] : \int_a^b \left| f(x) \right| dx \leq 1\},$$ where $d(f,g) = \int_0^1 \left| f(x) - g(x) \right|dx$. I'm trying to show that this metric space is not ...
7
votes
1answer
117 views

Is ZFC ω-consistent over ZF?

Gödel proved that if ZF is consistent, then ZFC is also consistent. He did this by showing that his constructible universe is a model of ZFC. Gödel also introduced the notion of an $\omega$-consistent ...
5
votes
2answers
153 views

How can you come to the truth of a statement without proving it?

I was reading a bit about Gödel's incompleteness theorems. I haven't took the time to really study it, but I'm very curious about statements like these: In other words, if our axioms are ...
1
vote
1answer
26 views

Minimal arithmetic proving a statement similar to a Gödel sentence

I will use $\textbf{Q}$ to denote minimal arithmetic for this post. (I suppose Robinson arithmetic would also suffice (?)) Suppose we have $F(x)$ be a formula defining, in $\textbf{Q}$ the primitive ...
2
votes
1answer
24 views

Busy Beaver unprovoable for large inputs?

From Wikipedia on the busy beaver, there is a true-but-unprovable sentence of the form "$Σ(10↑↑10) = n$", and there are infinitely many true-but-unprovable sentences of the form "$Σ(10↑↑10) < ...
0
votes
0answers
36 views

Rosser Sentences and Theories

Let T be any theory extending Q. Let R be the Rosser sentence of T. Let T0 be T + {R} and T1 be T + {∼ R}. Show that T0 and T1 are both consistent. Show that T0 ∪T1 is inconsistent. Show that for each ...
0
votes
1answer
40 views

If a theory is 1-consistent then it is consistent

I am attempting to back two claims in this problem: I use $\textbf{Q}$ to denote minimal arithmetic for this post. I use the term 'rudimentary sentence' to denote formulas built using only negation, ...
11
votes
4answers
462 views

Can unprovability unprovable? Is there an $\omega$-fold unprovability?

I was just thinking about unprovability. I just wanted to know if it is possible to make a concrete boundary between provable problems and unprovable problems in a certain axiomatic system. We know ...
-3
votes
1answer
101 views

Does Gödel’s theorem affect anything but the arithmetic of the natural numbers? [closed]

Влияют ли теоремы Гёделя на что-нибудь кроме арифметики натуральных чисел? Существуют ли интересные независимые от ZFC утверждения ,которые рождены теоремами Гёделя о неполноте, и которые не ...
0
votes
0answers
27 views

Why is it impossible to prove absolute consistency of a theory falling prey to Godel's theorems?

Why is it impossible to prove absolute consistency of a theory T falling prey to Godel's theorems? I understand that a theory falling prey to Godel's second incompleteness theorem cannot prove its own ...
3
votes
1answer
92 views

Why can't we keep adding axioms forever?

Let F be a formal system falling prey to Gödel's incompleteness theorems, implyng there is a true but unprovable statement, call it $G_1$. Of course, adding $G_1$ to the axioms of F doesn't solve the ...
0
votes
0answers
22 views

Can there be true but unprovable statements about object other than numbers?

In ZFC, everything is a pure set, and because the necessary amount of arithmetic for the Gödel's incompleteness theorems to go through is interpretable within ZFC, there are undecidable statements ...
0
votes
2answers
54 views

Impossibility of proving a foundation to be consistent

An argument came to my mind that seems really mind-blowing and I haven't found it anywhere. Here's how it goes: We call a formal system F embodied in classical logic a foundation of mathematics when ...
2
votes
1answer
203 views

Why does the existence of independent statements not prove consistency?

I've read before that, by the Principle of Explosion, if a theory is inconsistent, then absolutely any statement can be proven within it. Obviously, there are statements which are independent of ZFC (...
1
vote
0answers
28 views

Can we prove undefinability theorem first (using techniques that are different from Godel's) and then deduce Incompleteness from it?

I asked a related question about the matter here in philosophy platform where it was suggested to ask a modified version of the question on Math.se My question is, Is there any known way to prove ...
0
votes
1answer
35 views

Any foundational theory of math falls prey to the incompleteness theorems - true or false?

I heard somewhere on the internet once something along the following lines: Any conceivable foundational theory of mathematics (be it ZFC or, if ZFC was found to be inconsistent, some modification ...
3
votes
1answer
59 views

What is the simplest formal system falling prey to Gödel's incompleteness theorems?

What is the the simplest formal system falling prey to Gödel's incompleteness theorems? Is the answer different for the first and second theorems? Is the answer Q for the first theorem and PRA for ...
1
vote
0answers
23 views

Exercise Henkin Theory

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah. I have to do this excercise: Assume that Γ is a theory satisfying the following: Γ is a Henkin ...
0
votes
0answers
15 views

Same number of provable as unprovable statements?

Building on this question: Infinitely many nonequivalent unprovable statements in ZFC because of Gödel's incompleteness theorem? is the infinity of provable statements the same infinity of ...
4
votes
2answers
303 views

Sequent calculus and first incompletness theorem

Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
63
votes
7answers
5k views

Is linear algebra more “fully understood” than other maths disciplines?

In a recent question, it was discussed how LA is a foundation to other branches of mathematics, be they pure or applied. One answer argued that linear problems are fully understood, and hence a ...
2
votes
1answer
39 views

First Incompleteness Theorem: Does the limit of $\mathsf{T}_n\cup\{\rho_{\mathsf{T}_n}\}$ exist?

Suppose $\mathsf{T}$ is a consistent, computably axiomatizable theory extending $\mathsf{Q}$, Robinson arithmetic. Then by the First Incompleteness theorem there is a sentence $\rho_\mathsf{T}$ such ...
2
votes
1answer
190 views

Informal proof of Godel's second incompleteness theorem

This relates to two previous threads: Question about Godel's first incompleteness theorem and the theory within which it is proved Explanation of proof of Gödel's Second Incompleteness ...
2
votes
2answers
69 views

Help understanding Gödel's theorems?

What are the prerequisites to even begin to understand Gödel's theorems? I'm reading Hofstadter's book but would like a more fundamental approach to understanding these theorems. I have no knowledge ...
3
votes
1answer
81 views

Godel's proof for dummies [closed]

Can someone give me as simple-a-proof as possible for Godel's Incompleteness Theorem? I'd love to understand it more.
4
votes
3answers
554 views

The Penrose–Lucas argument

I was looking at the Penrose–Lucas argument as discussed on Wikipedia. It states: In 1931, the mathematician and logician Kurt Gödel proved that any effectively generated theory capable of ...
55
votes
12answers
7k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
3
votes
1answer
67 views

Is there a consistent arithmetically definable extension of PA that proves its own consistency?

Gödel's second incompleteness applies, for instance, to r.e. extensions of PA. I am wondering if it applies more generally to arithmetically definable extensions of PA. I see that there is a complete ...
1
vote
3answers
69 views

Gödel's Incompleteness Theorem and Numerical Analysis

I am no expert in Mathematical Logic so I can't really express my question formally but I do hope that it will make sense. As far as I know the implication of Gödel's incompleteness theorem for ...
1
vote
1answer
84 views

Is there a difference between induction in Peano Arithmetic and Presburger Arithmetic

Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics I was thinking ...
2
votes
1answer
38 views

Does the existence of uncomputable functions imply that a theory is incomplete?

For example Kolmogorov complexity is uncomputable and Chaitin used that fact to prove incompleteness. If this is not the case, can you give me a counter example? Set of axioms is countable.
3
votes
2answers
86 views

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my "proof" of "ZF is inconsistent" was that I was not considering that there are models with non-standard integers. However now I think I ...
2
votes
2answers
65 views

Trying to understand self-reference as it relates to Godel's Second Incompleteness Theorem

As noted in this post, I'm trying to understand how a sufficiently powerful consistent theory $T$ can prove statements about itself without contradicting Godel's Second Incompleteness Theorem. Let $...
0
votes
2answers
77 views

Is it possible to formalize $T \models \sigma$ within the deductive calculus?

I know that the notion of $T \vdash \sigma$ is formalizable within any sufficiently powerful theory $T$ but is $T \models \sigma$ formalizable as well? How is this possible if there are infinitely ...
1
vote
2answers
54 views

What does this deduction involving provability imply?

I recently asked this question asking why my reasoning for ZF being inconsistent was wrong. I didn't realize that we have to account for models with non-standard integers. However, I'm left with the ...
7
votes
1answer
91 views

What's wrong with this proof of ZF being inconsistent?

I'm studying (independently) mathematical logic and in investigating self-referential statements I developed a result which I don't know how to interpret. I'll use the notation from Enderton's "A ...
6
votes
5answers
884 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
5
votes
6answers
1k views

Can we prove that a statement cannot be proved?

Is it possible to prove that you can't prove some theorem? For example: Prove that you can't prove the Riemann hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in ...
0
votes
1answer
109 views

Analogy between a Gödelian puzzle and Gödel's first incompleteness theorem

I'm studying Gödel's incompleteness theorems. And I have the following slide that defines a version of Gödel's first incompleteness theorem. The point is that one can always follow the math and get ...
0
votes
2answers
74 views

How can Godel's theorem apply to every formal system?

How can Godel's theorem apply to any formal system of logic, if the truth of the theorem itself is only relative to the axioms and rule of inference that were used to generate it. In other words ...
1
vote
1answer
41 views

Expanding arithmetic to a complete theory by a transfinite sequence of expansions.

We all know that Godel first incompleteness theorem states that any recursive sufficiently strong theory to express arithmetic is incomplete. in particular, arithmetic is not complete. It's common ...
1
vote
2answers
87 views

How does Gödel's second incompleteness apply to any theory containing arithmetic?

If I understand correctly, there are two facts proven by Gödel's second incompleteness theorem, for a formal theory containing arithmetic 1) It is possible to express the consistency of the theory ...
11
votes
4answers
1k views

How does Gödel Completeness fail in second-order logic?

So a while ago I saw a proof of the Completeness Theorem, and the hard part of it (all logically valid formulae have a proof) went thusly: Take a theory $K$ as your base theory. Suppose $\varphi$ ...
0
votes
1answer
54 views

Gödel's Incompleteness theorem in modal logic

I think I once taught that the statement of the Gödel's Incompleteness theorem is equivalent to : $ \diamond \neg \square \square p $, if p is a complex enough system. Is this right?
2
votes
1answer
53 views

Is there a result for second-order theories analogous to Gödel's second incompleteness theorem?

One formulation of Gödel's second theorem says that, if $T$ is a consistent, axiomatisable extension of $PA$, and then $T$ cannot prove $\neg Prv(\ulcorner 0=1 \urcorner)$, where $Prv(-)$ is a ...
5
votes
2answers
768 views

What does Gödel's Incompleteness Theorem prove?

Does Gödel's incompleteness theorem only prove that you can't have a formal system which describes number theory which is both complete and consistent, or is it more general? In other words: does it ...