# Tagged Questions

61 views

### set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
92 views

### In Godel's first incompleteness theorem the Godel sentence G is true otherwise it contradicts itself, however its truth implies it is not provable .

How can this be? I understand there are two basic definitions of truth in mathematics, one being the formalist definition which includes excluded middle and the second form being the intuitionist in ...
499 views

### Godel Incompleteness Theorem

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 ?
75 views

### How can I imagine a model of $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$?

Gödel's second incompleteness theorem states that if $\mathsf{ZF-Inf}$ is consistent, then $\mathsf{ZF-Inf} \nvdash \mathsf{Con(ZF-Inf)}$. Moreover, if $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$ ...
66 views

### Godel's completeness theorem and formula that states consistency of ZF

Godel's completeness theorem, in original formulation, says that every logically valid statement/formula has finite deduction of a formula. Now then there is Godel's incompleteness theorem. Would this ...
85 views

### Expressibility of Gödel's Incompleteness Theorem

Can Gödel's Incompleteness Theorem be expressed as a formal sentence in ZFC and be proven formally or is it inherently meta-mathematical? (Note: I am referring to the theorem itself, not the ...
42 views

### Can two distinct formulae (or series of formulae) have the same Gödel number?

As I am studying Gödel's incompleteness theorem I am wondering if two distinct formulae or series of formulae can have the same Gödel number? Or the function mapping each formula or series of formulae ...
59 views

### Gödel's proof method and fundamental theorem of arithmetic

I am a novice to Gödel's proof (the theorem that consistency contradicts completeness), and, as it seems to me, he uses the fundamental theorem of arithmetic to uniquely number any formula. My ...
218 views

### Could it be that Goldbach conjecture is undecidable?

The result closest to Goldbach conjecture is Chen's theorem [Sci. Sinica 16 157–176], the proposition 1+2''. It is natural to ask if it is likely that under our arithmetic axioms the Goldbach ...
72 views

### If a statement holds for all standard models of PA, then does it hold for all models?

Suppose that $\varphi$ is a consequence of every standard model of PA. Then is it provable from PA?
157 views

### Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
56 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 ...
94 views

### Criticism on truth of Gödel sentence in standard interpretation

Mendelson in his book mentioned the Gödel sentence and argued that in standard interpretation it is true. But Peter Milne in his article (On Godel Sentences and What They Say) criticized: "But we know ...
65 views

### Truth of Godel's sentence in standard interpretation

It is siad that the Godel's sentence: g is true in the standard interpretation. But I have problem in truth of g in the standard interpretation. We proved that if theory K is consistent g is not ...
108 views

### Gödel incompleteness theorem [closed]

Gödel incompleteness theorem states that any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.So what are some Gödel sentences about ...
37 views

### Undecidable sentence in Godel's incompleteness theorem? [duplicate]

At first I want to apologize to you for repeating my question, since I didnt get satisfying answer. And because answering to this question is very important to me, I have to repost this question. ...
36 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 ...
124 views

### Undecidable sentence in Godel's incompleteness theorem

In Godel's incompleteness theorem, the undecidable sentence is g: I am not provable. Ok. I accepted it and realized that in satandard interpretation it is true. So we found a true sentence which ...
92 views

### Scapegoat theory and PA

A theory T is scapegoat if for every formula A with only one free variable there exist a closed term s such that T proves: (∃x(¬A(x)))⇒¬A(s) I think it is an expectable property for each theory since ...
85 views

### Understanding ω-consistent and ω-incomplete theory

A theory $K$ is said to be $ω$-consistent if, for every formula $B(x)$ of $K$, if $﹁ B(n)$ is a theorem in $K$ for every natural number $n$, then it is not the case that $(∃x)B(x)$ is a theorem in ...
189 views

### Concrete example for diagonal lemma

Diagonal lemma says that in a theory with enough assumption for any formula $A(x)$ there exist a sentence $B$ such that $B$ $\iff$ $A(\#(B))$ is a theorem in that theory, in which $\#(B)$ represents ...
163 views

### Is Douglas Hofstadter's version of Godel's proof utter nonsense?

Is Douglas Hofstadter's version of Godel's proof, which he offers in his book Godel, Escher, Bach, utter nonsense? Hofstadter goes to great length to disguise the fact that there are two distinct ...
91 views

### If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. ...
119 views

### Gödel's incompleteness theorems: where to learn? Is there a straightforward relation between the two?

What would be a good textbook or paper to learn the proofs of the two Gödel's incompleteness theorems from? I would prefer it to be as close to the original proofs as possible. I have not tried to ...
128 views

### Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
81 views

### Must every decidable theory be axiomatizable?

Note: By "theory" I mean a set of sentences, not assumed to be closed under logical consequence (otherwise the question would be trivial). Comments/ideas: There's a well-known result that every ...
81 views

### Peano's theory of arithmetic and Gödel's 1st Incompleteness Theorem

Let $\mathcal{N}$ be Peano's 1st order theory of arithmetic and $\mathscr{A}$ it's standard model (which we assume exists). Infer from Gödel's 1st Incompleteness Theorem that there exists a closed ...
60 views

120 views

### What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...
82 views

### How can a statement be known to be undecidable in ZFC without ZFC being inconsistent?

I'm attempting to understand the answer to the question, Is there a statement whose undecidability is undecidable (as in independent, not a decision problem)? The answer appears to be "Yes". However, ...
118 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 ...
135 views

### Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
74 views

### Is this possibility ruled out by Godel's Incompleteness Theorem?

From Wikipedia: "The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any ...
182 views

### What was the planned topic of Gödel's second paper on incompleteness?

Gödel's incompleteness theorems first appeared together in a paper titled (translated to English) "On formally undecidable propositions of Principia Mathematica and related systems I," with the Roman ...
116 views

### Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
137 views

### Questions on a sentence in ZFC asserting that ZFC has a model

Question 1. Let $\operatorname{con}(\mathsf{ZFC})$ be a sentence in $\mathsf{ZFC}$ asserting that $\mathsf{ZFC}$ has a model. Let $S$ be the theory $\mathsf{ZFC}+\operatorname{con}(\mathsf{ZFC})$. ...
79 views

### Expressibility; Incompleteness of Peano Arithmetic

I'm working through Peter Smith's book, 'An Introduction to Godel's Theorems'. One small issue I've encountered is how the notion of expressibility is used to prove the incompleteness of Peano ...
139 views

### Formalizing proof of Godel sentence's non-provability?

In the question What does it mean for something to be true but not provable in peano arithmetic? Henning Makholm states, "...he [Godel] gave a (formalizable, with a few additional technical ...
167 views

### Explain/illustrate Goedel's theorems and possible implications to non-mathematicians

I am asked to give a talk about (a) mathematical practice, (b) axiomatization, (c) Gödel's theorems and (d) possible antimechanist arguments based on the incompleteness theorems (as mentioned in P ...
103 views

### Impossibility of theories proving consistency of each other?

By Godel's second incompleteness theorem, a consistent theory (to which the theorem applies) cannot prove itself consistent. I learned that it's also impossible to have a pair of consistent theories ...
81 views

### Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately ...
147 views

### Is every theorem of PA true in the standard model of number theory $N$?

My understanding is that every theorem $\phi$ of $PA$ is true in $N$ because $N$ is a model for $PA$, $N\models PA$. By completeness of first order logic, "$PA\vdash\phi$" implies that "if \$N\models ...