Lecture 17 — Set Theory Definitions and Examples
Pre-work: Video 021 (Set Theory Definitions) and Video 022 (More definitions and examples of sets). See sets-and-set-notation for the reference material — every definition below, with the worked examples and the diagrams.
Learning goals
- Understand the distinction between “is an element of” \(x \in A\) and “is a subset of” \(A \subseteq B\).
- Be comfortable with notation for sets including \[x \in A, \quad A \subseteq B, \quad A \subset B, \quad A \cap B, \quad A \cup B, \quad A - B, \quad A^{c}, \quad \mathcal{P}(A), \quad A \times B\]
Element, subset, proper subset
What is the difference between “is a subset of” \(\subseteq\) and “is a proper subset of” \(\subset\)? A four-way comparison settles it:
| \(\subseteq\) | \(\subset\) | |
|---|---|---|
| \(\mathbb{Z}\) against \(\mathbb{R}\) | \(\mathbb{Z} \subseteq \mathbb{R}\) ✓ | \(\mathbb{Z} \subset \mathbb{R}\) ✓ |
| \(\mathbb{Z}\) against itself | \(\mathbb{Z} \subseteq \mathbb{Z}\) ✓ | \(\mathbb{Z} \not\subset \mathbb{Z}\) ✗ |
A set is always a subset of itself, and never a proper subset of itself. That single row is the entire difference — exactly parallel to \(\leq\) against \(<\).
What is the difference between “is a subset of” and “is an element of”? A concrete universe shows it better than a symbol:
Let \(L := \{\text{everyone in the lecture theatre}\}\), and let \(m :=\) me and \(y :=\) you.
Four memberships hold: \(m \in L\), \(y \in L\), \(\{m\} \subseteq L\), \(\{m,y\} \subseteq L\). The two braced objects are sets. A person is an element; a group of people is a subset. One is a person, the other is a collection of people. Just as \(2 \neq \{2\}\) (below), \(m \neq \{m\}\) — a person is not a group containing one person.
Figure 1: The lecture theatre example drawn out. A person in the room is an element of L; any group of people in the room is a subset of L. The two symbols relate different kinds of thing, which is why m and {m} are not the same object even though the group has exactly one member.
The other people in the room are drawn into Figure 1 for a reason: \(\{m,y\}\) is a subset of \(L\), not the subset. Every group you can pick out of the room is one, and there are a great many of them — how many exactly is the power set fact further down this page.
Why isn’t \(\mathbb{Z} \in \mathbb{Q}\) — aren’t all integers rational numbers? They are, and that is exactly the claim \(\mathbb{Z} \subseteq \mathbb{Q}\). But \(\mathbb{Z} \in \mathbb{Q}\) says \(\mathbb{Z}\) is one of the rational numbers, and \(\mathbb{Z}\) is a set of numbers, not a number. The instinct is right; the symbol is wrong.
Set difference — do the backslash and the minus sign mean the same thing? Yes. \(A - B\) can be written \(A \setminus B\). Purely a matter of which textbook you are reading.
Q2 from the pre-class questions
True or false? \(\;\mathbb{Z} \in \mathbb{Q}\)
False. \(\mathbb{Z}\) is a set of numbers, so it is not an element of \(\mathbb{Q}\); the true statement is \(\mathbb{Z} \subseteq \mathbb{Q}\).
Take care with the distinction between “is an element of” and “is a subset of”.
And one level down: a single element is not the same as the set containing a single element, so \(2 \neq \{2\}\).
Worked: is it an element?
Determine whether each of the following is true or false.
| Statement | Reasoning | ||
|---|---|---|---|
| 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 does contain \(\{4\}\) as an element |
| c) | \(\{4\} \in \{2,3,4\}\) | False | \(\{2,3,4\}\) does not contain \(\{4\}\) as an element — it does contain \(4\) as an element |
- and (c) are parallel: in each case the set contains something, just not the thing being asked about. \(\{4\} \subseteq \{2,3,4\}\) is true — (c) fails on the symbol, not on the containment.
The reliable technique is to write the set’s elements out as a list and ask whether the left-hand object is literally one of them. For \(\{\{4\}\}\) that list has one entry, the set \(\{4\}\), and \(4\) is not it.
Subsets and proper subsets
A set \(S\) is a subset of a set \(T\), denoted \(S \subseteq T\), if every element that is in \(S\) is also in \(T\). Formally we say \(\forall x\), if \(x \in S\) then \(x \in T\).
A set \(S\) is a proper subset of a set \(T\), denoted \(S \subset T\), if \(S \subseteq T\) and there is an element in \(T\) that is not in \(S\).
Examples: \(\mathbb{Z} \subseteq \mathbb{Q}\) and \(\mathbb{Z} \subseteq \mathbb{Z}\); \(\mathbb{Z} \subset \mathbb{Q}\) but \(\mathbb{Z} \not\subset \mathbb{Z}\).
For sets \(S\) and \(T\), to prove that \(S \subseteq T\), you consider an arbitrary element of \(S\) and show that it is also in \(T\). That is, we suppose \(x \in S\) and prove that \(x \in T\).
Worked: prove one set is a subset of another
(a) Let \(D = \{n \in \mathbb{Z} \mid n \equiv 2 \;(\mathrm{mod}\; 8)\}\) and let \(E\) be the set of even integers. Prove that \(D \subseteq E\).
Writing out both sets first makes the shape of the proof obvious:
\[D = \{\dots, 2, 10, 18, \dots\} \qquad E = \{\dots, 2, 4, 6, 8, \dots\} = \{n \in \mathbb{Z} \mid n \equiv 0 \;(\mathrm{mod}\; 2)\}\]
Rewriting \(E\) as a congruence class is the move that makes the two sets comparable — both are now “\(\equiv\) something”, and the proof is arithmetic.
Proof. Let \(x \in D\). Then \(x \equiv 2 \;(\mathrm{mod}\; 8)\), so \(\exists k \in \mathbb{Z}\) such that \[x = 8k + 2 = 2(4k+1) + 0\] \(\therefore x \equiv 0 \;(\mathrm{mod}\; 2)\), \(\therefore x \in E\). Thus \(D \subseteq E\). \(\blacksquare\)
(b) Is \(D \subset E\)?
Yes. \(4 \in E\) but \(4 \notin D\), so \(D \subseteq E\) is proper. One witness is all a proper containment needs.
When are two sets equal?
For sets \(S\) and \(T\), saying \(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\) is logically equivalent to \((S \subseteq T) \land (T \subseteq S)\).
So to prove two sets \(S\) and \(T\) are equal you do two separate proofs: suppose \(x \in S\) and prove \(x \in T\) (giving \(S \subseteq T\)), then suppose \(x \in T\) and prove \(x \in S\) (giving \(T \subseteq S\)). Together these show \(S = T\).
This is a consequence, not a convention — it is the biconditional law of logical-equivalence-laws read through the definition of \(\subseteq\).
The empty set
\(\emptyset = \{\;\}\)
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 is never satisfied, so the conditional is vacuously true — the F-hypothesis row of the truth table in conditional-statements is doing all the work.
Take the two halves of the conditional separately: \(x \in \emptyset\) is F — always false, whatever \(x\) is — and \(x \in A\) is F/T, because it could go either way. A conditional with a false hypothesis is true regardless of the conclusion, so the implication holds for every \(x\) and every \(A\).
Do not confuse this with \(\emptyset \in A\). There are some sets that do contain the empty set, but there are lots of sets that do not.
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 time because the conclusion restates the hypothesis.
Lemma. There is only one empty set.
Proof (by contradiction). Suppose that \(\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, we have \(\emptyset_2 \subseteq \emptyset_1\). Thus \(\emptyset_1 = \emptyset_2\) by definition of set equality, and we have reached a contradiction. \(\blacksquare\)
Hence \(\emptyset_1 = \emptyset_2 = \emptyset\) — the empty set, which is why it gets a symbol of its own.
Unions and intersections
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\}\]
\[\bigcup_{i=1}^{3} A_i = A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5\}\]
\[\bigcap_{i=1}^{3} A_i = (A_1 \cap A_2) \cap A_3 = \{1,2\} \cap \{3,4,5\} = \emptyset\]
All three pairwise intersections are non-empty, and the triple intersection is still empty. Pairwise overlap does not propagate to the whole family.
Worked: an infinite union and an infinite intersection
Determine the following sets, recalling the interval notation \([a,b] = \{x \in \mathbb{R} \mid a \leq x \leq b\}\).
\[\bigcup_{i=0}^{\infty} \{i, -i\} = \{0, -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\}\]
For the intersection, the intervals grow with \(i\) — \([0,0] \subseteq [-1,1] \subseteq [-2,2] \subseteq \cdots\) — so the intersection is pinned by the smallest, the \(i=0\) term \([0,0] = \{0\}\). The nested intervals are drawn on a number line in sets-and-set-notation.
The power set
Let \(S = \{1,2,3\}\). Then \(\mathcal{P}(S) = \big\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\big\}\)
The elements of a power set are sets, which resets the \(\in\)/\(\subseteq\) trap one level up:
| \(\{1,2\} \in \mathcal{P}(S)\) | it is one of the eight things listed |
| \(\{1,2\} \not\subseteq \mathcal{P}(S)\) | that would need \(1\) and \(2\) to be elements of \(\mathcal{P}(S)\) |
| \(\big\{\{1,2\}\big\} \subseteq \mathcal{P}(S)\) | its one element, \(\{1,2\}\), is in \(\mathcal{P}(S)\) |
Since \(\emptyset \subseteq A\) for every set \(A\), it follows that \(\emptyset \in \mathcal{P}(A)\) for every set \(A\).
Fact. If \(T\) is a finite set that contains \(n\) elements, then \(|\mathcal{P}(T)| = 2^{n}\).
This fact is important. The finite qualifier is part of it, and the \(2^{n}\) comes from building a subset by making \(n\) independent in-or-out choices.
Worked: element or subset of a power set?
True or false? \(\;\{1, 3, -1\} \subset \mathcal{P}(\mathbb{Z})\)
False, by walking the levels carefully:
\[1, 3, -1 \in \mathbb{Z} \;\;\therefore\; \{1,3,-1\} \subseteq \mathbb{Z} \;\;\therefore\; \{1,3,-1\} \in \mathcal{P}(\mathbb{Z}) \;\;\text{so}\;\; \{1,3,-1\} \not\subset \mathcal{P}(\mathbb{Z})\]
It is an element of the power set, not a subset of it. For it to be a subset, its own elements \(1\), \(3\), \(-1\) would have to be subsets of \(\mathbb{Z}\) — and they are integers, not sets. The statement is off by exactly one level.
Worked: write down each power set
Number the elements while writing them and then check each answer against \(2^n\), which is the cheapest way to catch a dropped brace:
| Power set | Value | Check |
|---|---|---|
| \(\mathcal{P}(\{a\})\) | \(\big\{\emptyset,\; \{a\}\big\}\) | \(|\{a\}| = 1\), so \(2^1 = 2\) ✓ |
| \(\mathcal{P}(\emptyset)\) | \(\big\{\emptyset\big\}\) | \(|\emptyset| = 0\), so \(2^0 = 1\) ✓ |
| \(\mathcal{P}(\mathcal{P}(\emptyset)) = \mathcal{P}(\{\emptyset\})\) | \(\big\{\emptyset,\; \{\emptyset\}\big\}\) | \(|\{\emptyset\}| = 1\), so \(2^1 = 2\) ✓ |
| \(\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\), so \(2^2 = 4\) ✓ |
The line to get right is \(\mathcal{P}(\emptyset) = \{\emptyset\}\): the empty set has exactly one subset — itself — so its power set has one element and is not empty.
Cartesian products
Let \(A_1 = \{1,2\}\), \(A_2 = \{3,4,5\}\) and \(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)\}\]
with \(|A_1 \times A_2| = |A_1| \cdot |A_2| = 2 \times 3 = 6\). The product is drawn as a grid of points in sets-and-set-notation.
Let \(S = \{a,b,c\}\) and \(T = \{c,d\}\).
- \((d,c) \notin S \times T\) since \(d \notin S\) — order matters.
- \((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}\}\), often denoted \(\mathbb{R}^2\).
Two more facts: if \(A = \emptyset\) or \(B = \emptyset\) then \(A \times B = \emptyset\); and for finite sets, \(|A_1 \times A_2 \times \cdots \times A_n| = |A_1| \cdot |A_2| \cdots |A_n|\).
Notation issue to be aware of. \((a,b)\) can be used for an ordered pair. \((a,b)\) can also be used as an interval, representing the real numbers \(x\) where \(a < x < b\). Only context distinguishes them.
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\]
Examples. A partition of \(\mathbb{Z}\) is given by \(\{E, O\}\) where \(E\) is the even integers and \(O\) the odd integers. Another partition of \(\mathbb{Z}\) is \(\big\{\{0\}, \mathbb{Z}^{+}, \mathbb{Z}^{-}\big\}\) — the same set, partitioned two different ways.
Worked: partitions
(a) 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 the set \(R\)? Explain why or why not.
No. The covering condition \(R = S \cup T\) holds by definition, but disjointness fails:
\[10 \equiv 1 \;(\mathrm{mod}\; 3) \;\Rightarrow\; 10 \in S \qquad\text{and}\qquad 10 \equiv 2 \;(\mathrm{mod}\; 4) \;\Rightarrow\; 10 \in T\]
So \(10 \in S \cap T\), hence \(S \cap T \neq \emptyset\), and \(\{S,T\}\) is not a partition of \(R\). Stripe the two congruence classes along a number line — pink for \(S\), green for \(T\) — and a tick carrying both colours is a point of \(S \cap T\).
Figure 2: Finding the counterexample: the two congruence classes striped along the integers — S every third integer (pink row), T every fourth (green row) — and read off for a tick that both stripes cover. The grey capsules mark those ticks, which are the overlap.
The grey capsules mark every tick both stripes cover in the range drawn — \(10\) is the witness above, and \(-2\) works equally well. Two witnesses are no better than one here: disjointness is a universal claim, so a single overlap kills it.
(b) State two different partitions of the set \(\mathbb{Z} \times \mathbb{Z}\).
By the sign of the first coordinate: \[R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a \geq 0\} \qquad L = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a < 0\}\] \(\{L, R\}\) is a partition of \(\mathbb{Z} \times \mathbb{Z}\).
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}\).
Picture \(\mathbb{Z} \times \mathbb{Z}\) as a lattice of dots carrying both partitions at once: a block over the right half of the lattice against a block over the left half for \(\{L, R\}\), and horizontal stripes alternating row by row for the parity split \(\{E, O\}\) — the same “cut the whole thing up and check nothing is covered twice” picture as Figure 2, one dimension up.
The general recipe: any property that every element either has or lacks splits the set into two parts that partition it, provided neither part is empty. Made exact later in the course by equivalence relations.
See also
- sets-and-set-notation — the reference note for all of the above
- proving-set-properties · functions-on-general-sets — where Lecture 18 takes this
- modular-arithmetic — the congruence classes in the subset proof and the partition question
- conditional-statements · logical-equivalence-laws — vacuous truth, and the biconditional behind set equality
- 2026-08-31-solving-recurrence-relations — Lecture 16
- 2026-09-03-set-properties-and-functions — Lecture 18
- practice-problems — §21 Set Theory Definitions, with full worked solutions
- practice-problems — §22 More Definitions and Examples of Sets