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 \lnot 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
\(\emptyset\) 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

Powerset

Given a set \(S\), the powerset of \(S\), \(P(S)\), is the set container all the subsets of \(S\).

\[ \begin{flalign} S &= \{a, b\} \\ P(S) &= \{\emptyset , \{a\}, \{b\}, \{a,b\}\} \end{flalign} \] Cadninatily of \(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} \]