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

learn more… | top users | synonyms

10
votes
1answer
132 views
+100

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 ...
2
votes
2answers
79 views

Why does Gödel's (First) Incompleteness Theorem apply to ZFC?

Okay, so I'm reading Smullyan's book on Gödel's incompleteness theorems, and I've just about finished the part where he shows that Peano arithmetic is incomplete using Tarski's truth set (chapter IV). ...
5
votes
1answer
59 views

Absolutely undecidable statements in Peano arithmetic

Let "Undec(x)" be a predicate in Peano Arithmetic that says "x is the Gödel number of a sentence that is neither provable nor refutable" It is easy to see that this predicate is in fact expressible in ...
1
vote
0answers
50 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 ...
5
votes
1answer
168 views

Since arithmetic has a model (thus it is consistent) why care if consistency can't be proved?

Since arithmetic has a model, the numbers as we know them, it is consistent. Why do we care if consistency can't be proved within arithmetic? Do I miss something, ie in what we can consider a model?
2
votes
1answer
62 views

Does semantic inconsistency guarantee syntactic inconsistency?

I'm wondering about the possibility of circumventing the problem of incompleteness posed by Roger Penrose in his book "Shadows of the Mind". It occurred to me (and, Googling has revealed to me, ...
4
votes
2answers
195 views

Gödels incompleteness vs incompleteness

This has been nagging me, and might be an unfit question, but still: I've been taught that completeness of a theory $T$ means that for any sentence $\varphi$ in the language of the theory, we have ...
3
votes
1answer
68 views

How to show incompleteness of second order logic?

I'm trying to see/show that second order logic (with full semantics) is incomplete - i.e. that there are sentences that are true in all models of some theory $T$, and yet still can not be proved from ...
4
votes
1answer
112 views

What is wrong with this “proof” that there is no $\omega$th inaccessible cardinal?

"Theorem": There is no $\omega$th inaccessible cardinal. "Proof": Assume ZFC. Let $\kappa_n$ be the $n$-th inaccessible cardinal; since $V_\kappa$ is a model of ZFC for inaccessible $\kappa$, ...
3
votes
1answer
85 views

Consistent, complete axiom system that proves its own consistency

Is there a consistent, complete axiom system that proves its own consistency? I know that this question isn't exact and I haven't defined when an axiom system proves its own consistency because ...
2
votes
1answer
44 views

Peano and consistency, how to understand it rightly.

I'm struggling with the notion of consistency, and a few cases : I'm writing in the following $Con(T)$ to denote the arithmetic formula which expresses the consistency of $T$, for $T$ a consistent ...
9
votes
2answers
204 views

Why is $\omega$-consistency needed in Gödel's original Incompleteness proof?

I don't see why the original version of Gödel's first incompleteness theorem (before Rosser's improvement, I mean) had to include the assumption of $\omega$-consistency in order to show that $F ...
4
votes
1answer
130 views

Why a system becomes incomplete once it's capable of doing arithmetic?

For a Formal axiomatic system to obey Godel's incompleteness theorems, It has to be powerful enough to incorporate Peano Axioms. Why It does not apply to say, Presburger arithmetic or the axioms of ...
1
vote
2answers
47 views

show the set of valid second-order $\emptyset$-sentences is not R-enumerable

show the set of valid second-order $\emptyset$-sentences is not R-enumerable this would have the empty symbol set i.e. $S = \emptyset$ so it would be sentences that are universally or existentially ...
3
votes
1answer
73 views

Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee ...
1
vote
1answer
51 views

How does PA prove all $\Delta_0$-formulas which are true in the standard model?

Let $\varphi(x_1,\dots,x_n)$ be a $\Delta_0$-formula, i.e. a formula in which every quantifier is bounded. I want to prove that $$ \text{PA}\vdash\varphi(\overline{n_1},\dots,\overline{n_k}) \iff ...
5
votes
0answers
55 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 ...
1
vote
1answer
86 views

Non-standard model of arithmetic and Gödel's theorem [closed]

This is a cross-post of a question asked on History of Science and Mathematics Stack Exchange. I've read Skolem's paper on his non-standard models of the arithmetic ("Über die ...
3
votes
2answers
75 views

Lindebaum's Lemma seemingly inconsistent with Gödel's incompleteness theorem?

Lindenbaum's Lemma: Any consistent first order theory $K$ has a consistent complete extension. First Incompleteness Theorem: Any effectively generated theory capable of expressing elementary ...
1
vote
1answer
75 views

What does “Fixed-Point Lemma” says intuitively?

The lemma as stated in Enderton's logic says: Fixed-Point Lemma.   Given any formula $\beta$ in which only $v_1$ occurs free, we can find a sentence $\sigma$ such that $$ A_E \vdash ...
0
votes
1answer
21 views

Question about Godel's first incompleteness theorem and the theory within which it is proved

Please explain the error in my reasoning with this: Let T be a formal theory within which Godel's first incompleteness theorem can be proved. In other words... suppose when we write the proof of ...
3
votes
2answers
147 views

Do we know if the consistency of $ \mathsf{ZFC} $ is sufficient to prove that $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) \to \mathsf{SM} $?

This is basically a sequel to this earlier post. There, I asked: If $ \mathsf{ZFC} $ is consistent, then is $ \mathsf{ZFC} \nvdash \neg \text{Con}(\mathsf{ZFC}) $, i.e., $ \neg ...
1
vote
1answer
99 views

Reference request for the independence of $ \text{Con}(\mathsf{ZFC}) $.

Gödel’s Second Incompleteness Theorem says that if $ \mathsf{ZFC} $ is consistent, then $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) $, i.e., $ \text{Con}(\mathsf{ZFC}) $ is not provable in $ ...
1
vote
2answers
54 views

Confusion in Godel's numbering for subscripts

I don't understand how to represent subscripts in Godel's numbering. Suppose I have a formula: $$x_1 + sx_{11} = s(x_1 + x_{11})$$ and an encoding: then what should be the Godel Numbering? Should ...
2
votes
0answers
65 views

How does Godel Escher Bach support Artificial Intelligence? [closed]

Typically, Godel's Incompleteness theorems have been used to argue against the possibility that the human mind is essentially equivalent to a formal system. However, in Daniel Dennett's book "Darwin's ...
1
vote
2answers
50 views

Limit of Cauchy Sequence

Let $(X,d)$ be a metric space and $(x_n)$ be a Cauchy sequence in $X$. Is there a limit $x$ for $(x_n)$ whether $x$ in X or not ? In general, does every Cauchy sequence has a limit, if that limit ...
4
votes
1answer
89 views

Integer induction without infinity

In ZFC minus infinity (let us call this T), one can still define ordinals, and then define integers as ordinals all of whose members are zero or successor ordinals. I am looking for a formula $\psi$ ...
0
votes
0answers
18 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 ...
3
votes
1answer
42 views

Incompleteness of formal systems as opposed to completeness of a non-formal theory

I have read that Gödel's incompleteness theorem does not apply to real closed field theory. But the incompleteness theorem applies only to formal systems, that is systems whose alphabet of symbols and ...
1
vote
2answers
82 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
126 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 ...
3
votes
3answers
112 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
146 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
24 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
45 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
0answers
50 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
77 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
72 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 ...
20
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
22 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
191 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
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 ...
1
vote
1answer
96 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$ ...
8
votes
1answer
248 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
104 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
107 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
42 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 ...
1
vote
0answers
73 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
78 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
60 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 ...