Beweis
Da abzählbar ist, ist auch abzählbar. Es sei
, ,
eine Abzählung sämtlicher Ausdrücke aus . Wir definieren induktiv eine aufsteigende Folge von Ausdrucksmengen durch
und
-
Wir setzen
-
Diese Menge ist widerspruchsfrei, da andernfalls schon eines der widersprüchlich wäre, was aufgrund der induktiven Definition nicht der Fall ist. Um zu zeigen, dass maximal widerspruchsfrei ist, sei
.
Da in der Abzählung der Ausdrücke vorkommt, ist
für ein gewisses . Im -ten Konstruktionsschritt wurde nicht hinzugenommen, sonst wäre
.
Also ist widersprüchlich und damit ist auch widersprüchlich.