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

learn more… | top users | synonyms

11
votes
2answers
121 views

Proportion of true statements that are provable

In an axiomatic system, there are true statements, some but not all of which are provable. Is there any sense in which we can quantify the proportion of those statements that are true? Here's an ...
0
votes
2answers
65 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 ...
10
votes
1answer
143 views

Decidability of equality of two set-theoretical terms constructed without replacement or specification

Define the set of NS-terms (NS is for "no schemes") to be the smallest set of terms satisfying the following rules : $\emptyset,\omega$ are NS-terms. if $x$ and $y$ are NS-terms, then so are $x\cup ...
3
votes
1answer
76 views

Independence of existence of inaccessible cardinals

Let $I$ be the formula which states that there exists strongly inaccessible cardinals. My question is regarding the proof of $ZFC\nvdash I$ appearing in Jech (part of theorem 12.12). He starts by ...
1
vote
1answer
52 views

understanding gödel's 1931 paper - number theoritical formulae

I am reading a translation of Gödel's original paper about in completeness theorem and there are a couple things i don't understand. Here is the document i am using primarily : ...
1
vote
1answer
50 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
73 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
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 ...
0
votes
1answer
88 views

understanding gödel's 1931 paper - elementary formulae

I am trying to understand Gödel's first incompleteness theorem from his original 1931 paper. Here is a translation i am using for my studies : ...
0
votes
1answer
57 views

understanding gödel's 1931 paper - proof of theorem / proposition V 5

I am trying to fully understand gödel's proof of the first incompleteness theorem from it's original 1931 paper. Here is the document I am using : ...
0
votes
1answer
49 views

Does the Law of the Excluded Middle imply syntactical completeness?

The Law of the Excluded Middle (LEM) states that for any proposition $p$, we have $\vdash p \lor \lnot p $. Syntactic completeness (a.k.a negation completeness) states that for any proposition $p$, ...
9
votes
0answers
155 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
222 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
51 views

Vaught's essentially undecidable set theory

Today I was reading this paper, which includes discussion of essential undecidability of various weak theories. On page 24, I was surprised to find out that Vaught has showed that set theory with the ...
5
votes
0answers
60 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 ...
5
votes
0answers
285 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
116 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 ...
3
votes
0answers
92 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
42 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
92 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
22 views

How to show that F is recursive?

In the road to Godel's incompleteness theorem, Problem saying: Show that Frame For $G:\omega\times\omega\times\omega^{n}\rightarrow\omega$ a recursive function, the function ...
1
vote
0answers
54 views

Enumerating the reals using a definability hierarchy

(edit : for those perplexed with the meaning of "truth" in the following, let us say we believe in the consistency of ZFC, use the completeness theorem and reason in a fixed model $M$ of ZFC. The ...
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
0answers
73 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
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 ...
1
vote
0answers
66 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
25 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
0answers
37 views

Standard model of the Meta theory in the proof of arithmetic incompleteness

I have a question about the incompleteness of arithmetic. I wonder in which meta theory we are reasoning. For example, if we are in ZFC, then there are some non standard models of ZFC. As far as I ...
0
votes
0answers
22 views

Quantitative results on PA completeness?

Are there any results estimating the number of sentences in PA that are not provable together with their negations, as a function of the sentence length or the depth of the sentence parse tree or ...
0
votes
0answers
22 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
63 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: ...