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

learn more… | top users | synonyms

1
vote
2answers
91 views

Does “provable” include “proved by reduction to absrdity”?

The incompleteness says that formal logic system (under certain condition) contains non provable TRUE sentence. It seems that "prove" means here "derive". Only TRUE sentence could be proved. If a ...
2
votes
2answers
159 views

Are Gödel's incompleteness theorems really about primitive recursive functions?

Any formulation of Gödel's incompleteness theorems seems to involve arithmetic. Why is arithmetic so fundamental? After thinking about the issue a little bit, I came to the conclusion that the ...
4
votes
3answers
150 views

Why can PA + $\neg G_{PA}$ be consistent?

Wikipedia and other sources claim that $PA +\neg G_{PA}$ can be consistent, where $\neg G_{PA}$ is the Gödel statement for PA. So what is the error in my reasoning? $G_{PA}$ = "$G_{PA}$ is ...
4
votes
1answer
173 views

Is there a relationship between Turing's Halting theorem and Gödel Incompleteness

Turing's proof that a Halting oracle is impossible and Gödel's proof that and omega-consistent first order theory of arithmetic must be incomplete are similar in that they use self-referential ...
1
vote
0answers
26 views

Closed term conditions in PA

The situation I have to transfer statements from the "recursive world" into the "$\color{red}{\text{syntactical world}}$", in the context of binumerability of primitive recursive predicates into the ...
1
vote
1answer
53 views

Understanding Rosser's Theorem

Initial Situation For some time now I'm trying to understand a proof for Rosser's Theorem -- the proof given in Smorynski's article "The Incompleteness Theorems" (here is a first entry from google: ...
1
vote
1answer
79 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 ...
1
vote
1answer
91 views

Explanation of $\mathrm{ZFC} + \lnot \mathrm{Con(ZFC)}$

I read in JDH's answer to this mathoverflow question that $\mathrm{ZFC}$ is equiconsistent with $\mathrm{ZFC} + \lnot \mathrm{Con(ZFC)}$. But this second statement is a bit weird. What does ...
2
votes
1answer
81 views

diagonalization about incompleteness

In the Enderton's logic book(page 186-187), he writes 'diagonalization approach' for proving undefinability of $\#Th\mathfrak{N}=\{\#\tau |\vDash_{\mathfrak{N}}\tau \}$ where $\#\tau$ is the godel ...
22
votes
3answers
2k views

Why is Gödel's Second Incompleteness Theorem important?

Given that the consistency of a system can be proven outside of the given formal system, Gödel says, It must be noted that proposition XI... represents no contradiction to the formalities ...
0
votes
1answer
27 views

Proving divergence of a sequence in a normed linear space

My aim is to prove that the space $(C_\mathbb{R}[0,1],||•||)$, where $||•||=\int_{0}^{1} t(1-t)|f(t)|dt$, is not complete. I have already proved that the sequence $(f_n)$ defined by ...
5
votes
0answers
323 views

Gödel's Incompleteness Theorem in “Gödel, Escher, Bach”

Ok, so I'm reading the chapter on Gödel's Incompleteness Theorem in "Gödel, Escher, Bach" and I want to make sure I'm getting this right: the idea of the book's proof is to form the sentence "There ...
2
votes
0answers
43 views

Is the probabilitistic distribution of the digits in the Chaitin's constant computable?

The Chaitin constant can in principle be computed with exponential effort on each sucessive digit by brute forcing all programs of a given length and simply proving special theorems on each case that ...
1
vote
1answer
101 views

What is the mathematical meaning of this statement made by Gödel (see details)? [closed]

It appears as Proposition VI, in Gödel's 1931 paper "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I" : "To every $\omega$-consistent recursive class $\kappa$ ...
11
votes
1answer
360 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
4
votes
0answers
120 views

Incompleteness theorem

