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

learn more… | top users | synonyms

3
votes
2answers
92 views

understanding gödel's 1931 paper - primitive recursive functions - projection and equality

I am reading a translation of gödel's original, and i'm a bit confused about the primitive recursive functions. Everywhere on the internet (or some resources like courses/classes i could put my hands ...
2
votes
2answers
104 views

understanding gödel's 1931 paper - gödel numbers

I am a little confused about gödel numbers and what numbers exactly we are manipulating. are the numbers "real" natural numbers (than we obviously represent as) 1, 2, ... or are we always dealing ...
0
votes
1answer
39 views

Godel's Incompleteness Theorem and Algorithms [closed]

According to Godel's incompleteness theorem, not every problem can be solved using algorithms. How do we know if a problem can be solved using algorithm? How do we know that NP problems are ...
0
votes
1answer
56 views

understanding gödel's 1931 paper - primitive recursive functions “FR(x)” and “n Gl x”

I am trying very hard to fully understand gödel's paper on the incompleteness theorem. I have a slight technical question about one of the 45 primitive recursive functions introduced to build the ...
1
vote
1answer
57 views

What's wrong with this proof that ZFC is consistent

If we take ZFC minus all it's axioms, we can easily prove that ZFC's first axiom is independent (because all statements are independent in a formal system without any axioms). We can then prove that ...
1
vote
1answer
30 views

Will assuming an undecidable statement result in a consistent system?

If you assume that an undecidable statement in a consistent axiomatic system is true (or false), will that new system also be consistent? For example, does $\mathsf{ZF}$ being consistent imply that ...
4
votes
1answer
175 views

What does a Godel sentence actually look like?

My understanding is that Godel's first theorem says that there is a sentence that is in a sense true in a formal system F but cannot be derived in that system. I then hear that Godel actually goes on ...
4
votes
2answers
120 views

$L$ models set theory and so does $V_\kappa$ for $\kappa$ inaccessible

Background: I have been reading the 1980 edition of Kunen. Theorem VI.2.1 states it is provable from ZF that $\mathbf L$ (Kunen writes classes in bold) is a model of ZF. Also, it is a well-known ...
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$ ...
1
vote
1answer
56 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$, ...
2
votes
1answer
71 views

$\mathrm{NBG}$ proves its own consistency

In $\mathrm{NBG}$, one can construct a model of $\mathrm{ZFC}$: $V$, the class containing every set. Thus: $\mathrm{NBG}$ can prove "$\mathrm{ZFC}$ is consistent". Furthermore, the following ...
3
votes
1answer
41 views

Consistency hierarchy between models with many urelements

The axiom of extensionality can be weakened, asking only for non-empty sets with the same elements to be equal. Then there can be many "different empty sets" called urelements. I call this theory ZFU ...
3
votes
2answers
161 views

Could someone show me a simple example of something being proved unprovable?

Could someone show me a simple example of something being proved unprovable? Pretty much what the title says, I want to understand a proof of some statement being proved unprovable. E: Please read ...
0
votes
1answer
52 views

Is there some result that says a theory cannot prove the consistency of any of its extensions?

Is there some result that says a (sufficiently strong) theory cannot prove the consistency of any of its extensions? Or something along these lines?? More generally, is there a result that says a ...
0
votes
1answer
29 views

What does it mean to encode some statement in Theory of Natural Numbers $Th(\mathbb{N})$?

For example Godel's Incompleteness Theorem says "Some statement in $Th(\mathbb{N})$ has no proof". Consider sentence "This sentence is not provable". We can encode this sentence in $Th(\mathbb{N})$. ...
-7
votes
1answer
130 views

Gödel's theorem, un-decidable propositions and axioms of a formal theory [closed]

There was a similar question of mine some time ago (which is now closed, but should not be). Anyway the question is similar, but simplified to avoid (mostly) "pedantic" objections, which bypass the ...
0
votes
1answer
28 views

Is there any relationship between Gödel numbers associated with proofs of undecidable theorems and infinitesimals?

I recall from my reading of the popular book, Gödel, Escher, Bach some years ago that Hofstadter speculated on the value of Gödel numbers of undecidable theorems. If I recall correctly, he suggested ...
1
vote
3answers
73 views

Godel's incompletness theorem - proving a statement is false

I have two question regarding Godel's incompletness theorem. The theorem says that every axiomatic system is either incomplete or inconsistent. If it's consistent, then there are true statements that ...
5
votes
1answer
67 views

Does the foundations of Arithmetic need to be effective?

I was reading about Godel's incompleteness theorem which is true for any formal theory that satisfies certain properties. One of these properties is the following: "The theory is assumed to be ...
3
votes
1answer
80 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 ...
0
votes
0answers
23 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
3answers
121 views

Godel's Second Incompleteness and the Assumption of Consistency

As I understand it, Godel's Second Incompleteness Theorem states that given a theory $T$ that is any extension of Robinson Arithmetic, that if that theory is consistent then it cannot prove a given ...
11
votes
1answer
148 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 ...
2
votes
2answers
169 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). ...
6
votes
1answer
90 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
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 ...
5
votes
1answer
183 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
77 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
3answers
222 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
155 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
158 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
110 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
65 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
273 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
154 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
57 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
93 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
61 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
64 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 ...
2
votes
1answer
123 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
95 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
83 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
51 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
166 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
119 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
63 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
92 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
95 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
95 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$ ...
3
votes
1answer
59 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 ...