Sets

Definition 1.1.1. If $$a$$ is a member of $$A,$$ we write

\[a\in A.\]

This basic relationship is called membership relation. An empty set is a set with no members.

Principle 1.1.2 (Principle of extension). Two objects are equal if they have the same members. Since the same objects have the same members, if follows that, for two objects $$A$$ and $$B,$$ $$A=B$$ if and only if, for all members $$x,$$ we have $(x\in A)\Leftrightarrow (x\in B).$

Theorem 1.1.3. There is only one empty set.

Proof. Let $$E_1$$ and $$E_2$$ be empty sets. Then there is no element $$x$$ that makes the truth values of $x\in E_1$ and $x\in E_2$ different from each other. But, according to Principle 1.1.2, two sets can be distinguished only if there exists an element such that $x\in E_1$ and $x\notin E_2$ or vice versa. That is, $$E_1=E_2.$$ $\square$

Notation 1.1.4. We write $\varnothing$ for the empty set. If $a_1,\dots,a_n$ are finitely many sets, we write $\lbrace a_1,\dots,a_n\rbrace$ for $\lbrace x : x=a_1 \lor \cdots \lor x=a_n\rbrace.$

Theorem 1.1.5. Everything is a set.

Proof. If $$A$$ is an object that is not a set, then there is no $$x$$ such that $x\in A.$ Thus $$A$$ is equal to the empty set by Principle 1.1.2, contradicting the assumption that it is not a set. Therefore everything is a set. $\square$

Definition 1.1.6. $$A$$ is a subset of $$B$$ if every element of $$A$$ is an element of $$B,$$ denoted by $A\subseteq B.$ That is,

\[A\subseteq B \iff \forall x\ (x\in A \rightarrow x\in B).\]

Then we see that

\[A = B \iff (A\subseteq B \land B\subseteq A).\]

If $A\subseteq B$ and $A\neq B,$ then $$A$$ is a proper subset of $$B,$$ denoted by $A\subset B.$

Definition 1.1.7. The power set of $$A$$ is the set $\mathcal P(A)$ defined by the equation

\[\mathcal P(A) = \lbrace X: X\subseteq A\rbrace .\]

Definition 1.1.8. The union of $\mathcal A$ is the set $\bigcup \mathcal A$ defined by the equation

\[\bigcup \mathcal A = \lbrace x : \exists X \in \mathcal A \ (x\in X)\rbrace .\]

We often write $\bigcup_{X\in \mathcal A}X$ and $A\cup B$ in place of $\bigcup \mathcal A$ and the union of a pair $\lbrace A, B\rbrace,$ respectively. That is,

\[\bigcup_{X\in \mathcal A}X = \bigcup \mathcal A\quad \text{and} \quad A\cup B = \bigcup \lbrace A, B\rbrace.\]

Definition 1.1.9. If $\mathcal A$ is a nonempty set, the intersection of $\mathcal A$ is the set $\bigcap \mathcal A$ defined by the equation

\[\bigcap \mathcal A = \lbrace x : \forall X \in \mathcal A \ (x\in X)\rbrace .\]

We often write $\bigcap_{X\in \mathcal A}X$ and $A\cap B$ in place of $\bigcap \mathcal A$ and the intersection of a pair $\lbrace A, B\rbrace,$ respectively. That is,

\[\bigcap_{X\in \mathcal A}X = \bigcap \mathcal A\quad \text{and} \quad A\cap B = \bigcap \lbrace A, B\rbrace.\]

Two sets $$A$$ and $$B$$ are disjoint if $A\cap B = \varnothing.$

Theorem 1.1.10. Let $$A,B$$ and $$C$$ be given. Then

\[A\cap (B \cup C) = (A\cap B) \cup (A \cap C) \quad \text{and} \quad A\cup (B \cap C) = (A\cup B) \cap (A \cup C).\]

