Set

1. Set Operation

1.1. Symmetric Difference

Definition 1.1    Suppose \(A\) and \(B\) are two sets. The symmetric difference of \(A\) and \(B\), denoted \(A \triangle B\), is the set \((A-B) \cup (B-A)\). The symmetric difference of two sets, a.k.a. the disjunctive union is the set of elements which are in either of the sets, but not in their intersection.

Property 1.1    Suppose \(A, B\) and \(C\) are sets, and \(X\) is a universal set:

    (1) \(A \cup B=(A \cap B) \cup (A \triangle B)\);

    (2) \(A \triangle \varnothing=A, A \triangle A=\varnothing, A \triangle A^c=X, A \triangle X=A^c\);

    (3) \(A \triangle B=B \triangle A\);

    (4) \((A \triangle B) \triangle C=A \triangle (B \triangle C)\);

    (5) \(A \cap (B \triangle C)=(A \cap B) \triangle (A \cap C)\);

    (6) \(A^c \triangle B^c= A \triangle B\);

    (7) \(A=A \triangle B \Leftrightarrow B=\varnothing\);

    (8) For any \(A\) and \(B\), there exists an only set \(E\) such that \(E \triangle A=B.\) In fact, \(E=B \triangle A\).

1.2. Limit of a Sequence of Sets

Definition 1.2    Suppose \(\{A_k\}\) is a sequence of sets. If \[A_1 \supset \cdots \supset A_k \supset \cdots,\] then \(\{A_k\}\) is a decreasing sequence of sets. The limit of \(\{A_k\}\), denoted \(\displaystyle \lim_{k \to \infty} A_k\), is \(\displaystyle \bigcap_{k=1}^\infty A_k\).

If \[A_1 \subset \cdots \subset A_k \subset \cdots,\] then \(\{A_k\}\) is a increasing sequence of sets. The limit of \(\{A_k\}\), denoted \(\displaystyle \lim_{k \to \infty} A_k\), is \(\displaystyle \bigcup_{k=1}^\infty A_k\).

Example 1.1    Suppose \(A_n=[n, \infty), n \in \mathbb{N}\), then \(\displaystyle \lim_{n \to \infty} A_n=\varnothing\).

Example 1.2    Suppose \[f_1(x) \leq \cdots \leq f_n(x) \leq \cdots, x \in \mathbb{R},\] and \(\displaystyle \lim_{n \to \infty} f_n(x)=f(x).\) For a given real number \(t\), let \[E_n=\{x: f_n(x)>t\}.\] Obviously, \(E_1 \subset \cdots \subset E_n \subset \cdots\), and \[\lim_{n \to \infty} E_n=\bigcup_{n=1}^\infty \{x: f_n(x)>t\}=\{x: f(x)>t\}.\]

Definition 1.3    Suppose \(\{A_k\}\) is a sequence of sets. Let \[B_j=\bigcup_{k=j}^\infty A_k, j \in \mathbb{N}.\] Since \(B_j \supset B_{j+1}\), then we define \[\lim_{j \to \infty} B_j=\lim_{j \to \infty}\bigcup_{k=j}^\infty A_k=\bigcap_{j=1}^\infty B_j=\bigcap_{j=1}^\infty\bigcup_{k=j}^\infty A_k\] as the upper limit of sets of \(\{A_k\}\), denoted as \(\displaystyle \varlimsup_{k \to \infty} A_k.\)

Similarly, we define \[\varliminf_{k \to \infty} A_k= \bigcup_{j=1}^\infty \bigcap_{k=j}^\infty A_k\] as the lower limit of sets of \(\{A_k\}\).

If \(\displaystyle \varlimsup_{k \to \infty} A_k=\varliminf_{k \to \infty} A_k\), then we say the limit of \(\{A_k\}\) exists, denoted as \(\displaystyle \lim_{k \to \infty} A_k\).

Example 1.3    Suppose \(E\) and \(F\) are sets. Let \[A_k=\begin{cases} E, &k\ \text{is odd}, \\ F, &k\ \text{is even}. \end{cases}\] Then we have \[\varliminf_{k \to \infty} A_k=E \cup F, \varliminf_{k \to \infty} A_k=E \cap F.\]

Theorem 1.2    Suppose \(\{A_k\}\) is a sequence of sets, then \[\varlimsup_{k \to \infty} A_k=\{x: \forall j \in \mathbb{N}, \exists k \geq j\ \text{s.t.}\ x \in A_k\},\] and \[\varliminf_{k \to \infty} A_k=\{x: \exists j_0 \in \mathbb{N}\ \text{s.t.}\ k \geq j_0 \Rightarrow x \in A_k\}.\]

Proof. Suppose \(\displaystyle x \in \varlimsup_{k \to \infty} A_k=\bigcap_{j=1}^\infty \bigcup_{k=j}^\infty A_k.\) This is equivalent to \[\forall j \in \mathbb{N}, x \in \bigcup_{k=j}^\infty A_k,\] which is equivalent to \[\forall j \in \mathbb{N}, \exists k \geq j\ \text{s.t.}\ x \in A_k.\]

Suppose \(\displaystyle x \in \varliminf_{k \to \infty} A_k=\bigcup_{j=1}^\infty \bigcap_{k=j}^\infty A_k.\) This is equivalent to \[\exists j_0 \in \mathbb{N}\ \text{s.t.}\ x \in \bigcap_{k=j_0} ^\infty A_k,\] which is equivalent to \[\exists j_0 \in \mathbb{N}\ \text{s.t.}\ k \geq j_0 \Rightarrow x \in A_k.\]

