home

# Sets

A set is a well-defined collection of any kind of objects. Order of elements is not defined.

## Notation

Symbol Description Example
$$\{ \cdots \}$$ elements $$A = \{1,2,3\}$$
$$\emptyset$$ empty set $$\emptyset \equiv \{\}$$
$$\in$$ is member of $$1 \in A$$
$$\notin$$ is not member of $$0 \notin A$$
$$\lvert \cdots \rvert$$ cardinality $$\lvert A \rvert = 3$$
$$\subseteq$$ subset $$\{1, 2\} \subseteq A$$
$$\supseteq$$ superset $$\{1,2,3,4\} \supseteq A$$
$$\{ \cdots \vert \cdots \}$$ set builder $$\mathbb Q = \{ \frac n m \lvert n, m \in \mathbb Z , m \neq 0 \}$$

## Operations

Symbol Term Definition
$$\cup$$ union $$A \cup B = \{x \vert x \in A \lor x \in B \}$$
$$\cap$$ intersection $$A \cap B = \{x \vert x \in A \land x \in B \}$$
$$-$$ set difference $$A - B = \{x \vert x \in A \land x \notin B \}$$
$$\oplus$$ symetric difference $$A \oplus B = \{x \vert (x \in A \lor x \in B) \land x \notin A \cap B \}$$
$$\overline{\cdots}$$ complement $$\overline{A} = \mathbb{U} - \mathbb{A}$$

### Special sets

Symbol Description
$$\varnothing$$ empty set
$$\mathbb{N}$$ natural number $$\{1,2,3,4,\ldots\}$$
$$\mathbb{Z}$$ integers $$\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$$
$$\mathbb{Q}$$ rational numbers
$$\mathbb{R}$$ real numbers

## Power set

Given a set $$S$$, the power set of $$S$$, $$\mathcal{P}(S)$$, is the set containing all possible subsets of $$S$$.

\begin{flalign} S &= \{a, b\} \\ \mathcal{P}(S) &= \{\varnothing , \{a\}, \{b\}, \{a,b\}\} \end{flalign} Cardinality of $$\mathcal{P}(S)$$ is always $$2 ^ {\lvert S \rvert}$$.

## Laws

Name Union Intersection
idempotent $$A \cup A = A$$ $$A \cap A = A$$
identity $$A \cup \emptyset = A$$ $$A \cap U = A$$
complement $$A \cup \overline{A} = U$$, $$\overline{U} = \emptyset$$ $$A \cap \overline{A} = \emptyset$$, $$\overline{\emptyset} = U$$
domination $$A \cup U = U$$ $$A \cap \emptyset = \emptyset$$
commutative $$A \cup B = B \cup A$$ $$A \cap B = B \cap A$$
associative $$(A \cup B) \cup C = A \cup (B \cup C)$$ $$(A \cap B) \cap C = A \cap (B \cap C)$$
distributive $$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$ $$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$
De Morgan’s laws $$\overline{A \cup B} = \overline{A} \cap \overline{B}$$ $$\overline{A \cap B} = \overline{A} \cup \overline{B}$$
double complement $$\overline{\overline{A}} = A$$
absorptive $$A \cup (A \cap B) = A$$ $$A \cap (A \cup B) = A$$
set difference $$A - B = A \cap \overline{B}$$

## Equality vs Equivalence

Two sets are equal if they contain the same elements.

Sets of the same cardinality, regardless of the elements they contain, are equivalent.

$\begin{gather} A = \{10, 11, 12\} \\ B = \{12, 11, 10\} \\ C = \{42, 42, 42\} \\ A = B, \quad A \neq C, \quad A \equiv C \end{gather}$