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

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

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

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

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

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

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

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

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?

Intereting Posts

Use of determinants
The largest number system
In what sense is a tesseract (shown) 4-dimensional?
Discontinuous derivative.
Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$
Approximating a $\sigma$-algebra by a generating algebra
Does there exist a computable function that grows faster than fast growing hierarchy?
Show that this entire function is polynomial.
e as sum of an infinite series
St. Petersburg Paradox
If $f$ is measurable and $fg$ is in $L^1$ for all $g \in L^q$, must $f \in L^p$?
Connecting square vertexes with minimal road
Does “partial integration” exist analogous to partial differentiation (in general)?
What is the value of $\sum_{p\le x} 1/p^2$?
If $\sum a_n$ converges then $\sum (-1)^n \frac {a_n}{1+a_n^2}$ converges?