Sets and Set Notation
The language the rest of mathematics is written in: what a set is, the difference between belonging to one and being contained in one, and the operations that build new sets from old. See proving-set-properties for the proof methods that go with these definitions, and functions-on-general-sets for what gets built on top of them.
Writing a set down
Two ways, both used constantly:
- By listing the elements, inside braces: \(\{1,2,3\}\), \(\{a\}\), \(\{\emptyset, \{\emptyset\}\}\). An infinite list gets an ellipsis: \(\{\dots, -2, -1, 0, 1, 2, \dots\}\).
- By a defining condition — set-builder notation: \(\{n \in \mathbb{Z} \mid n \equiv 2 \;(\mathrm{mod}\; 8)\}\), read “the set of integers \(n\) such that \(n \equiv 2\) mod \(8\)”.
Both a vertical bar and a colon are used as the “such that” separator, interchangeably. \(\{n \in \mathbb{Z} \mid n \equiv 2 \;(\mathrm{mod}\; 8)\}\) and \(\{(x,y) \mid x \in \mathbb{R} \text{ and } y \in \mathbb{R}\}\) take the bar; \(f = \{(x,y) \in \mathbb{R} \times \mathbb{R} : y = 2x+1\}\) and \(f^{-1}(B) = \{x \in X : f(x) \in B\}\) take the colon. Read either as “such that”; nothing turns on which one is written.
Two conventions worth naming, because everything below relies on them: sets take capital italic letters (\(A, B, C, S, T, X, Y\)), with \(U\) reserved for the universal set, and elements take lower case (\(x\), \(y\), \(t\), \(n\)). And \(|A|\) denotes the cardinality of \(A\) — the number of elements it has (for infinite sets, where “number of elements” needs care, see cardinality).
“Is an element of” versus “is a subset of”
Warning. Take care with the distinction between is an element of (\(\in\)) and is a subset of (\(\subseteq\)).
This is the single most common source of error in the whole topic, and it is worth being blunt about why: the two relate different kinds of thing.
| Reads | Left-hand side is | Right-hand side is | |
|---|---|---|---|
| \(x \in A\) | \(x\) is an element of \(A\) | an object | a set |
| \(A \subseteq B\) | \(A\) is a subset of \(B\) | a set | a set |
Is \(\mathbb{Z} \in \mathbb{Q}\)? False. The elements of \(\mathbb{Q}\) are rational numbers, and \(\mathbb{Z}\) is not a number — it is a set of numbers. The true statement in the neighbourhood is \(\mathbb{Z} \subseteq \mathbb{Q}\).
The instinct behind the mistake (“but aren’t all integers rational?”) is right; it is the symbol that is wrong. “All integers are rational” is exactly the claim \(\mathbb{Z} \subseteq \mathbb{Q}\).
The same care applies one level down: a single element is not the same as the set containing that element, so \(2 \neq \{2\}\).
Worked: true or false?
| Statement | Why | ||
|---|---|---|---|
| a) | \(4 \in \{4\}\) | True | \(\{4\}\) contains \(4\) as an element |
| b) | \(4 \in \{\{4\}\}\) | False | \(\{\{4\}\}\) does not contain \(4\) as an element — it contains \(\{4\}\) as an element |
| c) | \(\{4\} \in \{2,3,4\}\) | False | \(\{2,3,4\}\) does not contain \(\{4\}\) as an element — it contains \(4\) as an element |
Each false line becomes true if you swap the symbol or the braces, which is the point of the exercise. In (c), \(\{4\} \subseteq \{2,3,4\}\) is true.
The reliable technique: write out the set’s elements and ask whether the left-hand object is literally one of the things in the list. For \(\{\{4\}\}\) that list is a single item, the set \(\{4\}\) — and \(4\) is not on it.
Subsets and proper subsets
A set \(S\) is a subset of a set \(T\), written \(S \subseteq T\), if every element in \(S\) is also in \(T\). Formally, \(\forall x\), if \(x \in S\) then \(x \in T\).
A set \(S\) is a proper subset of \(T\), written \(S \subset T\), if \(S \subseteq T\) and there is an element in \(T\) that is not in \(S\).
So \(\subset\) is \(\subseteq\) plus “and they are not equal” — exactly parallel to \(<\) against \(\leq\) for numbers.
| Holds | Fails | |
|---|---|---|
| \(\subseteq\) | \(\mathbb{Z} \subseteq \mathbb{Q}\), and \(\mathbb{Z} \subseteq \mathbb{Z}\) | |
| \(\subset\) | \(\mathbb{Z} \subset \mathbb{Q}\) | \(\mathbb{Z} \not\subset \mathbb{Z}\) |
A set is always a subset of itself and never a proper subset of itself — that single line is the whole difference between the two symbols.
Figure 1: The four situations the symbols distinguish. An element sits inside a set; a subset is a set inside a set; a proper subset leaves something over; and equality is containment holding both ways at once. The contained set is green and the containing set pale blue, with elements as small blue dots; the red dot is the element that keeps the containment proper.
Proving one set is a subset of another
To prove \(S \subseteq T\), consider an arbitrary element of \(S\) and show it is also in \(T\). That is: suppose \(x \in S\), and prove \(x \in T\).
This is the element method, and it is used so heavily that proving-set-properties treats it in full. The word doing the work is “arbitrary” — you may assume nothing about \(x\) beyond membership of \(S\), which is what makes the one argument cover every element at once.
Worked. Let \(D = \{n \in \mathbb{Z} \mid n \equiv 2 \;(\mathrm{mod}\; 8)\}\) and let \(E\) be the set of even integers, i.e. \(E = \{n \in \mathbb{Z} \mid n \equiv 0 \;(\mathrm{mod}\; 2)\}\). Prove \(D \subseteq E\).
Proof. Let \(x \in D\). Then \(x \equiv 2 \;(\mathrm{mod}\; 8)\), so there exists \(k \in \mathbb{Z}\) such that \[x = 8k + 2 = 2(4k + 1) + 0\] Since \(4k + 1 \in \mathbb{Z}\), we have \(x \equiv 0 \;(\mathrm{mod}\; 2)\), and therefore \(x \in E\). Thus \(D \subseteq E\). \(\blacksquare\)
Rewriting \(8k+2\) as \(2(4k+1)\) is the entire proof — see modular-arithmetic for the definition being applied.
Is \(D \subset E\)? Yes. We have \(D \subseteq E\), and \(4 \in E\) while \(4 \notin D\) (since \(4 \not\equiv 2 \bmod 8\)), so the containment is proper. Note that upgrading \(\subseteq\) to \(\subset\) needs one witness, not a general argument.
When are two sets equal?
For sets \(S\) and \(T\), \(S = T\) means \(\forall x\), \(x \in S\) if and only if \(x \in T\).
Recall that \(S \subseteq T\) means \(\forall x\), if \(x \in S\) then \(x \in T\). Since \(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\), it follows that
\[S = T \quad\text{is logically equivalent to}\quad (S \subseteq T) \land (T \subseteq S)\]
So to prove two sets are equal, do two separate proofs:
- Suppose \(x \in S\), and prove \(x \in T\). This shows \(S \subseteq T\).
- Suppose \(x \in T\), and prove \(x \in S\). This shows \(T \subseteq S\).
Together these give \(S = T\). This is not a convention but a consequence — the double containment argument is just the biconditional law of logical-equivalence-laws read through the definition of \(\subseteq\), which is why “prove both directions” is never optional.
The empty set
\(\emptyset = \{\;\}\) — the set with no elements.
Why is \(\emptyset \subseteq A\) for every set \(A\)? Because “\(\forall x\), if \(x \in \emptyset\) then \(x \in A\)” is true for every set \(A\). The hypothesis \(x \in \emptyset\) is never satisfied, and a conditional with a false hypothesis is true — so the statement holds vacuously. See conditional-statements for that truth-table row, which is doing all the work here.
Do not confuse this with \(\emptyset \in A\). Some sets do contain the empty set as an element; many do not. \(\emptyset \subseteq A\) is a theorem about every set; \(\emptyset \in A\) is a claim about one particular set that usually fails.
Why is \(A \subseteq A\) for every set \(A\)? Because “\(\forall x\), if \(x \in A\) then \(x \in A\)” is true for every set \(A\) — this one for the opposite reason, that the conclusion simply restates the hypothesis.
There is only one empty set
Lemma. There is only one empty set.
Proof (by contradiction). Suppose \(\emptyset_1\) and \(\emptyset_2\) are distinct sets each having no elements, so \(\emptyset_1 \neq \emptyset_2\). Since \(\emptyset_1\) has no elements, it is a subset of \(\emptyset_2\); that is, \(\emptyset_1 \subseteq \emptyset_2\). Also, since \(\emptyset_2\) has no elements, \(\emptyset_2 \subseteq \emptyset_1\). Thus \(\emptyset_1 = \emptyset_2\) by definition of set equality — contradicting the supposition. \(\blacksquare\)
This is why we say the empty set and write a single symbol for it. The proof is a neat demonstration of the double-containment criterion doing real work: both containments come free from vacuous truth, and equality falls out.
Unions and intersections
\[A \cup B = \{x \mid x \in A \text{ or } x \in B\} \qquad\qquad A \cap B = \{x \mid x \in A \text{ and } x \in B\}\]
Figure 2: The four operations as shaded regions. Union takes everything in either circle, intersection only the overlap, difference removes B from A, and the complement is everything in the universe outside A — which is why a complement is only meaningful once the universe U is fixed. The enclosing rectangle is that universe.
Worked. Let \(A_1 = \{1,2,3\}\), \(A_2 = \{1,2,4\}\) and \(A_3 = \{3,4,5\}\).
\[A_1 \cup A_2 = \{1,2,3,4\} \qquad A_1 \cap A_2 = \{1,2\} \qquad A_1 \cap A_3 = \{3\} \qquad A_2 \cap A_3 = \{4\}\]
Indexed over all three:
\[\bigcup_{i=1}^{3} A_i = A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5\} \qquad\qquad \bigcap_{i=1}^{3} A_i = (A_1 \cap A_2) \cap A_3 = \{1,2\} \cap \{3,4,5\} = \emptyset\]
Worth noticing: the three sets intersect pairwise in a non-empty set every time, and yet the triple intersection is empty. Pairwise overlap does not survive to the whole family, so an indexed intersection has to be computed, not inferred.
Indexed families
\[\bigcup_{i \in I} A_i = \{x \mid x \in A_i \text{ for \textbf{at least one} } i \in I\} \qquad \bigcap_{i \in I} A_i = \{x \mid x \in A_i \text{ for \textbf{every} } i \in I\}\]
These extend to infinite index sets unchanged, which is where they earn their keep.
Worked, over \(i = 0, 1, 2, \dots\):
\[\bigcup_{i=0}^{\infty} \{i, -i\} = \{0\} \cup \{1,-1\} \cup \{2,-2\} \cup \cdots = \{\dots, -2, -1, 0, 1, 2, \dots\} = \mathbb{Z}\]
\[\bigcap_{i=0}^{\infty} [-i,\, i] = \{0\}\]
recalling the interval notation \([a,b] = \{x \in \mathbb{R} \mid a \leq x \leq b\}\).
The intersection is the interesting one. The intervals grow as \(i\) increases, so the intersection is pinned by the smallest of them, the \(i = 0\) term \([0,0] = \{0\}\). Every larger interval contains \(0\), so nothing is lost, and nothing else survives.
Figure 3: An intersection over an increasing family is decided by its smallest member. Each interval contains the one below it, so the only real number lying in all of them is the single point the innermost interval contains. The intervals sit above the number line, with a filled dot at each closed endpoint.
Set difference and complement
\[A - B = \{x \mid x \in A \text{ and } x \notin B\}\]
Both are drawn in Figure 2 above.
The backslash and the minus sign mean the same thing: \(A - B\) can equally be written \(A \setminus B\). Different textbooks pick different ones; there is no distinction to learn.
The complement \(A^{c}\) is the set difference from the universal set \(U\) under discussion: \(A^{c} = U - A\). It is only meaningful once \(U\) is fixed, so a complement always sits inside a stated universe.
The power set
\(\mathcal{P}(A)\) is the set of all subsets of \(A\).
Worked. Let \(S = \{1,2,3\}\). Then
\[\mathcal{P}(S) = \big\{\, \emptyset,\; \{1\},\; \{2\},\; \{3\},\; \{1,2\},\; \{1,3\},\; \{2,3\},\; \{1,2,3\} \,\big\}\]
Note that the elements of \(\mathcal{P}(S)\) are sets, which resets the \(\in\) / \(\subseteq\) trap one level up:
| Statement | Why | |
|---|---|---|
| \(\{1,2\} \in \mathcal{P}(S)\) | True | \(\{1,2\}\) is one of the eight things listed |
| \(\{1,2\} \subseteq \mathcal{P}(S)\) | False | that would need \(1\) and \(2\) themselves to be elements of \(\mathcal{P}(S)\), i.e. to be subsets of \(S\) — and they are numbers, not sets |
| \(\big\{\{1,2\}\big\} \subseteq \mathcal{P}(S)\) | True | the one element it has, \(\{1,2\}\), is in \(\mathcal{P}(S)\) |
Also worth recording as a standing fact: since \(\emptyset \subseteq A\) for every set \(A\), it follows that \(\emptyset \in \mathcal{P}(A)\) for every set \(A\). Every power set is non-empty, including \(\mathcal{P}(\emptyset)\).
Fact. If \(T\) is a finite set with \(n\) elements, then \(|\mathcal{P}(T)| = 2^{n}\).
The finiteness matters — the count is meaningless otherwise. The \(2^n\) comes from building a subset by making \(n\) independent in/out choices. Sorting the same subsets by size instead gives \(\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n\) (binomial-coefficients).
Worked: is \(\{1, 3, -1\} \subset \mathcal{P}(\mathbb{Z})\)?
False, and the reasoning is the \(\in\)/\(\subseteq\) distinction again, run carefully:
- \(1, 3, -1 \in \mathbb{Z}\), so \(\{1,3,-1\} \subseteq \mathbb{Z}\).
- Therefore \(\{1,3,-1\} \in \mathcal{P}(\mathbb{Z})\) — it is one of the subsets of \(\mathbb{Z}\), hence an element of the power set.
- So \(\{1,3,-1\} \not\subset \mathcal{P}(\mathbb{Z})\): for that, its elements \(1\), \(3\) and \(-1\) would have to be elements of \(\mathcal{P}(\mathbb{Z})\), i.e. subsets of \(\mathbb{Z}\) — and they are integers, not sets.
The statement is off by exactly one level, which is the characteristic failure mode with power sets.
Worked: power sets of power sets
Building up from the empty set, with the \(2^n\) fact as a running check:
| Value | \(|\,\cdot\,|\) of the input | Check | |
|---|---|---|---|
| \(\mathcal{P}(\{a\})\) | \(\big\{\emptyset,\; \{a\}\big\}\) | \(|\{a\}| = 1\) | \(2^1 = 2\) \(\checkmark\) |
| \(\mathcal{P}(\emptyset)\) | \(\big\{\emptyset\big\}\) | \(|\emptyset| = 0\) | \(2^0 = 1\) \(\checkmark\) |
| \(\mathcal{P}(\mathcal{P}(\emptyset)) = \mathcal{P}(\{\emptyset\})\) | \(\big\{\emptyset,\; \{\emptyset\}\big\}\) | \(|\{\emptyset\}| = 1\) | \(2^1 = 2\) \(\checkmark\) |
| \(\mathcal{P}(\mathcal{P}(\mathcal{P}(\emptyset))) = \mathcal{P}\big(\{\emptyset, \{\emptyset\}\}\big)\) | \(\big\{\emptyset,\; \{\emptyset\},\; \{\{\emptyset\}\},\; \{\emptyset, \{\emptyset\}\}\big\}\) | \(\big|\{\emptyset,\{\emptyset\}\}\big| = 2\) | \(2^2 = 4\) \(\checkmark\) |
\(\mathcal{P}(\emptyset) = \{\emptyset\}\) is the line to get right: the empty set has exactly one subset — itself — so its power set has one element and is not empty. Counting the elements at each stage and checking against \(2^n\) is the cheapest way to catch a dropped or duplicated brace.
Cartesian products
\[A \times B = \{(a,b) \mid a \in A \text{ and } b \in B\}\]
the set of ordered pairs with first coordinate from \(A\) and second from \(B\).
Worked. \(A_1 = \{1,2\}\), \(A_2 = \{3,4,5\}\), \(A_3 = \{6\}\).
\[A_1 \times A_2 = \{(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\}\]
\[A_1 \times A_2 \times A_3 = \{(1,3,6), (1,4,6), (1,5,6), (2,3,6), (2,4,6), (2,5,6)\}\]
Figure 4: A Cartesian product laid out as a grid: one row per element of the first set, one column per element of the second, one ordered pair at every crossing. The rectangular shape is the counting fact — the number of pairs is the product of the two sizes.
Worked. Let \(S = \{a,b,c\}\) and \(T = \{c,d\}\).
- \((d,c) \notin S \times T\), since \(d \notin S\) — the order matters, and \(d\) is disqualified as a first coordinate.
- \((c,d) \in S \times T\), since \(c \in S\) and \(d \in T\).
- \(S \times T\) contains \(3 \times 2 = 6\) elements.
The familiar case is \(\mathbb{R} \times \mathbb{R} = \{(x,y) \mid x \in \mathbb{R} \text{ and } y \in \mathbb{R}\}\), usually written \(\mathbb{R}^2\) — the plane is a Cartesian product, which is where the name comes from.
Two facts:
- If \(A = \emptyset\) or \(B = \emptyset\) then \(A \times B = \emptyset\) — there is no way to choose a coordinate from an empty set.
- For finite sets, \(|A_1 \times A_2 \times \cdots \times A_n| = |A_1| \cdot |A_2| \cdots |A_n|\).
Notation clash to be aware of. \((a,b)\) can mean an ordered pair, and \((a,b)\) can also mean an open interval — the real numbers \(x\) with \(a < x < b\). Nothing in the symbols distinguishes them; only the context does.
Partitions
A finite or infinite collection of non-empty sets \(\{A_1, A_2, A_3, \dots\}\) is a partition of a set \(A\) if and only if \[A = A_1 \cup A_2 \cup A_3 \cup \cdots \qquad\text{and}\qquad A_i \cap A_j = \emptyset \text{ for each } i, j \geq 1,\; i \neq j\]
Three conditions, all of which are checkable and all of which get tested: the pieces are non-empty, they cover \(A\), and they are pairwise disjoint.
Figure 5: A partition cuts a set into non-empty pieces that cover it with no overlap — every element lands in exactly one piece. Failing any one of the three conditions is enough to disqualify a collection. On the left is a partition: separate closed curves, one per piece, each holding its elements as dots. On the right, two pieces share an element, so the collection is not a partition.
Examples over \(\mathbb{Z}\):
- \(\{E, O\}\), where \(E\) is the even integers and \(O\) the odd integers, is a partition of \(\mathbb{Z}\).
- \(\big\{\{0\},\; \mathbb{Z}^{+},\; \mathbb{Z}^{-}\big\}\) is another partition of \(\mathbb{Z}\) — a set can be partitioned in many ways.
Worked: a collection that fails
Let \(S = \{x \in \mathbb{Z} \mid x \equiv 1 \;(\mathrm{mod}\; 3)\}\), let \(T = \{x \in \mathbb{Z} \mid x \equiv 2 \;(\mathrm{mod}\; 4)\}\), and let \(R = S \cup T\). Is \(\{S, T\}\) a partition of \(R\)?
No. The covering condition holds by construction — \(R = S \cup T\) is how \(R\) was defined. But disjointness fails:
\[10 = 3(3) + 1 \;\Rightarrow\; 10 \equiv 1 \;(\mathrm{mod}\; 3) \;\Rightarrow\; 10 \in S\] \[10 = 4(2) + 2 \;\Rightarrow\; 10 \equiv 2 \;(\mathrm{mod}\; 4) \;\Rightarrow\; 10 \in T\]
so \(10 \in S \cap T\) and \(S \cap T \neq \emptyset\). Therefore \(\{S,T\}\) is not a partition of \(R\).
A single witness settles it — disjointness is a universal claim, so one counterexample is a complete disproof.
Worked: two partitions of \(\mathbb{Z} \times \mathbb{Z}\)
Any rule that sorts every pair into exactly one bucket works. Two independent ways:
By the sign of the first coordinate. \[P = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a \geq 0\} \qquad N = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a < 0\}\] \(\{N, P\}\) is a partition of \(\mathbb{Z} \times \mathbb{Z}\) — every integer \(a\) is either \(\geq 0\) or \(< 0\), never both.
By the parity of the second coordinate. \[E = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid b \equiv 0 \;(\mathrm{mod}\; 2)\} \qquad O = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid b \equiv 1 \;(\mathrm{mod}\; 2)\}\] \(\{E, O\}\) is another partition of \(\mathbb{Z} \times \mathbb{Z}\).
The recipe generalises: take any property that every element either has or lacks, and the two resulting sets partition the whole — provided neither comes out empty. That connection is made exact by equivalence relations: every partition is the set of classes of one, and the other way round (equivalence-classes-and-partitions).
See also
- proving-set-properties — the element method, the set identities, and proofs about these operations
- functions-on-general-sets — functions defined as subsets of a Cartesian product
- equivalence-classes-and-partitions — partitions as the classes of an equivalence relation
- modular-arithmetic — the congruence sets used throughout the worked examples
- counting-principles · counting-selections — \(|A \times B| = |A| \times |B|\) as the multiplication rule, and \(\binom{n}{r}\), the number of \(r\)-element subsets of an \(n\)-element set
- inclusion-exclusion · probability — the size of a union of sets that overlap, with De Morgan’s law for “neither”, and events as subsets of a sample space
- pigeonhole-principle — a partition as the set of pigeonholes
- conditional-statements · logical-equivalence-laws — vacuous truth, and the biconditional behind set equality
- 2026-09-03-set-theory-definitions — Lecture 17
- practice-problems — §21 Set Theory Definitions, with full worked solutions
- practice-problems — §22 More Definitions and Examples of Sets