Correct me if I am wrong at any point! Godel's incompleteness theorem allows us to express "PA is consistent" in the language of Peano arithmetic, and shows that this is not provable in PA. Let's ...
5
votes
1answer
125 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
58 views

Why is the set of all true first-order statements about non-negative integers in the language with only equality, $+$ and $\times$ undecidable?

Apparently Tarski and Mostowski proved this, but intuitively I'm not seeing the difference between statements in a language of non-negative integers with equality, addition, and multiplication vs ...
4
votes
3answers
241 views

Does Gödel's incompleteness theorem contradict itself?

I have problems understanding Gödel's incompleteness theorem. I presume I have a misunderstanding of some phrase or I have to look closer at the meaning of some detail. Gödel's second incompleteness ...
1
vote
1answer
85 views

Trouble Reading “On Formally Undecidable Propositions”

I've been working my way through Godel's original paper of the incompleteness theorem in my spare time, and I'm stuck with something stupidly simple. I'm looking at the list of 45 definitions of ...
0
votes
1answer
86 views

Lindenbaum's Lemma

I am working on the proof of the Lindenbaum's lemma and there are some passages which are not very clear for me. Here is the statement: Let $\mathbb{L}$ a countable signature, $T$ a consistent set of ...
1
vote
1answer
113 views

Why are all computable functions representable in PA?

I'm trying to understand the proof of the first incompleteness theorem, and more specifically, the diagonal lemma. Suppose $GN(x)$ is the Gödel Number of a formula $x$. The first step of the diagonal ...
-1
votes
1answer
57 views

The existence of concatenation functions in Godel Numbering?

I know that there are many schema of Gödel Numbering, and each has its own method of Concatenation, n★m. But is there a general proof that shows 'For every Gödel Numbering scheme there exists a ...
11
votes
2answers
379 views

How to prove that Gödel's Incompleteness Theorems apply to ZFC?

Let us denote Robinson Arithmetic as Q and Primitive Recursive Arithmetic as PRA. Let $T$ be a formal theory formulated in the language of arithmetic. According to this page on the Stanford ...
3
votes
1answer
90 views

What does not having a first-order frame imply for models?

There are formulas in modal logic which which do not have a first-order frame condition, as stated here (Non-Sahlqvist formulas, Wikipedia). An example is the McKinsey formula for $p$: ...
2
votes
1answer
147 views

$\omega$-consistent in Gödel I

In a very accessible form one could state the first incompleteness as follows: Incompleteness Theorem I Assume that $\textbf{PA}$ is consistent. Then there is a sentence $\phi$ such that ...
9
votes
2answers
630 views

Is there a mistake in the SEP article about Godel's Incompleteness theorems?

Update: The mistake referred to in this question has now been corrected. The below refers to a previous version of the article: The second supplement to the Stanford Encyclopaedia of Philosophy ...
1
vote
0answers
74 views

Importance of Gödel Numbering System

How important is Gödel numbering to his incompleteness proofs, set theory, logic theory in general and proofs employing ZFC? Can we use some other numbering or 'meta' programming? How about if one ...
2
votes
3answers
385 views

Can we prove that axioms do not contradict?

We construct many structures by chosing a set of axioms and deriving everything else from them. As far as I remember we never proved in our lectures that those axioms do not contradict. So: Is it ...
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 ...
5
votes
1answer
155 views

Problem in Kunen - suitable representation of ZF proves the consistency of ZF?

I tried to prove the exercise problem in Kunen (Chapter IV, problem 36.) Problem. Show that there is a formula $\chi(x)$, such that $\chi$ represents ZF; i.e.,$$\phi\in \mathsf{ZF}\to ...
4
votes
2answers
178 views

Is it possible to prove that some point belongs to Mandelbrot set? Is this an example of Gödel's theorem?

Everybody knows about Mandelbrot set drawing computer programs. Program takes some point, builds sequence from it, and if found that sequence goes out of circle with 2 radius, then knows that this ...
0
votes
1answer
104 views

