K

Grad. student in mathematics

Subset Relations of Sets

Definition 1 $A\subseteq B$ means that for any $x$, the proposition $x\in A\implies x\in B$ is always true.

The following two propositions are two properties of $\subset$.

Proposition 2 $A\subseteq A$ always holds.

Proof

$x\in A\implies x\in A$ is always true.

Proposition 3 If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

Proof

First, the premise means that for any $x$, the two propositions $x\in A\implies x\in B$ and $x\in B\implies x\in C$ are true. Therefore, by syllogism, $x\in A\implies x\in C$ is also true, and since $x$ can be chosen arbitrarily, $A\subseteq C$ holds.

From the above two propositions, we understand that $\subseteq$ becomes an order relation among sets. (§Definition of Order Relations, ⁋Definition 1)

Ordered Pairs

Almost the only tool we will use in set theory is the binary relation, and the language used to express it is the ordered pair. For example, the binary relation $\subseteq$ examined above can be thought of as the “set”

\[\subseteq=\{(A,B),(B,C),\cdots\}\]

that collects all ordered pairs $(A,B)$ satisfying $A\subseteq B$.1 Similarly, a function $y=f(x)$ can be thought of as the following set

\[F=\{(x_1,f(x_1)), (x_2,f(x_2)),\cdots\}\]

and the equivalence relation, which we have not yet defined, can also be represented as a set of ordered pairs in this way.

However, among the sets we have defined, there is no tool that can serve the role of ordered pairs that we learned in middle and high school. For example, since $\{A,B\}=\{B,A\}$, we cannot distinguish the order of $A$ and $B$ simply by using the axiom of pair once.

Definition 4 An ordered pair $(x,y)$ is defined as the set $\big\{\{x\}, \{x,y\}\big\}$.

For the above definition to have meaning, we must first prove the following lemma.2

Lemma 5 For two sets $x$, $y$, the set $(x,y)$ always exists and is unique.

Proof

The sets $\{x\}=\{x,x\}$ and $\{x,y\}$ each exist by the axiom of pair, and therefore the set $\big\{\{x\}, \{x,y\}\big\}$ also exists by the axiom of pair.

For uniqueness, $\{x\}=\{x,x\}$ and $\{x,y\}$ are first uniquely determined, and by applying the axiom of pair to these again, we can verify that the set $(x,y)$ obtained is also uniquely determined by using extensionality twice.

We have confirmed that the ordered pair $(x,y)$ is well-defined, but we need to verify whether the ordered pair defined this way satisfies $(x,y)\neq (y,x)$ for general $x,y$.

Proposition 6 For two ordered pairs $(x,y)$ and $(x’,y’)$, $(x,y)=(x',y')$ and $x=x'$ and $y=y'$ are equivalent.

Proof

If $x=x’$ and $y=y’$, then $(x,y)=(x’, y’)$ is obvious. This is because $\{x\}=\{x’\}$ and $\{x,y\}=\{x’, y’\}$.

Now, conversely, assume $(x,y)=(x’,y’)$. By definition,

\[\big\{\{x\},\{x,y\}\big\}=\big\{\{x'\},\{x',y'\}\big\}\]

holds. Since exactly one of $x=y$ and $x\neq y$ must hold, let us approach by dividing into two cases.

  • If $x=y$, the left side of the above equation becomes

    \[\big\{\{x\},\{x,x\}\big\}=\big\{\{x\},\{x\}\big\}=\big\{\{x\}\big\}\]

    so $\big\{\{x\}\big\}=\big\{\{x’\},\{x’,y’\}\big\}$. Therefore, $\{x\}=\{x’\}=\{x’,y’\}$, so $x=x’=y’$, and thus $x=x’=y=y’$. That is, since $x=x’$ and $y=y’$, the proof is complete for this case.

  • The remaining case is $x\neq y$. In this case, since $\{x,y\}\neq\{x’\}$, for the two ordered pairs to be equal, we must have $\{x\}=\{x’\}$ and $\{x,y\}=\{x’,y’\}$. Then from $\{x\}=\{x’\}$, we must have $x=x’$, and from this and $\{x,y\}=\{x’,y’\}$, we must have $y=y’$. Thus, the proof is complete for this case as well.

Consider the set

\[\bigcup z=\{x\}\cup\{x,y\}=\{x,y\}\]

Now, if we define the property

$P(s)$: There exists some $t$ such that $z=(s,t)$.

then we obtain the subset

\[\left\{s\in\bigcup z\mid P(s)\right\}\]

of the preceding set $\bigcup z$. This set is the singleton $\{x\}$. If we define a property $Q$ similarly, we obtain the singleton $\{y\}$.

Definition 7 For the two sets $\{x\}$, $\{y\}$ obtained by the above process, the unique element $x$ of $\{x\}$ is called the first component of $z=(x,y)$, and the unique element $y$ of $\{y\}$ is called the second component of $z=(x,y)$. These are denoted respectively as

\[x=\pr_1 z,\qquad y=\pr_2 z\]

Here, $\pr$ is an abbreviation for projection. Meanwhile, we can define the product $A\times B$ of two sets $A$ and $B$ as follows.

Definition 8 For two sets $A$ and $B$, the following set

\[\{z\mid(z=(x,y))\wedge (x\in A)\wedge(y\in B)\}\]

is called the cartesian product of $A$ and $B$, and is simply denoted as $A\times B$.

Also, similar to Definition 7, the sets $A$ and $B$ are called the first and second components of $A\times B$.

To determine the conditions under which two product sets $A\times B$ and $A’\times B’$ become equal, we only need to determine when one product set is contained in another.

Proposition 9 For two non-empty sets $A’$ and $B’$, $A'\times B'\subseteq A\times B$ and $A'\subseteq A$ and $B'\subseteq B$ are equivalent.

Proof

First, assume $A’\times B’\subseteq A\times B$. We need to show $A’\subseteq A$, so let any $a’\in A’$ be given and show that $a’\in A$. Since $B’$ is not empty, there exists some element $b’\in B’$. Therefore $(a’,b’)\in A’\times B’$, and since $A’\times B’\subseteq A\times B$, we have $(a’,b’)\in A\times B$ and $a’\in A$. Similarly, we can show $B’\subseteq B$.

Conversely, assume $A’\subseteq A$ and $B’\subseteq B$. We need to show that when any $z’\in A’\times B’$ is given, $z’\in A\times B$. Let $z’=(a’,b’)$. That is, $a’\in A’$ and $b’\in B’$, but by assumption, $a’$ and $b’$ are also elements of $A$ and $B$, so $(a,b)\in A\times B$.

When one of $A,B$ is empty, the following proposition can be applied.

Proposition 10 For two sets $A$ and $B$, $A\times B=\emptyset$ and $A=\emptyset$ or $B=\emptyset$ are equivalent.

Proof

First, assume $A\times B=\emptyset$. If both $A$ and $B$ are non-empty, we can pick some $a\in A$ and $b\in B$, so $(a,b)\in A\times B$, which is a contradiction.

Conversely, assume $A$ or $B$ is empty. Again, by contradiction, if $A\times B$ is non-empty, there exists some element $(a,b)\in A\times B$. Therefore $a\in A$ and $b\in B$, which contradicts the assumption that $A$ or $B$ is empty. The proof is complete.

References

[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

  1. Of course, this “set” is not a set. (§ZFC Axioms, ⁋Example 4) ↩

  2. With the proof of this lemma, we will no longer mention the axioms used in proofs. ↩

댓글남기기