Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

105 Views Asked by At

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also follow Hao Wang's notation, where $d(f,x)=F∗x$ is read as "$F$ applies to $x$", as Wang says that he replaced Goedels dot between the arguments $(F,x)$ with $d(F,x)$. I hope that by using Wang's notation it is not too complicated in appearance, as Goedel approved of using his change in notation.

Theorem 1.0. (Goedel) A function $F$ is considered "regular" if $F$ applies to every argument (possibly a function). Let $F$ apply to every argument $x$, then $F$ derives $0=1$.

1) $d(F,x)=F(x)$ if $F$ is regular, and $0$ if otherwise.

2) Introduce $F$ as $E$ as follows:

$E(x)=0$ if $x≠1$ & $E(x)=1$ if $x≠0$.

3) Therefore, by (1), we have that $E(x)≠x$.

4) Let $H(x)$ be $E(d(x,x)$, which is by assumption regular by (1).

5) Hence we have that $d(H,x)=H(x)=E(d(x,x)$.

5) Substituting $H$ for $x$, we get: $d(H,H)=E(d(H,H))$, contradicting (3).

This ends Goedels proof of Theorem 1.0.

Question: Given the above derivation of Goedel's paradox for Theorem 1.1., Godel further asks if it can be reduced to the notion of provability in intuitionistic mathematics (as implicit in (2) above is the law of excluded middle. That is, by "provability", I mean that $A \rightarrow B \iff$ for every proof of $A$ you can derive (intuitionistically) a proof of $B$. Does the following paradox, which is derived using only function application from Goedel's paradox above, allow one to derive $0=1$ for the intuitionistic case if one substitutes provability for Goedel's function application?

A) $d(E,x)=E(x)$ if $E$ is regular & $E(x) =0$ if otherwise.

B) $E(x)=0$ if $x≠0$ [i.e., $E$ is not regular if $E$ is regular], and $E(x)=1$ if $x=0$. [i.e., $E$ is regular if not regular].

C) Therefore $E(x)≠x$. [Since if a regular function $E$ does not apply to itself then $E$ is not a regular function, a contradiction].

D) Let $H(x)=E(d(x,x))$, which is regular by (1) [equivalently, by (A)] we have: $d(H,x)=H(x)=E(d(x,x))$.

Da) More precisely, $H(x)=H(x)$, supposing (A) holds.

E) By substituting $H$ for $x$ in $H(x)$, we attain for all arguments of $H$: $d(H,H)=E(d(H,H))$, contradicting (C), since by substituting $H$ for $x$ throughout we have $H(H)=H(H)$.

Ea) That is, due to (C), $H(H)≠H$ if $H$ is a regular function [applies to every entity], and by (D), $H$ is regular. QED

Thank you for your help. I have thought it is interesting that Goedel saw that this paradox could be generalized to an intuitionistic proof of $0=1$ via the notion of provability being substituted for function application when taken as above, however I have not heard of recent news if this has been accomplished or if it is even true in general.