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

learn more… | top users | synonyms

2
votes
1answer
81 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 ...
1
vote
2answers
36 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 ...
2
votes
1answer
54 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 ...
8
votes
0answers
177 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 ...
5
votes
1answer
64 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?
7
votes
1answer
150 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 ...
0
votes
1answer
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 ...
0
votes
0answers
30 views

Tensor Product of Hilbert Spaces: incomplete?

Let $\mathcal{H}$ be an infinite dimensional Hilbert space and $\mathcal{H}\otimes_0\mathcal{H}$ its algebraic twofold tensor product. Define a scalar product on it as ...
0
votes
1answer
78 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 ...
0
votes
1answer
56 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 ...
2
votes
2answers
106 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 ...
0
votes
0answers
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. ...
1
vote
0answers
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 ...
0
votes
2answers
121 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 ...
0
votes
2answers
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 ...
0
votes
5answers
77 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 ...
4
votes
3answers
176 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 ...
8
votes
1answer
132 views

How did Kurt Gödel's Incompleteness Theorem affect the mathematical world?

Hi I am looking not to understand the Incompleteness Theorem, but to find out more about how and what this has effected the mathematics world. I am in high school, in Honors Algebra II, and I am ...
-4
votes
2answers
75 views

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

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

Why doesn't “$V$ is a model of $ZF$” imply consistency of ZF?

One can prove that $V$, Von Neumann's universe, satisfies all of $ZF$ axioms, so it's a model of $ZF$. But I can't see why this doesn't imply the consistency of that theorem. I'm aware that ...
1
vote
1answer
159 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 ...
2
votes
0answers
40 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
3
votes
2answers
86 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$. ...
3
votes
2answers
114 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 ...
5
votes
2answers
127 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 ...
1
vote
1answer
78 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 ...
0
votes
1answer
80 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 ...
2
votes
1answer
51 views

Does second-order arithmetic (Z2) prove soundness and uniform reflection for first-order arithmetic (PA)?

(1) Does full second-order arithmetic (Z2) prove soundness and uniform reflection schemas for first-order arithmetic (PA)? That is, do we have for all formulas $\phi$: $$ \underset \phi \forall \; ...
2
votes
1answer
56 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
-6
votes
2answers
91 views

Does Gödel's theorem of incompleteness contradicts it self? [closed]

I stumbled today with Gödel's theorem of incompleteness, and couldn't avoid to think about the possibility, that it could also be incomplete. It comes to mind that if one assume that maths are ...
5
votes
2answers
198 views

Interaction of completeness and second incompleteness theorems

So I was reading the Wikipedia article on Godel's completeness theorem, the section on its relation to completeness. It says that completeness gives the existence of a model of arithmetic $\mathcal M ...
3
votes
1answer
55 views

The effects of requiring a recursive vs. a recursively enumberable axiomatization in the incompleteness theorem

I believe that the (paraphrased) original statement of Gödels first incompleteness theorem (including Rosser's trick) is If T is a sufficiently strong recursive axiomatization of the natural ...
1
vote
1answer
37 views

Logic soundness and completeness

I have to do a number of similar type questions, but I am having trouble grasping the general concepts around soundness and completeness. I have read up on the general definitions and think I ...
5
votes
4answers
241 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
0
votes
1answer
35 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
3
votes
1answer
113 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 ...
6
votes
2answers
360 views

Gödel's (in)completeness theorems and the axiomatization of Euclidean geometry

In David Hilbert's 1899 Grundlagen der Geometrie, Hilbert gives a rigorous axiomatization of Euclidean geometry. As I understand it, some of Hilbert's axioms must be expressed in second order logic ...
0
votes
1answer
81 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, ...
7
votes
0answers
117 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 ...
2
votes
1answer
134 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" ...
1
vote
2answers
72 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 ...
9
votes
1answer
131 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 ...
3
votes
1answer
112 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 ...
1
vote
1answer
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})$. ...
2
votes
1answer
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 ...
6
votes
2answers
138 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 ...
5
votes
1answer
165 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 ...
1
vote
1answer
41 views

Can we determine which statements are incomplete due to Godel?

Due to Godel's incompleteness theorems we know that there are true statements in a system that cannot be proven with that system. My questions are 1) can we tell which statements in a system are the ...
5
votes
1answer
102 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 ...
2
votes
2answers
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 ...