subset

集合定義

Question

98 清大資應證明題
93 師大資工

定義

集合建構符號, empty set(空集合)
集合運算:對稱差(symmetric difference)

Proper subset

\( A\subseteq B \) and \( A\neq B \)
Sign as \( A\subset B \)

Empty set

Suppose \( A= \{\} \)
\( A \) is empty set
Sign as \( \emptyset \)

Suppose \( A=\{1,2,3\}, B=\{\}=\emptyset \)
\( \emptyset\not\in A, \emptyset=\{\}\subseteq A\)
\( \emptyset=\{\} \) is subset of A
\( \emptyset\not\in B, \emptyset=\{\}\subseteq B \)
\( \emptyset=\{\} \) is subset of B

Empty set is subset any of set.	Example: \( \emptyset\subseteq\emptyset \) \( \{\}\subseteq\{\} \)	\( \{\}=\emptyset\not\in\emptyset=\{\} \) \( \{\}=\emptyset\in\{\emptyset\}=\{\{\}\} \)
\( A = \{\;\emptyset, \; \{\emptyset\}, \;\{\emptyset, \{\emptyset\}\}\;\} \) \( \emptyset \in A= \{\;{\color{blue}\emptyset}, \; \{\emptyset\}, \;\{\emptyset, \{\emptyset\}\}\;\} \) \( \{\emptyset\} \in A= \{\;\emptyset, \; {\color{blue}\{\emptyset\}}, \;\{\emptyset, \{\emptyset\}\}\;\} \) \( \{\; \emptyset,\{\emptyset\} \;\} \subset A= \{\;{\color{blue}\emptyset, \; \{\emptyset\}}, \;\{\emptyset, \{\emptyset\}\}\;\} \) \( \{\; \{\emptyset,\{\emptyset\}\} \;\} \subset A= \{\;\emptyset, \; \{\emptyset\}, \;{\color{blue}\{\emptyset, \{\emptyset\}\}}\;\} \) \( \{\; \emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\} \;\} \subseteq A= \{\;{\color{blue}\emptyset, \; \{\emptyset\}, \;\{\emptyset, \{\emptyset\}\}}\;\} \)

\( |A|\rightarrow \text{ cardinality of A.} \)
\( \emptyset \not\equiv \{\emptyset\} \)
\( A = \emptyset = \{\} \text{ have 0 element}, |A|=0. \)
\( B= \{\emptyset\} \text{ have 1 element}, |B|=1. \)
\( C= \{\{\emptyset\}\} \text{ have 1 element}, |C|=1. \)

\( x\in A, \{x\}\subseteq A \)

Element in set and subset

\( A\subseteq B \)
\( \forall x(x\in A\rightarrow x\in B) \)

\( A=B \leftrightarrow (A\subseteq B) \cap (B\subseteq A) \)
\( (A\subseteq B)\cap(B\subseteq C)\rightarrow A\subseteq C \)

Set Operation

Suppose \( U \text{ is universal set.} \), \( A,B\subseteq U \)

difference

\( A - B=\{x|(x\in A) \cap (x\not\in B)\} \)

complement

Venn diagram
left circle: A
right circle: B

relative complement as difference. \( A^c\cap B = B-A\) \( =B\backslash A \)
absolution complement \( A^c=U\backslash A=\overline{A}\) \( =\{x\|(x\not\in A) \cap (x\in U)\} \) \( =U-A \)

symmetric difference

\( \oplus \)(oplus) , \( \Delta \)(delta)

\( A\oplus B =A\Delta B \)
\( =(A-B)\cup(B-A) \)
\( =(A\cup B)-(A\cap B) \)

example

For \( A= \{a,\{a\}, \{a,b\},\emptyset\} \), determine the following sets.

\( A-\{a\} \)
Ans.
\( \{{\color{blue}a},\{a\}, \{a,b\},\emptyset\}-\{a\} \)
\( =\{\{a\}, \{a,b\},\emptyset\} \)
\( \{a,b,c\}-A \)
\( Ans. \)
\( \{{\color{blue}a},b,c\}- \{a,\{a\}, \{a,b\},\emptyset\} \)
\( =\{b,c\} \)
\( ( A \cup \{a,b\} ) \cap \{\emptyset\} \)
Ans.
\( (\; \{{\color{red}a},\{a\}, \{a,b\},\emptyset\} \cup \{{\color{red}a},{\color{blue}b}\} \;) \cap \{\emptyset\} \)
\( =\{a,b,\{a\}, \{a,b\},{\color{blue}\emptyset}\} \cap \{\emptyset\} \)
\( =\{\emptyset\} \)

Operation properties

\( A,B,C\subseteq U \)

associative laws

\( A\cup(B\cup C) = (A\cup B)\cup C \)
\( A\cap(B\cap C) = (A\cap B)\cap C \)

distributive laws

\( A\cup(B\cap C) = (A\cup B)\cap (A\cup C) \)
\( A\cap(B\cup C) = (A\cap B)\cup (A\cap C) \)

identity laws

\( A\cup\emptyset=A \)
\( A\cap U=A \)

inverse laws

\( A\cup \overline{A}=U \)
\( A\cap\overline{A}=\emptyset \)

domination laws

\( A\cup U=U \),
\( A\cap\emptyset =\emptyset \)

absorption laws

\( A\cup(A\cap B)=A \),
\( A\cap(A\cup B)=A \)

OPlus

associative and distributive(interaction) laws

\( (A\oplus B)\oplus C= A\oplus(B\oplus C) \)
\( A\cap(B\oplus C)=(A\cap B)\oplus(A\cap C) \)

Hint: Using Venn Diagram to solute.

De Morgan's law

\( \overline{A\cup B}= \overline{A}\cap\overline{B} \)
\( \overline{A\cap B}= \overline{A}\cup\overline{B} \)

proof \( \overline{A\cup B}= \overline{A}\cap\overline{B} \)

(\( \leftrightarrow \))
\( \forall x\in U\)
\( x\in\overline{A\cup B} \)
\( \leftrightarrow x\not\in (A\cup B) \)
\( \leftrightarrow x\not\in A \cup x\not\in B \)
\( \leftrightarrow x\in \overline{A}\cap \overline{B} \)
\( \therefore \overline{A\cup B} = \overline{A}\cap\overline{B} \)

Cardinality

Suppose \( A \) is a set.
Number of no repeated elements in A is cardinality. Sign as \( |A| \)
example:
\( A=\{1,2,\{1,2\}\}, |A|=3 \)
\( A=\{1,1,2,2,2,\{1,2\} \}, |A|=3\)
\( A=\{\}=\emptyset, |A|=|\emptyset|=0 \)
\( A=\{\{\emptyset\}\}, |A|=1 \)