Logo notas.itmens

Diagonal Argument

Cantor's diagonal argument doesn't depend on the specific construction of set theory. It's a near universal argument about the self-contradictory nature of the absolute infinity.

It's not only the argument that gives rise to uncountable sets, that says it is impossible to have a universe of sets that is also a set. It also gives the undecidability of the halting problem, and Godel's second incompleteness theorem is also a theorem that is blatantly based on diagonal argument. 

The first incompleteness theorem makes use of the fixed point lemma, which is a weak instance of diagonal argument. Actually Chaitin's incompleteness is broadly speaking also an instance of diagonal argument. The hierarchy of complexity classes in computational complexity is also proved by diagonal argument - really no different from that of the halting problem. 

All those paradoxes such as Burali-Forti's, Mirimanoff's, Berry's, Richard's, Grelling's… are essentially diagonal argument in different guises.