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

learn more… | top users | synonyms

-9
votes
2answers
178 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory [closed]

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
3
votes
1answer
40 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 ...
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$, ...
2
votes
1answer
66 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
2answers
153 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 ...
8
votes
2answers
282 views

How is the standard model of number theory specified, and why can't we use that specification to prove any number theoretical sentence of interest?

According to Gödel's incompleteness theorem, there exists a sentence $G$ in the vocabulary of number theory ($N$) which is not provable from any (recursively enumerable) consistent set of axioms $T$, ...
0
votes
1answer
51 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
119 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 ...
4
votes
3answers
217 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 ...
0
votes
1answer
27 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
67 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 ...
9
votes
2answers
504 views

Are the Gödel's incompleteness theorems valid for both classical and intuitionistic logic?

I am studying an undergraduate text about math logic. The proofs of the two Gödel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I ...
4
votes
3answers
212 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 ...
5
votes
1answer
64 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
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 ...
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
3answers
114 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 ...
19
votes
6answers
3k views

Does Gödel's Incompleteness Theorem really say anything about the limitations of theoretical physics?

Stephen Hawking believes that Gödel's Incompleteness Theorem makes the search for a 'Theory of Everything' impossible. He reasons that because there exist mathematical results that cannot be proven, ...
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 ...
2
votes
2answers
134 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
85 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 ...
2
votes
1answer
71 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, ...
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?
4
votes
1answer
137 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
97 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
63 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
234 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
147 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
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 ...
1
vote
2answers
55 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
90 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 ...
9
votes
2answers
714 views

Is there an algorithm that when given a set of axioms, will generate a statement independent of those axioms?

Is there any mechanism or algorithm where one can generate mathematical statements/problems that are undecidable, i.e their proof is independent, from a certain set of axioms?
1
vote
1answer
60 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 ...
1
vote
1answer
114 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 ...
0
votes
2answers
76 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 ...
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 ...
3
votes
2answers
90 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
93 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
vote
1answer
81 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
30 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
164 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
112 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
58 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
82 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 ...
4
votes
3answers
936 views

Classifying Types of Paradoxes: Liar's Paradox, Et Alia

The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false ...
1
vote
2answers
88 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 ...
68
votes
14answers
25k views
4
votes
1answer
91 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$ ...