Set Theory

Donovan D Chang

12 Set Theory

The set theory is a branch of mathematical logic studying sets. Let us begin with the formal definition of a set.

$\left\lbrace x: P(x)\right\rbrace$

denotes the collection of elements, represented by $x$ , defined by $P(x)$ , a one-variable open sentence describing the properties of the set. Following is an example of expressing the same set.

$\begin{align*} &\left\lbrace x: x \, \text{is an odd natural number}\right\rbrace\\ = &\left\lbrace 1,3,5,\cdots \right\rbrace\\ = &\left\lbrace x:x\in \mathbb{N} \,\text{, where}\, x\,\text{is odd}\right\rbrace \end{align*}$

How is an empty set, denoted $\emptyset$ , without any elements? In fact, an empty set is the empty set, i.e. the set without any element is unique. Formally the empty set or null set is defined as

Definition. (The Empty Set or Null set)

$\emptyset =\left\lbrace x:x \neq x\right\rbrace$

So, we can see formally the empty set is defined as a contradiction, that the empty set is the collection of elements such that $x$ is not $x$ itself, which can never be true.

Next, we move on to the definition of a subset. We say one set is a subset of another set when every element of the former set is also the element of the latter set. Therefore, technically every set is the subset of the set itself, but in this case, we call this a trivial subset; otherwise, non-trivial or proper subsets. Formal definition of a subset is as follows:

Definition. (Subset)

$A\subseteq B \Leftrightarrow \left(\forall x\right)\left(x\in A\Rightarrow x\in B\right)$

where $\forall$ means “for all” or “every”.

Therefore, to prove one set is a subset of another set, we take the following approach:

Direct Proof of $A \subseteq B$ .
Let $x$ be an arbitrary object.
Suppose $x\in A$ .
$\cdots$
Then, $x \in B$ .
Therefore, $A \subseteq B$ .

How about the equality of two sets? Intuitively we would think any given two sets are the same, i.e. equal, whenever the elements included in each set are identical. However, individually examining every element of each set would not be so efficient, or infeasible, when the number of elements is large, or even impossible when the number of elements is infinitely many, either countable or not. Therefore, we need a strategy, and typically the proof of the equality of sets takes the form:

Proof of the Equality of Sets $A$ and $B$ .
1. Prove $A \subseteq B$ .
2. Prove $B \subseteq A$ .
3. Therefore, $A=B$ .

Let us illustrate with an example.

Example. Prove $X=Y$ , where $X=\left\lbrace x\in \mathbb{C}:x^2=-1 \right\rbrace$ and $Y=\left\lbrace i,-i\right\rbrace$ .\,

1. Prove $X \subseteq Y$ .
Let $t\in X$ .
Then, $t^2=-1$ by definition of $X$ .
Then,

$\begin{align*} t^2+1 &= 0\\ (t+i)(t-i) &= 0\\ \therefore t &= \pm i \end{align*}$

Therefore, if $t\in X$ , then $t\in Y$ .
Therefore, $X\subseteq Y$ .

2. Prove $Y \subseteq X$ .

Use brute force.

$\begin{align*} i^2+1 &= -1+1\\ &= 0 \end{align*}$

Also,

$\begin{align*} (-i)^2+1 &= -1+1\\ &= 0 \end{align*}$

Therefore, $y\in X$ for all $y\in Y$ , i.e. $Y \subseteq X$ .

3. Therefore, by 1. and 2., $X=Y$ .

Set Operations

Now we turn to set operations, operations between multiple sets. First, binary, involving only 2 sets, operations are introduced.

Definition.
Let $A$ and $B$ sets.
The union of $A$ and $B$ is the set $A\cup B=\left\lbrace x:x\in A \, \text{or} \, x\in B\right\rbrace$ .
The intersection of $A$ and $B$ is the set $A\cap B=\left\lbrace x:x\in A \, \text{and} \, x\in B\right\rbrace$ .
The difference of $A$ and $B$ is the set $A-B=A\setminus B=\left\lbrace x:x\in A \,\text{and}\, x\notin B\right\rbrace$ .

