1. What is a set
A set is a collection of things — any collection, with no order and no repeats. The 50 US states form a set. The prime numbers form a set. The collection $\{2, 5, 17\}$ is a set. The things inside a set are called its elements (you'll also hear them called members — same thing, different word). What makes a set a set is just this: which things are inside, and which aren't.
Two properties matter. First, membership is sharp: for any object you might name, the question "is this in the set?" has a yes-or-no answer — no maybes, no fuzz. Second, each element shows up once. A set isn't a list, and it isn't a multiset. Writing $\{1, 2, 1\}$ doesn't give you a set with three things in it — it gives you the same two-element set as $\{1, 2\}$.
With that intuition in hand, here's how Cantor — the mathematician who first put the idea on paper — stated it formally:
A set is a collection of definite, distinct objects, considered as a single entity. The objects of the set are its elements.
The two technical words map onto what we just said: definite is the sharp yes-or-no membership, and distinct is the no-repeats rule.
That's "naive" set theory: a working vocabulary that almost every mathematician uses without ever invoking a formal axiom. It's powerful enough for almost everything you'll do day to day. It also, as we'll see at the end, has a famous landmine — but for now, treat sets as collections, the way Cantor did.
A set is fully specified by its membership and nothing else. No order, no multiplicity, no "first element," no internal structure. Two sets are the same set exactly when they have the same elements — that's it.
2. Two ways to write a set
There are two standard ways to describe a set: list its elements, or describe them by a property.
Roster (listing) notation
Enumerate the elements inside braces, separated by commas:
$$ \{2, 3, 5, 7\}, \qquad \{\text{red}, \text{green}, \text{blue}\}, \qquad \{\,\} = \varnothing. $$The roster is concrete and unambiguous, but it only scales up to about a handful of elements. Beyond that you reach for the second form.
Set-builder notation
Describe the set by a defining property:
$$ \{\, x \in A \mid P(x) \,\} \quad = \quad \text{"the elements } x \text{ of } A \text{ for which } P(x) \text{ holds."} $$Read the bar as "such that." So $\{\, n \in \mathbb{N} \mid n \text{ is prime} \,\}$ is "the natural numbers $n$ such that $n$ is prime," and $\{\, x \in \mathbb{Z} \mid x^2 < 10 \,\} = \{-3, -2, -1, 0, 1, 2, 3\}$.
The form $\{\, x \mid P(x) \,\}$ — with no domain $A$ — is informally tolerated but technically illegal. Letting any property carve a set out of the entire universe is exactly the move that produces Russell's paradox (§9). When in doubt, name the domain you're carving from.
3. Membership, subsets, and equality
One primitive relation underlies everything: belonging. We write $x \in A$ to mean "$x$ is an element of $A$," and $x \notin A$ for its negation. From this single relation, all the other structural ideas follow.
Subset
$A$ is a subset of $B$ when every element of $A$ is also an element of $B$. Formally: $\;A \subseteq B \;\iff\; \forall x \,(x \in A \to x \in B).$
If additionally $A \neq B$, we call $A$ a proper subset, written $A \subsetneq B$. The reverse relation, $A \supseteq B$, means "$A$ is a superset of $B$" — just $B \subseteq A$ read the other way.
Equality by extensionality
Two sets are equal precisely when they have the same elements. This is the axiom of extensionality, and it's the deep reason sets ignore order and repetition:
$$ A = B \;\iff\; A \subseteq B \;\text{ and }\; B \subseteq A. $$This gives the standard recipe for proving set equality: prove both inclusions. Take an arbitrary $x \in A$ and show $x \in B$; then take an arbitrary $x \in B$ and show $x \in A$. This double-containment argument is the most common move in elementary set theory.
Membership and subset are different kinds of statement. $3 \in \{1, 2, 3\}$ is true; $\{3\} \subseteq \{1, 2, 3\}$ is true; but $3 \subseteq \{1, 2, 3\}$ is ill-typed (3 isn't a set), and $\{3\} \in \{1, 2, 3\}$ is false (the set $\{3\}$ is not one of the elements 1, 2, 3). Reading membership and inclusion as the same relation is the single most common beginner error.
4. The empty set, the universe, the power set
The empty set $\varnothing$
The empty set, written $\varnothing$ or $\{\,\}$, is the unique set with no elements. Two facts about it are worth saying out loud, because both are routinely misread:
- $\varnothing \subseteq A$ for every set $A$ — vacuously, because there's no element of $\varnothing$ that fails to be in $A$.
- $\varnothing \neq \{\varnothing\}$. The empty set has zero elements. The set $\{\varnothing\}$ has one element — namely, the empty set. They are as different as an empty box and a box containing an empty box.
The universal set $U$
In any particular discussion there is a fixed background set called the universe, written $U$, that contains all the objects under consideration. When you're doing number theory, $U$ might be $\mathbb{Z}$; in probability, $U$ is the sample space; in a Venn diagram, $U$ is the enclosing rectangle. The universe is what gives "everything not in $A$" — the complement — a definite meaning.
The power set $\mathcal{P}(A)$
The power set of $A$ is the set of all subsets of $A$: $\;\mathcal{P}(A) = \{\, S \mid S \subseteq A \,\}.$ For finite $A$, $|\mathcal{P}(A)| = 2^{|A|}$.
For $A = \{a, b\}$, listing systematically by size:
$$ \mathcal{P}(\{a, b\}) = \{\, \varnothing,\; \{a\},\; \{b\},\; \{a, b\} \,\} \quad (\text{four subsets} = 2^2). $$The doubling comes from a simple counting argument: building a subset means making one yes-or-no decision per element, and $n$ binary choices give $2^n$ outcomes. The power set of $\varnothing$ is $\{\varnothing\}$ — one subset, the empty one. Note that $\mathcal{P}(\varnothing)$ has one element, while $\varnothing$ has none.
5. Cartesian product: ordered pairs
Sets ignore order, but lots of mathematics needs ordered data: the point $(3, 5)$ in the plane is not the same as $(5, 3)$. The Cartesian product is how we build ordered structure on top of unordered sets.
$A \times B = \{\, (a, b) \mid a \in A,\; b \in B \,\}$ — the set of all ordered pairs with first entry from $A$ and second from $B$. For finite sets, $|A \times B| = |A| \cdot |B|$.
With $A = \{1, 2\}$ and $B = \{x, y, z\}$:
$$ A \times B = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\}, \qquad |A \times B| = 2 \cdot 3 = 6. $$The Cartesian plane $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ is the most familiar instance: a point is an ordered pair of real numbers. Higher products $A_1 \times A_2 \times \cdots \times A_n$ produce $n$-tuples and underpin everything from coordinate geometry to database tables to function graphs (which we'll meet in the next topic).
$A \times B$ and $B \times A$ are different sets unless $A = B$, because $(a, b) \neq (b, a)$ in general. Order matters inside an ordered pair, even though it doesn't matter inside a set.
6. The five operations
Fix a universe $U$ and let $A, B \subseteq U$. The five operations below are exactly the set-theoretic shadows of the logical connectives — union is or, intersection is and, complement is not. Hold that correspondence in your head and the algebraic laws stop looking like memorization.
| Operation | Definition | Logical reading |
|---|---|---|
| Union $A \cup B$ | $\{\, x \mid x \in A \;\text{or}\; x \in B \,\}$ | $x \in A \,\vee\, x \in B$ |
| Intersection $A \cap B$ | $\{\, x \mid x \in A \;\text{and}\; x \in B \,\}$ | $x \in A \,\wedge\, x \in B$ |
| Difference $A \setminus B$ | $\{\, x \mid x \in A \;\text{and}\; x \notin B \,\}$ | $x \in A \,\wedge\, x \notin B$ |
| Complement $A^c$ | $U \setminus A = \{\, x \in U \mid x \notin A \,\}$ | $\neg(x \in A)$ |
| Symmetric difference $A \triangle B$ | $(A \setminus B) \cup (B \setminus A)$ | $x \in A \,\oplus\, x \in B$ (xor) |
A concrete instance to fix the picture. Let $A = \{1, 2, 3\}$, $B = \{3, 4, 5\}$, and $U = \{1, 2, 3, 4, 5, 6\}$. Then:
$$ \begin{aligned} A \cup B &= \{1, 2, 3, 4, 5\} \\ A \cap B &= \{3\} \\ A \setminus B &= \{1, 2\} \\ B \setminus A &= \{4, 5\} \\ A^c &= \{4, 5, 6\} \\ A \triangle B &= \{1, 2, 4, 5\} \end{aligned} $$Difference is asymmetric: $A \setminus B \neq B \setminus A$. The symmetric difference $A \triangle B$ is the symmetric version — the elements in exactly one of the two sets. It's the set-theoretic mirror of exclusive-or.
$A^c$ is meaningless on its own — "everything not in $A$" depends entirely on what "everything" is. Changing the universe changes the complement. State $U$ before you take a complement.
7. Venn diagrams
For two or three sets, the operations have a tidy pictorial form. Each set is a region; the universe is the surrounding rectangle. The shaded part is the set the picture stands for.
For three sets the picture has eight regions — one for each pattern of in/out across the three circles. That mirrors $2^3 = 8$ rows of a truth table over three propositions, which is no coincidence:
8. Algebraic laws and De Morgan
The five operations satisfy a clean algebra. Most of these laws have direct twins in propositional logic — they're the same statements, with $\cup$ in place of $\vee$, $\cap$ in place of $\wedge$, and complement in place of negation.
| Name | Statement |
|---|---|
| Commutative | $A \cup B = B \cup A$, $\;A \cap B = B \cap A$ |
| Associative | $(A \cup B) \cup C = A \cup (B \cup C)$, similarly with $\cap$ |
| Distributive | $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and dual |
| Identity | $A \cup \varnothing = A$, $\;A \cap U = A$ |
| Domination | $A \cup U = U$, $\;A \cap \varnothing = \varnothing$ |
| Idempotence | $A \cup A = A$, $\;A \cap A = A$ |
| Double complement | $(A^c)^c = A$ |
| Inclusion–exclusion | $|A \cup B| = |A| + |B| - |A \cap B|$ |
De Morgan's laws for sets
The pair worth memorizing — and worth understanding rather than memorizing — is De Morgan's laws. They tell you exactly how complement interacts with union and intersection:
$$ (A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c. $$In words: the complement of a union is the intersection of complements; the complement of an intersection is the union of complements. Complement swaps $\cup$ and $\cap$. The logical version you've already met says exactly the same thing for $\neg, \vee, \wedge$ — and the proof is, in essence, the same proof:
$$ x \in (A \cup B)^c \;\iff\; \neg(x \in A \vee x \in B) \;\iff\; \neg(x \in A) \wedge \neg(x \in B) \;\iff\; x \in A^c \cap B^c. $$That mechanical translation — chase an element, push the logical equivalence through, translate back — is the bread-and-butter technique for proving any set identity. Combine it with double-containment from §3 and you can settle most exam-style set equalities in a few lines.
Sets-under-these-operations and propositions-under-these-connectives are two faces of the same algebraic structure: a Boolean algebra. That's not a coincidence to be tolerated; it's the structural fact that makes set theory and logic interchangeable for most foundational purposes — and the reason digital-logic engineers reason with Venn diagrams.
9. Russell's paradox: why this had to be redone
Cantor's definition feels innocent — "a collection of definite, distinct objects" — and the rules in §2 let you build sets out of any property you like. It was the most natural way to ground mathematics, and around 1900 Gottlob Frege was finishing a multi-volume work doing exactly that.
Then Bertrand Russell asked a question.
Most sets aren't elements of themselves. The set of all integers is not an integer, so it doesn't belong to itself. The set of all triangles isn't a triangle, so it doesn't belong to itself. Russell asked: what about the set of all sets that don't belong to themselves?
$$ R = \{\, x \mid x \notin x \,\}. $$Now ask: is $R$ an element of $R$?
- If $R \in R$, then $R$ satisfies the defining property of $R$, namely $R \notin R$. Contradiction.
- If $R \notin R$, then $R$ satisfies the defining property, so $R \in R$. Contradiction.
Either way you get a contradiction. There is no consistent answer. Russell mailed the paradox to Frege in 1902, just as Frege was sending volume II of his Grundgesetze to press. Frege wrote a stunned appendix conceding that the foundation of his life's work was broken.
The culprit is the assumption that any property defines a set — "unrestricted comprehension." Russell's $R$ shows that this principle is inconsistent. The fix, due to Zermelo in 1908 and refined by Fraenkel and Skolem, is to restrict comprehension to separation: a property carves a subset out of an existing set, not a set out of the whole universe. So $\{\, x \in A \mid P(x) \,\}$ is legal; $\{\, x \mid P(x) \,\}$ across all objects is not.
That refined theory is called ZFC (Zermelo–Fraenkel with Choice) and is the standard modern foundation of mathematics. We don't need its axioms for anything in this topic — they're a separate study — but it's worth knowing they exist, and worth knowing why: naive set theory works for the day-to-day, but it's not safe at the boundary. Always specify a domain for your set-builders, and you stay on the safe side of Russell's line.
10. Common pitfalls
$\{1, 2\} \in \{\{1, 2\}, 3\}$ is true (the set $\{1, 2\}$ is an element of the outer set), but $\{1, 2\} \subseteq \{\{1, 2\}, 3\}$ is false — for that you'd need both $1$ and $2$ to be elements of the outer set, and only $\{1, 2\}$ and $3$ are. Re-read the surrounding braces carefully.
Zero elements versus one element. $|\varnothing| = 0$; $|\{\varnothing\}| = 1$. The latter has exactly one element, which happens to be the empty set.
True only when $A$ and $B$ are disjoint. Otherwise you've double-counted the intersection. The correct formula is inclusion–exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$.
$A^c$ has no meaning until you fix $U$. If you change the universe — say from $\mathbb{N}$ to $\mathbb{Z}$ — the complement changes with it. State the universe whenever you take a complement.
$(A \cup B)^c = A^c \cap B^c$, not $A^c \cup B^c$. Complement swaps the connectives; it doesn't preserve them. Saying it out loud — "complement of a union is the intersection of complements" — is the easiest sanity check.
$\{\, x \mid P(x) \,\}$ with no domain is the move that produces Russell's paradox. Always anchor the construction in an existing set: $\{\, x \in A \mid P(x) \,\}$.
11. Worked examples
Each example uses one canonical move from above. Try it yourself before opening the solution.
Example 1 · List the power set of $\{a, b, c\}$.
Enumerate systematically by subset size: size 0, size 1, size 2, size 3.
$$ \mathcal{P}(\{a, b, c\}) = \{\, \varnothing,\; \{a\},\; \{b\},\; \{c\},\; \{a, b\},\; \{a, c\},\; \{b, c\},\; \{a, b, c\} \,\}. $$Eight subsets, as expected from $2^3 = 8$.
Example 2 · With $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5, 6\}$, $U = \{1, \ldots, 8\}$, compute every operation.
Work through each definition.
$$ \begin{aligned} A \cup B &= \{1, 2, 3, 4, 5, 6\} \\ A \cap B &= \{3, 4\} \\ A \setminus B &= \{1, 2\} \\ B \setminus A &= \{5, 6\} \\ A \triangle B &= \{1, 2, 5, 6\} \\ A^c &= \{5, 6, 7, 8\} \\ B^c &= \{1, 2, 7, 8\} \end{aligned} $$Quick check of inclusion–exclusion: $|A| + |B| - |A \cap B| = 4 + 4 - 2 = 6 = |A \cup B|$. ✓
Example 3 · Prove $A \subseteq B \;\iff\; A \cap B = A$.
Two directions.
($\Rightarrow$) Assume $A \subseteq B$. Show $A \cap B = A$ by double containment. The inclusion $A \cap B \subseteq A$ is built into the definition of intersection. For $A \subseteq A \cap B$, take $x \in A$; since $A \subseteq B$ we have $x \in B$, so $x \in A$ and $x \in B$, hence $x \in A \cap B$.
($\Leftarrow$) Assume $A \cap B = A$. Take any $x \in A$. Then $x \in A \cap B$ (by the assumed equality), so in particular $x \in B$. Hence $A \subseteq B$.
Example 4 · Prove the De Morgan identity $(A \cap B)^c = A^c \cup B^c$ by element-chasing.
Show both inclusions at once with logical equivalences:
$$ \begin{aligned} x \in (A \cap B)^c &\iff x \notin A \cap B \\ &\iff \neg(x \in A \;\wedge\; x \in B) \\ &\iff \neg(x \in A) \;\vee\; \neg(x \in B) \\ &\iff x \in A^c \;\vee\; x \in B^c \\ &\iff x \in A^c \cup B^c. \end{aligned} $$Because every step is an "iff," both containments are established simultaneously. The middle step is the logical De Morgan law — the engine driving the set-theoretic version.
Example 5 · A tea-and-coffee survey. 40 people drink tea, 30 drink coffee, 12 drink both. How many drink at least one?
Let $T$ be the set of tea-drinkers and $C$ the set of coffee-drinkers. We want $|T \cup C|$. By inclusion–exclusion:
$$ |T \cup C| = |T| + |C| - |T \cap C| = 40 + 30 - 12 = 58. $$Adding $40 + 30$ counted the 12 dual-drinkers twice; subtracting $|T \cap C|$ removes the double count.
Example 6 · Decide whether $\{2\} \in \mathcal{P}(\{1, 2, 3\})$ and whether $\{2\} \subseteq \mathcal{P}(\{1, 2, 3\})$.
$\mathcal{P}(\{1, 2, 3\}) = \{\varnothing, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$.
The set $\{2\}$ appears as one of the listed elements, so $\{2\} \in \mathcal{P}(\{1, 2, 3\})$ is true.
For $\{2\} \subseteq \mathcal{P}(\{1, 2, 3\})$ to hold, every element of $\{2\}$ — that is, the number $2$ — would need to be an element of the power set. But $2$ is a number, not a set, and the elements of $\mathcal{P}(\{1, 2, 3\})$ are sets. So $2 \notin \mathcal{P}(\{1, 2, 3\})$, and the subset claim is false.
This is the cleanest example of why $\in$ and $\subseteq$ must be distinguished.