Sets and Set Operations

The Foundation of Everything Discrete

A set is an unordered collection of distinct objects, its elements. We write $x \in A$ for "$x$ is in $A$" and $x \notin A$ for "$x$ is not in $A$." Sets are the bedrock of discrete mathematics — numbers, relations, functions, and even logic are all defined in terms of sets. Two features matter: a set has no order ($\{1,2\} = \{2,1\}$) and no duplicates (listing an element twice changes nothing).

Key relationships and special sets:

• $A$ is a subset of $B$ (written $A \subseteq B$) if every element of $A$ is also in $B$.
• The empty set $\emptyset$ has no elements and is a subset of every set.
• The cardinality $|A|$ is the number of elements in $A$.

The operations combine sets into new sets:

• Union $A \cup B$ — elements in $A$ or $B$ (or both).
• Intersection $A \cap B$ — elements in both $A$ and $B$.
• Difference $A \setminus B$ — elements in $A$ but not in $B$.
• Complement $\overline{A}$ — everything (in the universe) not in $A$.

These mirror boolean logic exactly: union is OR, intersection is AND, complement is NOT. So De Morgan's laws hold for sets too: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$. A crucial counting rule is inclusion-exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$ — you add the sizes and subtract the overlap counted twice.

Common pitfall: confusing union with intersection, or forgetting the overlap in inclusion-exclusion. Union collects everything in either set; intersection keeps only what is in both. And $|A \cup B|$ is not simply $|A| + |B|$ — that double-counts the shared elements, so you must subtract $|A \cap B|$.

Two overlapping set circles A and B; the lens overlap flashes in accent as it is subtracted once, illustrating |A ∪ B| = |A| + |B| − |A ∩ B|.

$$|A \cup B| = |A| + |B| - |A \cap B|$$