Prerequisits

Cf. Ontological Argument(s) & Topological Theology

Set Theory: Classes vs Sets #

[In my humble opinion ] a Set is something that can exists, at least potentially; exists possibly, in a possible world [cf. Modal Logic above]; assumption of it’s existence doesn’t lead to a logical contradiction.

A Class - is something that exists in name only, something that necessarily doesn’t exist, something that involves a logical contradiction and thus doesn’t occur in any possible world [excepting fictional/artistic/illogical ones].

Obviously, we can come up with a name  and ascribe some qualities to the name - this doesn’t mean that there is anything behind that name. Think “ghosts” for example. Or, temperatures below 0K. These examples are physical rather than logical, but they may convey the feeling.

The situation may not be that simple, though…

I think it has a lot to do with Popper’s three worlds - also discussed by Sir Roger Penrose in “The Road to Reality”. And, it’s important to rememeber the words of Oscar Wilde, who opined in an 1889 essay that, “Life imitates Art far more than Art imitates Life”. Or, in other words: the world of Art influences the real world more than the real world influences the world of Art.

Diagonalization #

Or, rather Diagonalization in broader context

The argument was first used by Georg Cantor to prove

Cantor’s theorem: Let @@X@@ be a set. Then the power set @@2^X := \{ A: A \subset X \}@@ of @@X@@ cannot be enumerated by @@X@@, i.e. one cannot write @@2^X := \{ A_x: x \in X \}@@ for some collection @@(A_x)_{x \in X}@@ of subsets of @@X@@.

Proof:

Suppose for contradiction that there existed a set @@X@@ whose power set @@2^X@@ could be enumerated as @@\{ A_x: x \in X \}@@ for some @@(A_x)_{x \in X}@@. Using the axiom schema of specification, one can then construct the set

$$ \displaystyle Y := \{ x \in X: x \not \in A_x \}. $$

The set @@Y@@ is an element of the power set @@2^X@@. As @@2^X@@ is enumerated by @@\{ A_x: x \in X \}@@, we have @@Y = A_y@@ for some @@y \in X@@. But then by the definition of @@Y@@, one sees that @@y \in A_y@@ if and only if @@y \not \in A_y@@, a contradiction.

A lot of paradoxes and their solutions depend on diagonalization. Perhaps, it is more about self-reference than diagonalization, though. Noson S. Yanofsky noticed that you don’t need diagonalization as such to prove that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers - some permutation/bijection would suffice…

The most generic approach to diagonalization is, arguably, Lawvere’s Fixed-point Theorem

In 1969 Francis William Lawvere suggested a categorical scheme that encompasses virtually all kinds of diagonal arguments and also covers some fixed point results.

Some important corollaries of this are:

  • Cantor’s theorem
  • Cantor’s diagonal argument
  • Diagonal lemma
  • Russell’s paradox
  • Gödel’s first incompleteness theorem
  • Tarski’s undefinability theorem
  • Turing’s proof
  • Löb’s paradox
  • Roger’s fixed-point theorem
  • Rice’s theorem