3. 모임과 집합 (i): 모임의 대수Classes and Sets (i): The Algebra of Classes

By Definition 3.3, since $A$ is a proper class, $A \notin X$ for every class $X$, and since $B$ is a proper class, $B \notin X$ for every class $X$. Thus for an arbitrary class $X$, both the sentences $A \in X$ and $B \in X$ are false.

By the truth table for the implication in Definition 2.6, an implication with a false premise is always true. Therefore

are both true. Thus by Notation 2.18,

Since $X$ was an arbitrary class, by Definition 3.6,

By the axiom of extent (Axiom 3.9), for all classes $A$ and $B$,

so

By Notation 2.18, $x \in A \iff x \in B$ is the abbreviation for $(x \in A \implies x \in B) \wedge (x \in B \implies x \in A)$, so by De Morgan's law from Exercise 2.21,

By the truth table in Definition 2.6, the implication $x \in A \implies x \in B$ is false if and only if $x \in A$ is true and $x \in B$ is false, i.e. $x \in A \wedge x \notin B$. Similarly, $x \in B \implies x \in A$ is false if and only if $x \in B \wedge x \notin A$. Combining these,

In other words, $A \neq B$ means that there exists an element $x$ that belongs to exactly one of $A$ and $B$.

(4) Assume that $A \subset B$ and $B \subset A$. By the definition of $\subset$ (Definition 3.11),

Thus by Notation 2.18,

Therefore by the axiom of extent, $A = B$.

(5) Assume that $A \subset B$ and $B \subset C$. By the definition of $\subset$,

Thus by Theorem 2.17 (the transitive law),

Therefore by the definition of $\subset$, $A \subset C$.

Here we prove these statements without using the axiom of extent, using only Definition 3.6 (the equality of classes).

1. By Example 2.8(4), for a fixed class $X$, the sentence
   $$A \in X \implies A \in X$$
   is always true. By Notation 2.18, $A \in X \iff A \in X$ is the abbreviation for $(A \in X \implies A \in X) \wedge (A \in X \implies A \in X)$, which is the conjunction of two true sentences and hence true. That is,
   $$A \in X \iff A \in X.$$
   Since $X$ was an arbitrary class, by Definition 3.6, $A = A$.
2. Assume that $A = B$. By Definition 3.6, for every class $X$,
   $$A \in X \iff B \in X.$$
   Thus by the definition of $\iff$ (Notation 2.18) and Theorem 2.19(4),
   $$B \in X \iff A \in X.$$
   Since $X$ was an arbitrary class, by Definition 3.6, $B = A$.
3. Assume that $A = B$ and $B = C$. By Definition 3.6, for an arbitrary class $X$ we have the following four statements.
   $$A \in X \implies B \in X, \qquad B \in X \implies A \in X,$$
   $$B \in X \implies C \in X, \qquad C \in X \implies B \in X.$$
   By the first and third implications and Theorem 2.17 (the transitive law),
   $$A \in X \implies C \in X.$$
   Similarly, by the fourth and second implications and Theorem 2.17,
   $$C \in X \implies A \in X.$$
   Combining these two implications, by Notation 2.18,
   $$A \in X \iff C \in X.$$
   Since $X$ was an arbitrary class, by Definition 3.6, $A = C$.

The axiom of class construction (Axiom 3.16) only permits us to form the class of all elements $x$ which satisfy a statement $P(x)$; it does not guarantee the existence of the class of all classes $X$ — elements and proper classes alike — which satisfy $P(X)$ (Remark 3.17(2)).

To see why this restriction is necessary, recall how Von Neumann's idea (Idea 1.14) and the class axiom (Axiom 1.15) avoided Russell's paradox. There, only elements were admitted as candidates, so $S = \{x : x \text{ is an element and } x \notin x\}$ was formed. If $S \in S$, then by the definition of $S$, $S \notin S$, a contradiction; hence $S \notin S$. If we further assume that $S$ is an element, then by the definition of $S$ and $S \notin S$ we get $S \in S$, again a contradiction; hence $S$ is not an element. That is, $S$ is a proper class. By Definition 3.3, a proper class cannot be an element of any class, so $S \notin S$ simply holds and no further contradiction arises — the paradox is resolved precisely because $S$, not being an element, was never eligible to be a member of anything in the first place.

Now let us see what happens once this escape route is closed. Suppose that the class $C$ of all classes $X$ (elements and proper classes alike) satisfying $P(X)$ exists in general, and take in particular

so that $C = \{X : X \notin X\}$. Asking whether $C \in C$ or $C \notin C$ gives the following.

• If $C \in C$, then by the definition of $C$, $C$ must satisfy $P(C)$, i.e. $C \notin C$, contradicting the assumption.
• If $C \notin C$, then $C$ is a class satisfying $P(C)$, i.e. $C \notin C$, so by the definition of $C$, $C \in C$, again contradicting the assumption.