What does First Godel's Incompleteness theorem mean?

I am terribly confused what really "Incomplete" mean in terms of the Godel's theorem. Does it mean there are some theorems that are definable in First order theory of natural numbers and true but ...
1
vote
1answer
99 views

Uncountable reals in the theory

The Question I'm looking for a possibility to somehow proof the "essence" of Cantor's diagonal argument within a recursive first-order theory which is satisfied by the reals (better: within a theory ...
1
vote
1answer
87 views

Algorithm to force decidability of statements using an intuitionistic series of new axioms

Say that a set $\Phi$ is a finite set of statements in Peano arithmetic is meekly consistent if it contains no "inner,immediate" contradiction, i.e. for any statements $\alpha,\beta$, it does not ...
7
votes
0answers
234 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
4
votes
2answers
361 views

Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?

I want to ask if it is possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem. I am reading the following AMS-Notice article. The authors claim that: The ...
1
vote
1answer
100 views

Show that the metric $d_1$ on $C([0,1])$ does not give rise to a complete metric space. [duplicate]

Show that the metric $d_1$ on $C([0,1])$ does not give rise to a complete metric space. $$ d_1(f,g) = \int_0^1 |f(s)−g(s)| \, ds $$
0
votes
0answers
73 views

Questions about godel's first incompleteness theorem

I'd rather not get into the formal proof of godel's first incompleteness theorem. But I have 2 general questions. Looking at the statement from wikipedia: ...
1
vote
1answer
74 views

How can Goodstein's theorem be expressed in PA

I understand Goodstein's Theorem and its proof. I'm trying to understand the proof of why Goodstein's Theorem cannot be proved in PA. However, it's not immediately clear to me that Goodstein's Theorem ...
2
votes
1answer
350 views

True but unprovable?

I would like to ask a question about Gödel's Incompleteness Theorems which I've had in the back of my head for some time. Since I'm a student working in a completely different area of maths (my usual ...
4
votes
1answer
69 views

About Gödel's Incompleteness Theorem

A short time ago, I've been thinking about what statements in Number Theory are true but not provable. I've seen the proof of the Incompleteness Theorem (in the Gödel's works) and he gave an example ...
1
vote
1answer
67 views

Question about the incompleteness proof (Theorem V)

Question in short: Where do I find a complete proof of Theorem V from Gödels incompleteness proof? If it does not exists, can someone provide it? Question in detail: I am trying to understand ...
10
votes
3answers
315 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
301 views

Problems with nesting proof predicates in first order logic.

Whenever I start nesting proof predicates, I always seems to run into these bizarre situations. I was wondering if anyone knows about this and could shed some light on it or provide me with some ...
4
votes
1answer
229 views

Proof of “If $ZFC$ proves there is an inaccessible cardinal, then $ZFC$ is inconsistent”.

Let $I$ be the statement "there is an inaccessible cardinal". I'm aware of two proofs of "If $ZFC\vdash I$ then $ZFC$ is inconsistent". One proof uses the Second Incompleteness Theorem, which I ...
1
vote
1answer
87 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
1
vote
1answer
83 views

Boolean Algebra and Godel

Can anyone give an example of a theorem in Boolean Algebra that isn't immediately obvious to someone with a computer that can construct a truth table? Clearly no propisition that can be proved using ...
1
vote
3answers
194 views

In Godel's first incompleteness theorem the Godel sentence G is true otherwise it contradicts itself, however its truth implies it is not provable .

How can this be? I understand there are two basic definitions of truth in mathematics, one being the formalist definition which includes excluded middle and the second form being the intuitionist in ...
1
vote
0answers
112 views

Do we know that if $\pi$ is normal then there is a proof of it?

We do not know whether $\pi$ is normal or it is not and many other weaker statements, e.g. (*) $\pi$ contains infinitely many $0$s. Inspired by the Godel's incompleteness theorem that there are some ...