\(\square\)

The upper limit of \(\{A_k\}\) includes the elements that belong to an infinite number of sets in \(\{A_k\}\). The lower limit of \(\{A_k\}\) includes the elements that do not belong to only finitely many sets in \(\{A_k\}\). Therefore, \(\displaystyle \varlimsup_{k \to \infty} A_k \subset \varliminf_{k \to \infty} A_k.\)

Example 1.4    Suppose \[A_{2m+1}=\left[0, 2-\frac{1}{2m+1}\right], m=0, 1, \ldots\] and \[A_{2m}=\left[0, 1+\frac{1}{2m}\right], m=1, 2, \ldots.\] Find \(\displaystyle \varlimsup_{n \to \infty} A_n\) and \(\displaystyle \varliminf_{n \to \infty} A_n\).

Solution. Obviously, \([0, 1] \subset A_n\). For every \(x \in (1, 2)\), when \(m \to \infty\), there are infinite many sets in \(\{A_{2m}\}\) such that \(x \notin A_{2m}\), and thus \(\displaystyle x \notin \varliminf_{n \to \infty} A_n\). There are infinite many sets in \(\{A_{2m+1}\}\) such that \(x \in A_{2m+1}\), and thus \(\displaystyle \varlimsup_{n \to \infty} A_n=[0, 2)\) and \(\displaystyle\varliminf_{n \to \infty} A_n=[0, 1]\).

Example 1.5    Use set notation to represent \(\displaystyle \lim_{n \to \infty} a_n=a\).

Solution. Since \(\displaystyle \lim_{n \to \infty} a_n=a\), then \[\forall \varepsilon>0, \exists N \in \mathbb{N}\ \text{s.t.}\ \forall n \geq N, |a_n-a|<\varepsilon.\] Therefore \[a \in \bigcap_{\varepsilon \in \mathbb{R}^+} \bigcup_{N=1}^\infty \bigcap_{n \geq N} \{x: |a_n-x|<\varepsilon\}=\bigcap_{\varepsilon \in \mathbb{R}^+} \varliminf_{n \to \infty} \{x: |a_n-x|<\varepsilon\}.\]

2. Cardinal Number

Definition 2.1    Suppose \(A\) and \(B\) are sets. If there exists a bijection from \(A\) to \(B\), then we say \(A\) is equipotent to \(B\), denoted as \(A \sim B\). Specifically, \(\varnothing \sim \varnothing\).

Property 2.1    An equipotent relationship is an equivalence relation, i.e., for any sets \(A, B\) and \(C\):

    (1) \(A \sim A\);

    (2) If \(A \sim B\), then \(B \sim A\);

    (3) If \(A \sim B\) and \(B \sim C\), then \(A \sim C\).

Definition 2.2    Suppose \(A\) and \(B\) are sets. If \(A \sim B\), then the cardinal number of \(A\) and \(B\) are equal, denoted as \(\overset{=}{A}=\overset{=}{B}\).

基数的概念可以看作有限集合中所含元素个数的推广. 对于一个集合\(A\)，我们考虑所有与\(A\)对等的集合所构成的类. 公理集合论允许我们从每一个这样的类中按确定的方式选出一个代表（即所谓良序集——依某种意义排好了次序的集），我们把这个代表定义为这一类中各个集合的基数，记之为\(\overset{=}{A}\).

Definition 2.3    Suppose \(A\) and \(B\) are sets. If \(A \not\sim B\), and \(B^* \sim A\) where \(B^* \subset B\), then \(\overset{=}{A}<\overset{=}{B}\) or \(\overset{=}{B}>\overset{=}{A}\).

We can show that for any two sets \(A\) and \(B\), one and only one of the relations holds: \[\overset{=}{A}<\overset{=}{B}, \overset{=}{A}=\overset{=}{B}, \overset{=}{A}>\overset{=}{B}.\]

Theorem 2.2 (Cantor-Bernstein Theorem)    Suppose \(A\) and \(B\) are non-empty sets. If \(A\) is equipotent to a subset of \(B\), and \(B\) is equipotent to a subset of \(A\), then \(A \sim B\).

Corollary 2.3    If \(A \supset B \supset C\) and \(A \sim C\), then \(A \sim B\).

3. Countable Set and Uncountable Set

Definition 3.1    The countable sets are the sets that are equipotent to \(\mathbb{N}\). Note that \(\overset{=}{\mathbb{N}}=\aleph_0\).

Definition 3.2    The uncountable sets are the sets that are not countable sets.

关于可数集与不可数集的相关定理与推论在抽象数学一课中已经进行了详细探讨，在此不再赘述. 但我们仍应当记得——任何无限集合都至少包含一个可数子集，也意味着可数集在所有无限集中有最小的基数；可数集的任何无限子集仍是可数集；至多可数个至多可数集的并仍是至多可数集；\(\mathbb{Q}\)是可数集；代数数集\(\mathcal{A}\)是可数集；有限个至多可数集的直积是至多可数集；\(\mathbb{R}\)是不可数集且连续基数记为\(\overset{=}{\mathbb{R}}=c>\aleph_0\)；至多可数个不可数集的并或直积是不可数集；值得特别注意的是：可数个至多可数集的直积不一定可数；\(c\)个基数为\(c\)的集合的并的基数仍然是\(c\).