Articles of incompleteness

Gödel's Incompleteness Theorem — meta-reasoning “loophole”?

Gödel’s Theorem says that I can construct a mathematical statement like “f(x1,x2,…,x_n)=0 has no integer solution”, where it is impossible (in a certain system of axioms) to formally prove that it’s true, and also impossible to formally prove that it’s false. I have often heard a school of thought that goes like “Well, in reality, […]

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 theorem)?

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my “proof” of “ZF is inconsistent” was that I was not considering that there are models with non-standard integers. However now I think I developed an actual deduction of $T \vdash \text{Cons} T$ for any sufficiently powerful theory $T$ thus implying by Godel’s […]

Is Robinson Arithmetic complete and not-complete?

Is Robinson Arithmetic complete in the sense of Gödels completeness theorem? And is Robinson Arithmetic incomplete in the sense of Gödels first incompleteness theorem? If RA is both it would be a good example to explain the different notions of “completeness” used in the two theorems mentioned.

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C when it will actually never halt?

understanding gödel's 1931 paper – elementary formulae

I am trying to understand Gödel’s first incompleteness theorem from his original 1931 paper. Here is a translation i am using for my studies : http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf I feel like i now have a decent intuitive understanding of it all. Now I’m trying to understand all the technical details of it. I don’t fully understand these […]

Infinitely many nonequivalent unprovable statements in ZFC because of Gödel's incompleteness theorem?

Am I right in thinking that there are countably infinitely many nonequivalent unprovable statements in ZFC due to the Gödel’s first incompleteness theorem? If not, why?

Gödel's Incompleteness Theorem – Diagonal Lemma

In proving Gödel’s incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $\phi$ that spoke about itself? Can’t this formula be built this way: Diagonal Function. Let $D(x, y)$ be the diagonal function, such that $D$ returns the result obtained by replacing the formula with Gödel […]

clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

I am not quite sure what really is meant when talking about “arithmetics” in context of Gödel’s incompleteness theorems. How I so far understand it: Gödel proved that every sufficiently powerful first-order theory is not both consistent and complete at the same time. This is, you pick a first-order language (so the logical symbols are […]

Are (some) axioms “unprovable truths” of Godel's Incompleteness Theorem?

Like any math newbie, Godel’s Incompleteness Theorems are easy to understand in general layman’s terms, but difficult to understand beyond the typical “liar’s paradox” and “barber’s paradox” type examples. But then I started thinking, are axioms examples of the truths of mathematics that can’t be proven? For example, Peano’s Postulates: a very popular “starting point” […]