Set Theory Reference
Set Theory and Set Operations
Set theory gives a precise language for collections, membership, and the ways groups overlap or combine.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Membership | $x\in A$ means $x$ is an element of $A$. | An element is not the same thing as a subset. |
| Subset | $A\subseteq B$ means every element of $A$ is also in $B$. | The empty set is a subset of every set. |
| Union and intersection | $A\cup B$ collects elements in either set; $A\cap B$ collects elements in both. | The union is inclusive. |
| Complement and difference | $A^c$ contains elements of the universe outside $A$; $A\setminus B$ contains elements of $A$ not in $B$. | State the universe when using complements. |
| Power set | $\mathcal P(A)$ is the set of all subsets of $A$. | A set with $n$ elements has $2^n$ subsets. |
Content Formulas
Cardinality of a Union
$$|A\cup B|=|A|+|B|-|A\cap B|$$
Complement
$$|A^c|=|U|-|A|$$
Power Set Size
$$|\mathcal P(A)|=2^{|A|}$$
De Morgan Laws
$$(A\cup B)^c=A^c\cap B^c,\quad (A\cap B)^c=A^c\cup B^c$$
Set equality means the sets contain exactly the same elements. Order and repeated listing do not matter: $\{1,2,2\}=\{2,1\}$.
Classic Examples
Find a Union and Intersection
Let $A=\{1,2,3,4\}$ and $B=\{3,4,5\}$. Find $A\cup B$ and $A\cap B$.
Solution Steps
- List each element that appears in either set for the union.
- Keep only elements shared by both sets for the intersection.
$$A\cup B=\{1,2,3,4,5\}$$
$$A\cap B=\{3,4\}$$
List a Power Set
Find the power set of $A=\{a,b\}$.
Solution Steps
- List the empty subset, each one-element subset, and the full set.
- Check that a two-element set has four subsets.
$$\mathcal P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}$$
$$|\mathcal P(A)|=2^2=4$$
Count a Union
If $|A|=18$, $|B|=14$, and $|A\cap B|=6$, find $|A\cup B|$.
Solution Steps
- Add the two set sizes.
- Subtract the overlap that was counted twice.
$$|A\cup B|=18+14-6$$
$$|A\cup B|=26$$
Form a Cartesian Product
Let $A=\{1,2\}$ and $B=\{x,y\}$. List $A\times B$.
Solution Steps
- Pair each element of $A$ with each element of $B$.
- Keep the first and second coordinates in order.
$$A\times B=\{(1,x),(1,y),(2,x),(2,y)\}$$
$$|A\times B|=|A||B|=2\cdot2=4$$