Articles of incompleteness

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” […]

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific number $y$ such that Peano arithmetic proves $y = f(x)$. (This follows from the fact that $f$ is […]

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 unprovable in PA” $\neg G_{PA} $ $\implies$ $\neg$ “$G_{PA}$ is unprovable in PA” $\implies$ “$G_{PA}$ is provable in PA” $\implies$ $G_{PA}$ I […]

Proving that the existence of strongly inaccessible cardinals is independent from ZFC?

ZFC can’t prove that strongly inaccessible cardinals exist, or else it would prove that a model of itself exists and hence $Con(ZFC)$. So this leaves us with two options: ZFC proves there are no strongly inaccessible cardinals The existence of strongly inaccessible cardinals is independent from ZFC I’ve heard, however, that you can’t actually prove […]

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$ such that T proves $\psi(0)$ T proves $\psi(n)\Rightarrow \psi(n+1)$ for every “integer” (in the above sense ) $n$, T […]

Gödel Completeness theorem

I realized recently that I did not understand well the completeness theorem of Godel, and how it interacts with the incompleteness theorems. What I understand now (and you will see my understanding is not consistent !) Incompleteness means that, as long as I have some kind of arithmetic power (let’s say multiplication) in my axioms, […]

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 properly the question before marking as duplicates, I’m asking for a proof of a statement being proved unprovable, not examples of unprovable/indecidable […]

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 each proving the consistency of the other. But I can’t see how this follows from the second theorem. Or is there something more involved?