Therefore

which is an outright contradiction (Russell's paradox). Note that, unlike the case of $S$, here $C$ becoming a proper class (i.e. $C \notin C$) does not by itself dissolve the contradiction. Since $C$, by its definition, must contain every class satisfying $P(X) = (X \notin X)$ regardless of whether that class is an element or a proper class, taking $C$ to be a proper class merely reproduces the contradiction: by Definition 3.3 it gives $C \notin C$, and $C \notin C$ is exactly the condition $P(C)$, so the definition of $C$ forces $C \in C$, contradicting that $C$ is a proper class. Hence there is no way to escape this contradiction. This is exactly why the class of all classes $X$ satisfying $P(X)$ cannot exist in general.

By Definition 3.21,

Note that the symbol $\vee$ means “or”. Thus

The statement $x \in A \vee x \in B$ can be expressed entirely in terms of the symbols $\in$, $\vee$, and the variables $x$, $A$, $B$, so it is a statement in the formal language required by the axiom of class construction (Axiom 3.16). Therefore, the class $A \cup B$ exists by the axiom of class construction.

Note. Theorem 3.28(4) is printed as $B \cap B \subset B$ in the source, and the proof there derives exactly that form from (3) by taking $A = B$. By symmetry with (1)–(3), however, the intended statement is $A \cap B \subset B$. Below we first derive that fact directly, in the same way the source proves (3), and then use it.

First we prove the only if part. Assume $A \subset B$. By Theorem 3.28(3),

On the other hand, if $x \in A$, then by the assumption $A \subset B$ we also have $x \in B$. Thus $x \in A$ and $x \in B$, so $x \in A \wedge x \in B$. That is,

so by the definition of the intersection (Definition 3.19) and the definition of $\subset$ (Definition 3.11), $A \subset A \cap B$. Combining these two inclusions, by Theorem 3.13(4),

Next we prove the if part. First we check that $A \cap B \subset B$. By the definition of the intersection and Theorem 2.13(4),

so by the definition of $\subset$, $A \cap B \subset B$ (this is Theorem 3.28(4) as read in the note above). Now assume that $A = A \cap B$. Then

By the axiom of extent, the definitions of the complement, the intersection, and the union, and Exercise 2.21,

(2) By the definition of the intersection and Theorem 2.19(4),

(3) By the definition of the union and Theorem 2.19(1),

(4) By the definition of the intersection and Theorem 2.19(2),

(6) By the definition of the intersection and Theorem 2.19(6),

(8) By the definition of the union, the definition of the intersection, and Theorem 2.19(8),

(4) By Theorem 3.25(2),

Thus by Theorem 3.29(2),

(5) By Definition 3.23, $\mathcal{U} = \{x : x = x\}$, so by Theorem 3.13(1), every element $x$ satisfies $x \in \mathcal{U}$. That is, there is no element $x$ such that $x \notin \mathcal{U}$. Thus by the definition of the complement (Definition 3.27), $\mathcal{U}^c = \{x : x \notin \mathcal{U}\}$ has no elements at all, so $x \in \mathcal{U}^c \implies x \in \emptyset$ is true (since the premise is always false). Thus by the definition of $\subset$,

On the other hand, by Theorem 3.25(1),

Thus by Theorem 3.13(4),

(6) By Definition 3.24, $\emptyset$ has no elements at all, so $x \notin \emptyset$ holds for every element $x$. Thus by the definition of the complement, every element $x$ satisfies $x \in \emptyset^c$. On the other hand, by Definition 3.23, every element $x$ satisfies $x \in \mathcal{U}$. Therefore, for every element $x$,

holds (both sides being always true), and by the axiom of extent,

(7) By Theorem 3.25(2),

Conversely, assume $x \in \mathcal{U}$. Then $x$ is an element. We divide into two cases according to whether $x \in A$ is true or false. If $x \in A$ is true, then by the definition of the union (Definition 3.21), $x \in A \cup A^c$. If $x \in A$ is false, then by the definition of the complement (Definition 3.27), $x \in A^c$, so again by the definition of the union, $x \in A \cup A^c$. In either case we obtain $x \in A \cup A^c$, so

Thus $\mathcal{U} \subset A \cup A^c$. Combining the two inclusions, by Theorem 3.13(4),

(8) Assume $x \in A \cap A^c$. By the definition of the intersection (Definition 3.19) and the definition of the complement,

However, no element can satisfy $x \in A$ and $x \notin A$ at the same time. Thus there is no element $x$ satisfying $x \in A \cap A^c$, so $x \in A \cap A^c \implies x \in \emptyset$ is true (since the premise is always false), and by the definition of $\subset$,

On the other hand, by Theorem 3.25(1),

Thus by Theorem 3.13(4),