Proof. To prove the first equality, we show that $A\cap (B \cup C)$ and $(A\cap B) \cup (A \cap C)$ have the same members. Suppose that $x\in A\cap (B \cup C).$ Then $x\in A$ and $x\in (B\cup C).$ This is divided into two cases. $x\in A$ and $x\in B,$ the first case, and $x\in A$ and $x\in B,$ the second case. In the first case, $x\in (A\cap B)$ so that $x\in (A\cap B) \cup (A \cap C).$ In the second case, $x\in (A\cap C)$ so that $x\in (A\cap B) \cup (A \cap C).$ Thus, if $x\in A\cap (B \cup C),$ then $x\in (A\cap B) \cup (A \cap C).$ Conversely, we suppose that $x\in (A\cap B) \cup (A \cap C).$ In the same way, we can see that if $x\in (A\cap B) \cup (A \cap C)$ then $x\in A\cap (B \cup C).$ Therefore $A\cap (B \cup C)$ and $(A\cap B) \cup (A \cap C)$ have the same elements. The second equality can be proven in the same way as above. $\square$

Definition 1.1.11. The relative complement of $$B$$ in $$A$$ is the set $$A-B$$ defined by

\[A - B = \lbrace x\in A : x\notin B\rbrace.\]

Theorem 1.1.12 (De Morgan’s laws). Let $$U$$ be a set, and let $$A,B\subseteq U$.$ For every $X\subseteq U,$ define the relative complement of $$X$$ to $$U$$ by $X^{c}=U - X.$ Then

\[(A\cup B)^{c}=A^{c}\cap B^{c} \quad \text{and} \quad (A\cap B)^{c}=A^{c}\cup B^{c}.\]

Proof. To prove the first equality, we show that $(A\cup B)^{c}$ and $A^{c}\cap B^{c}$ have the same members. Suppose that $$x$$ is a member of $(A\cup B)^{c}.$ Then $$x$$ is not a member of $A\cup B,$ hence $x\notin A$ and $x\notin B.$ Since $x\notin X$ implies $x\in X^c,$ we have $x\in A^c$ and $x\in B^c.$ Therefore $$x$$ is a member of $A^{c}\cap B^{c},$ so that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}.$ We now suppose that $$x$$ is a member of $A^{c}\cap B^{c}.$ Then $x\in A^c$ and $x\in B^c.$ It follows that $x\notin A$ and $x\notin B,$ so that $x\notin A\cap B.$ Therefore $x\in (A\cap B)^c,$ so $A^{c}\cap B^{c}\subseteq A\cup B)^{c}.$ Since we have $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ and $A^{c}\cap B^{c}\subseteq A\cup B)^{c},$ it is concluded that $(A\cup B)^{c}=A^{c}\cap B^{c}.$ The second equality can be proven in the same way as above. $\square$

Theorem 1.1.13. Let $$U$$ be a set, and let $A_i\subseteq U$ for every $i\in I.$ Then

\[\lowparen{\bigcup_{i\in I } A_i}^{\!\!c} = \bigcap_{i\in I } A^c_i \quad \text{and} \quad \lowparen{\bigcap_{i\in I } A_i}^{\!\!c} = \bigcup_{i\in I } A^c_i.\]

Proof. To prove the first equality, we show that the two sets have the same members. Suppose that

\[x\in \lowparen{\bigcup_{i\in I } A_i}^{\!\!c}.\]

Then we have $x\notin \bigcup_{i\in I } A_i.$ Thus $x\notin A_i$ for every $i\in I.$ It follows that $x\in A^c_i$ for every $i\in I.$ Hence $x\in \bigcap_{i\in I } A^c_i$ so that

\[\lowparen{\bigcup_{i\in I } A_i}^{\!\!c} \subseteq \bigcap_{i\in I } A^c_i.\tag{$\ast$}\]

We now suppose that $x\in \bigcap_{i\in I } A^c_i.$ Then we have $x\in A^c_i$ for every $i\in I.$ It follows that $x\notin A_i$ for every $i\in I.$ Hence $x\notin \bigcup_{i\in I } A_i.$ Therefore

\[x\in \lowparen{\bigcup_{i\in I } A_i}^{\!\!c}\]

so that

\[\bigcap_{i\in I } A^c_i \subseteq \lowparen{\bigcup_{i\in I } A_i}^{\!\!c}.\tag{$\ast\ast$}\]

By $(\ast)$ and $(\ast\ast),$ it is concluded that

\[\lowparen{\bigcup_{i\in I } A_i}^{\!\!c} = \bigcap_{i\in I } A^c_i .\]

The second equality can be proven in the same way as above. $\square$

References

Cameron, P. J. (1998). Sets, logic and categories. Springer. https://doi.org/10.1007/978-1-4471-0589-3

External

1.1. Sets

References