Sets and Set Operations

A set is simply a collection of things, where all you care about is what's in it and what isn't. It's good for describing groups precisely: "the even numbers," "users who watch dramas," "search results matching both keywords." The symbols look foreign, but each is a one-word idea: $A \cup B$ (everything in $A$ or $B$), $A \cap B$ (only what's in both), $A \setminus B$ (in $A$ but not $B$), $\overline{A}$ (everything outside $A$) and $\mathcal{P}(A)$ (the collection of all possible sub-collections of $A$). That's the whole toolkit, and you'll find you already know it from logic.

Sets are written with braces, $A = \{1, 2, 3\}$, or by a rule, $\{x \in \mathbb{Z} : x > 0\}$. Order and repetition don't matter, since a set only records membership: $\{1, 2\} = \{2, 1, 1\}$. The cardinality $|A|$ is the number of elements, and $\varnothing$ is the empty set.

$A \subseteq B$ means every element of $A$ is in $B$. The power set $\mathcal{P}(A)$ collects all subsets. Why is its size $2^{|A|}$? Building a subset means walking through the elements of $A$ and deciding, for each one, "in or out." That's two choices per element, so $|\mathcal{P}(A)| = 2^{|A|}$.

Now think back to the logic unit. The operations match it exactly: $x \in A \cup B$ means $x \in A \vee x \in B$, $x \in A \cap B$ means $x \in A \wedge x \in B$, and complement is "not." So any law of logic becomes a law about sets for free. De Morgan's laws, for instance, turn into $\overline{A \cup B} = \overline{A} \cap \overline{B}$: being outside "$A$ or $B$" means being outside $A$ and outside $B$.

A common mistake. It's tempting to treat $\varnothing$ and $\{\varnothing\}$ as the same thing, since both look "empty." They aren't: $\varnothing$ has no elements, while $\{\varnothing\}$ has one element (which happens to be the empty set). That's also why the empty set counts as one of the $2^{|A|}$ subsets in the power set.

The Cartesian product $A \times B$ is the set of ordered pairs $(a, b)$, and $|A \times B| = |A| \cdot |B|$, since each of the $|A|$ first entries pairs with each of the $|B|$ second entries.

Database queries combine result sets with exactly these operations (SQL's UNION, INTERSECT and EXCEPT), and so do search filters.