Algebra of sets

Set-theoretic operations

• $A \cup B$ is the union of $A$ and $B$.
• $A \cup B = \{x:x \in A \vee x \in B\}$.
• $A \cap B$ is the intersection of $A$ and $B$.
• $A \cap B = \{x:x \in A \wedge x \in B \}$.
• $A \setminus B$ is the set difference.
• $A \setminus B = \{x:x\in A \wedge x \notin B\}$.
• $A \bigtriangleup B$ is the symmetric difference.
• $A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)$.

The laws of Boolean logic (associativity, distributivity, idempotence, commutativity, De Morgan's, etc.) also apply to sets, where $\cup$ is equivalent to $\vee$, $\cap$ is equivalent to $\wedge$ and an overline is used to show negation ($\overline{A}$).

Set difference proof

Prove $A \bigtriangleup B = (A\setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$:

1. Let $x \in (A \setminus B) \cup (B \setminus A)$.

   1. Consider the case $x \in A \setminus B$: $x \in A$ and $x \notin B$.
      If $x\in A$ then $x \in A \cup B$. If $x \notin B$ then $x \notin A \cap B$. Combining the two expressions using the definition of $A \setminus B$ gives $x \in (A \cup B) \setminus (A \cap B)$.

   2. The same can be said when $x \in B \setminus A$:
      $x \in B$, $x \notin A$, $x \in A \cup B$, $x \notin A \cap B$, $x \in (A \cup B) \setminus (A \cap B)$.

   This has shown that $(A\setminus B) \cup (B \setminus A) \in (A \cup B) \setminus (A \cap B)$, but not the other way round.

2. Let $x \in (A \cup B) \setminus (A \cap B)$.
   Using the set difference, $x \in (A \cup B)$ and $x \notin (A \cap B)$.
   If $x \in (A \cup B)$, $x \in A$ or $x \in B$. Both can not be true or $A \cap B$ would be true, but $x \notin A \cap B$.
   This means either $x \in A \wedge x \notin B$ or $x \in B \wedge x \notin A$.
   Therefore, $x \in A \setminus B$ or $x \in B \setminus A$ by definition of set difference.
   This has shown that $(A\cup B)\setminus (A \cap B) \in (A \setminus B) \cup (B \setminus A)$.

It has now been shown that both $(A\setminus B) \cup (B \setminus A) \in (A \cup B) \setminus (A \cap B)$ and $(A\cup B)\setminus (A \cap B) \in (A \setminus B) \cup (B \setminus A)$. Therefore the sets are equal.

Expressions with indices

To define multiple sets, where each is the set of integers from $i$, you can use $A_i = \{x \in \mathbb{Z} : x \geq i\}$. To express the union of all of those sets ($A_1 \cup A_2 \cup A_n$), you can use a big $\cup$, similar to series notation: $\displaystyle\bigcup_{i=1}^{n}{A_i}$ and similarly $\displaystyle\bigcap_{i=1}^{n}{A_i}$ for intersection. Similarly to how the sum of natural numbers can be expressed in terms of $n$, the same can be done for sets. Using $A_i = \{x \in \mathbb{Z} : x \geq i\}$ as an example:

The values will change dependent on the definition of $A_i$.

It is also possible to make a general form for infinity:

$$ \begin{aligned} & \bigcup_{i=1}^{\infty} A_i = \{x:x \in A_i \text{ for some } i \in \mathbb{N} \}\\ & \bigcap_{i=1}^{\infty} A_i = \{x:x \in A_i \text{ for all } i \in \mathbb{N} \} \end{aligned} $$

Using $A_i = \{x \in \mathbb{Z} : x \geq i\}$ as an example again:

$$ \begin{aligned} & \bigcup_{i=1}^{\infty} A_i = A_1\\ & \bigcap_{i=1}^{\infty} A_i = \emptyset \end{aligned} $$ The union to infinity is the same as the the union to $n$. The intersection is different, as the set of integers not contained in the set of integers is the empty set.

Power sets and Cartesian products

Power set

The power set is the set of all subsets of a set.

In general, the power set of a set $S$ is denoted $2^S$ and is the set of all subsets of $S$. A power set of a finite set $S$ contains $2^{|S|}$ items.

Cartesian product and ordered pairs

The Cartesian product of two sets, $A \times B$, is the set of all ordered pairs $(a,b)$ where $a \in A$ and $b \in B$: $A \times B = \{(a, b) : a \in A, b \in B\}$.

Take two sets, $A = \{k,l,m\}$ and $B = \{q,r\}$. The Cartesian product of these sets would be $\{(k, q), (k, r), (l, q), (l, r), (m, q), (m, r)\}$ . Note that the first item in the sequences is from $A$ and the second is from $B$. For $B \times A$, the pairs will be swapped.