Consider a case where there is no common element between the two sets $A$ and $B$ , i.e. $A\cap B=\emptyset$ . Then, we call the sets $A$ and $B$ are disjoint.

So far we have discussed sets defined without giving any reference to a source, i.e. we simply referred an element to be arbitrary, where the universe it comes from was not defined. In fact, defining the boundary for the universe yields another useful concept complement. To define formally,

Definition.
Let $U$ be the universe, where $A\subseteq U$ .
The complement of $A$ is the set

$\begin{align*} A^c &= U\setminus A\\ &= \left\lbrace x:x\in U \, \text{and} \, x\notin A\right\rbrace \end{align*}$

Exploring with the definitions introduced so far, we can reach a few theorems as follows:

Theorem.
Let $U$ be the universe, where $A,B\subseteq U$ . Then,

1. Inclusion Property

$\begin{align*} A &\subseteq A\cup B\\ A\cap B &\subseteq A \end{align*}$

2. Commutativity

$\begin{align*} A\cup B &= B\cup A\\ A\cap B &= B \cap A \end{align*}$

3. Associativity

$\begin{align*} A\cup \left( B\cup C\right) &= \left(A\cup B\right) \cup C\\ A\cap \left( B\cap C\right) &= \left(A\cap B\right) \cap C \end{align*}$

4. Distributivity

$\begin{align*} A\cap \left( B\cup C\right) &= \left(A\cap B\right) \cup \left(A\cap C\right)\\ A\cup \left( B\cap C\right) &= \left(A\cup B\right) \cap \left(A\cup C\right) \end{align*}$

5. DeMorgan’s Laws

$\begin{align*} \left( A \cup B\right)^c &= A^c \cap B^c\\ \left( A \cap B\right)^c &= A^c \cup B^c \end{align*}$

The commutative, associative, and distributive laws also uphold in set operations as in the case of algebraic binary operations – all 3 laws hold in multiplication; and associativity and commutativity hold in addition. We conclude this section with the proof of DeMorgan’s Laws for set operations.

Proof of DeMorgan’s Laws.
1. $\left( A \cup B\right)^c = A^c \cap B^c$

(a) $\left( A \cup B\right)^c \subseteq A^c \cap B^c$
Let $x\in \left( A \cup B\right)^c$ .
Then, $x\in U$ and $x\notin (A\cup B)$ .
Then, $x\in U$ and $\sim\left(x\in A \,\text{or}\, x\in B\right)$ .
Then, $x\in U$ and $\left(x\notin A \,\text{and}\, x\notin B\right)$ .
Then, $\left( x\in U \,\text{and}\, x\notin A \right)$ and $\left( x\in U \,\text{and}\, x\notin B \right)$ .
Then, $x\in A^c$ and $x\in B^c$ .
Therefore, $\left( A \cup B\right)^c \subseteq A^c \cap B^c$ .

(b) $A^c \cap B^c \subseteq \left( A \cup B\right)^c$
Follow in the reverse order of the proof above.

Therefore, by (a) and (b), $\left( A \cup B\right)^c = A^c \cap B^c$ .

2. $\left( A \cap B\right)^c = A^c \cup B^c$

(a) $\left( A \cap B\right)^c \subseteq A^c \cup B^c$
Let $x\in \left( A \cap B\right)^c$ .
Then, $x\in U$ and $x\notin (A\cap B)$ .
Then, $x\in U$ and $\sim\left(x\in A \,\text{and}\, x\in B\right)$ .
Then, $x\in U$ and $\left(x\notin A \,\text{or}\, x\notin B\right)$ .
Then, $\left( x\in U \,\text{and}\, x\notin A \right)$ or $\left( x\in U \,\text{and}\, x\notin B \right)$ .
Then, $x\in A^c$ or $x\in B^c$ .
Therefore, $\left( A \cap B\right)^c \subseteq A^c \cup B^c$ .

(b) $A^c \cup B^c \subseteq \left( A \cap B\right)^c$
Follow in the reverse order of the proof above.

Therefore, by (a) and (b), $\left( A \cap B\right)^c = A^c \cup B^c$ .

12 Set Theory

Set Operations

License

Share This Book