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

learn more… | top users | synonyms

1
vote
2answers
79 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 ...
0
votes
2answers
68 views

particular property and completeness?

I was puzzeling with the almost standard definition of completeness: In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula ...
1
vote
1answer
41 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: ...
0
votes
1answer
65 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
42 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 ...
9
votes
0answers
137 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
7
votes
0answers
177 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 ...
5
votes
0answers
50 views

Deductive closure of sentence $\forall x \forall y F(x,y) \stackrel{.}{=} F(y,x)$ in language $\mathcal{L}$ is undecidable.

$\mathcal{L}$ is the language that contains a single binary function symbol $F$. In the earlier parts of this question, we were told to take the $\mathcal{L}$-structure $\mathcal{M}$ with universe ...
4
votes
0answers
147 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 ...
4
votes
0answers
94 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 ...
4
votes
0answers
90 views

An “internal” condition on $T$ so that for the standard provability predicate, $T$ proves $\text{Pf}(\underline S)$ implies $T$ proves $S$?

This is probably quite basic, but I'd like to make sure I got this right. Regarding the proof of Goedel's first incompleteness theorem, say that we have $T$ containing $PA$ effectively axiomatizable ...
2
votes
0answers
40 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 ...
2
votes
0answers
68 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
2
votes
0answers
86 views

Minimal number of variables in a ZFC-undecidable sentence?

Let $\phi$ be a sentence of set theory. In Prenex form, $\phi$ can be written $$ {\bf Q}_1 x_1 {\bf Q}_2 x_2 \ldots {\bf Q}_n x_n \ \ \psi(x_1,x_2, \ldots ,x_n) $$ where each ${\mathbf Q}_i$ is ...
1
vote
0answers
23 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
0answers
45 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
0answers
64 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
0answers
57 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 ...
1
vote
0answers
29 views

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

Consider pairs $(\Phi,n)$ where $\Phi$ is a finite set of statements in Peano arithmetic and $n$ is an integer. Say that $p'=(\Phi',n')$ is an elementary intuitionistic extension of $p=(\Phi,n)$ iff ...
1
vote
0answers
104 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 ...
1
vote
0answers
54 views

What follows from Incompleteness about provability of partial correctness?

A colleague and I can't figure out what our professor is getting at with this question: What follows from the incompleteness theorems about the provability of partial correctness assertions? What ...
0
votes
0answers
16 views

Formalisms of Mathematics in Gödel's Incompleteness Theorem

Unfortunately I have been more or less introduced to Gödel's Incompleteness Theorem(s?) via computer science and Turing machines, and we haven't addressed them very rigorously. My professor often says ...
0
votes
0answers
30 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: ...