# Tagged Questions

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

74 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 ...
135 views

131 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 ...
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 ...
73 views

99 views

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 $... 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 ... 0answers 66 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 ... 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 ... 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$... 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 ... 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 ... 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 ... 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 ... 3answers 113 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 ... 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 ... 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 ... 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: ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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$... 1answer 249 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 ... 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 ... 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 ... 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 ...