Naïve Set Theory and Paradoxes

A naive approach to set theory creates a lot of foundational problems, famous examples being paradoxes of Russell, Cantor and Burali-Forti. Discovery of these paradoxes implied that Cantor's original formulation of set theory was inconsistent. This article will introduce the aforementioned paradoxes.

Russell's paradox is closely related to the notion of a universal set. It can be stated as follows: Let $R$ be the set of all sets that are not members of themselves. Is $R$ member of itself? It doesn't matter if we assume $R \in R$ or $R \not \in R$, we reach contradiction either way. In logical notation:

   Let $R = \{r| r \not \in r \}$. Then $R \in R \iff R \not \in R$ 

To understand Cantor's paradox we need to understand the notion of a cardinal. We say that two sets are equinumerous if there exists a bijection between them. It is easily shown that equinumerousity is an equivalence relation. So we can pick out a representative from each equivalence class and we shall call them cardinals. Let $|X|$ denote the cardinal associated with $X$. Let $\chi$ denote the set of all cardinals. We will show that there exist a cardinal not belonging to $\chi$ which is a contradiction.

For that purpose, we give a partial order on $\chi$ as follows: $\mathcal{A} \leq \mathcal{B}$ iff here exist an injection from $\mathcal{A}$ to $\mathcal{B}$. In particular, $\mathcal{A} < \mathcal{B}$ means that there is an injection $f:\mathcal{A} \to \mathcal{B}$ but there is no bijection between them. It is fairly easy to check that $\leq$ is a reflexive and transitive. Antisymmetry follows from Schröder–Bernstein theorem. There is a trivial injection between a set $X$ and its powerset $\mathcal{P}(X)$ namely $x \mapsto \{ x\}$. However Cantor proved that there is no bijection between a set and its power set. So $|X| < |\mathcal{P}(X)|$. (Note if $A \subseteq B$ then $|A| \leq |B|$.)

Let $\mathcal{C}$ be the cardinal associated with union of all cardinals ie. $\mathcal{C} = |\bigcup \chi|$. Noting that every cardinal is a subset of $\bigcup \chi$ and that inclusion maps are injective, we have $\mathcal{A} \leq \mathcal{C}$, for all $\mathcal{A} \in \chi$. However $\mathcal{C} < |\mathcal{P}(\mathcal{C})|$ and so $|\mathcal{P}(\mathcal{C})| \not \in \chi$ which is absurd.

Burali-Forti paradox deals with ordinals. We are interested in partially ordered set $(W, \leq)$ where every nonempty subset of $W$ has a least element. These are called well ordered sets (or wosets). Given two partial orders $(W_1, \leq_1)$ and $(W_2, \leq_2)$, a function $f:W_1 \to W_2$ is called an order-isomorphism if $f$ is a bijection and preserves order in both direction ie. $a \leq_1 b$ iff $f(a) \leq_2 f(b)$ and in case such a function exists, we say $(W_1, \leq_1)$ is isomorphic to $(W_2, \leq_2)$. It is easy to check that this is an equivalence relation. Also note the property of "well order" is preserved by isomorphism. So from each equivalence class whose members are wosets, we can pick a representative whom we call an ordinal. Let $\Omega$ denote the set of all ordinals.

A classical result states that given two wosets $(W_1, \leq_1)$ and $(W_2, \leq_2)$, exactly one of the following holds: (this is known as trichotomy of ordinals)

• $(W_1, \leq_1)$ isomorphic to  $(W_2, \leq_2)$
• $(W_1, \leq_1)$ isomorphic to a proper initial segment of $(W_2, \leq_2)$
• $(W_2, \leq_2)$ isomorphic to a proper initial segment of $(W_1, \leq_1)$

So, we can define a partial order $\preceq$ on $\Omega$ in a natural way. With some work, we can show that $(\Omega, \preceq)$ is a woset. So there is an ordinal $\omega$ associated with $(\Omega, \preceq)$. Cantor had proved that any ordinal $\beta$ is the ordinal associated with the set $\{\alpha \in \Omega | \alpha \prec \beta \}$ well ordered using $\preceq$. So, in particular the proper subset $\{\alpha \in \Omega | \alpha \prec \omega \}$ of $\Omega$ is order isomorphic to $\omega$ and hence isomorphic to $\Omega$ which contradicts the trichotomy theorem.

Cantor's theory of sets consisted of laws of first order logic, axiom of extensionality (which states that two sets are equal iff they have the same elements) and axiom schema of comprehension (which states that given any logical property, we can construct a set containing precisely those elements satisfying the given logical  property) which turns out be the source of all these paradoxes. Standard theories like ZF set theory prevent these paradoxes by weakening the comprehension axiom, so we cannot construct universal set, set $R$ described in Russell's paradox, set of all  cardinals $\chi$ or set of all ordinals $\Omega$.

PS: This is an unreleased draft of an article which is probably gonna appear in CMIT's Donut. However, I have to cut down some words in final version.

References:

• Foundations of Mathematics by Kenneth Kunen
• Naive Set Theory by Paul Halmos