← Back to Module 0

Module 0a — Sets and Relations

Course: MAT1CJ101 — Differential Calculus (prerequisite refresher)
Status: Prerequisite background material — not part of the official 60 taught hours, not examined.

0. Why This Module Exists

Every definition in calculus — domain, range, limit, continuity — is phrased in the language of sets and relations. If “$x \in A$” or “$f \subseteq A \times B$” feels unfamiliar, the calculus definitions will feel like magic instead of precise statements. This module rebuilds that language from scratch, with enough worked examples that you can use it fluently, not just recognise it.

1. Sets

1.1 What Is a Set?

A set is a well-defined collection of distinct objects, called its elements or members. “Well-defined” means that for any object, we can say for certain whether it belongs to the set or not.

Notation:

• $x \in A$ means “$x$ is an element of $A$”
• $x \notin A$ means “$x$ is not an element of $A$”
• Sets are usually named with capital letters: $A, B, S, X, \ldots$

Ways to describe a set:

Worked Example 1: Write $B = {2, 4, 6, 8, 10, \ldots}$ (even natural numbers) in set-builder form.

1.2 Special Sets

Cardinality: $\lvert A \rvert$ denotes the number of elements in a finite set $A$. $\lvert {a, b, c} \rvert = 3$. A set with $\lvert A \rvert = 0$ is the empty set.

1.3 Subsets

Definition: $A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$: $(\forall x)(x \in A \implies x \in B)$.

• $A$ is a proper subset of $B$, written $A \subset B$, if $A \subseteq B$ and $A \neq B$ ($B$ has at least one element not in $A$).
• Every set is a subset of itself: $A \subseteq A$.
• The empty set is a subset of every set: $\emptyset \subseteq A$ for any $A$.

Worked Example 2: Let $A = {1, 2}$, $B = {1, 2, 3}$. Is $A \subseteq B$? Is $B \subseteq A$?

Check $A \subseteq B$: is every element of $A$ in $B$? \(1 \in A \text{ and } 1 \in B \ \checkmark \qquad 2 \in A \text{ and } 2 \in B \ \checkmark\) So $A \subseteq B$. Also $A \neq B$, so $A \subset B$ (proper subset).

Check $B \subseteq A$: is every element of $B$ in $A$? \(3 \in B \text{ but } 3 \notin A. \ \times\) So $B \not\subseteq A$.

Two sets are equal ($A = B$) exactly when $A \subseteq B$ and $B \subseteq A$. This “double subset” test is the standard way to prove two sets are equal.

1.4 The Power Set

The power set of $A$, written $P(A)$, is the set of all subsets of $A$ (including $\emptyset$ and $A$ itself).

Worked Example 3: Find $P(A)$ for $A = {a, b, c}$.

Subsets of size 0: $\emptyset$
Subsets of size 1: ${a}, {b}, {c}$
Subsets of size 2: ${a,b}, {a,c}, {b,c}$
Subsets of size 3: ${a,b,c}$

Count check: $\lvert A \rvert = 3$, so $\lvert P(A) \rvert = 2^3 = 8$. $\checkmark$ (8 subsets listed)

Fact: If $\lvert A \rvert = n$, then $\lvert P(A) \rvert = 2^n$. Each element independently is either “in” or “out” of a given subset, giving 2 choices per element and $2^n$ subsets total.

2. Set Operations

Let $U$ be a universal set and $A, B \subseteq U$.

2.1 Union, Intersection, Difference, Complement

Disjoint sets: $A$ and $B$ are disjoint if $A \cap B = \emptyset$ (no common elements).

Worked Example 4: Let $U = {1,\ldots,10}$, $A = {1,2,3,4,5}$, $B = {4,5,6,7}$. Find $A \cup B$, $A \cap B$, $A - B$, and $A’$.

\(A \cup B = \{1,2,3,4,5,6,7\} \quad \text{(everything in } A \text{ or } B\text{)}\) \(A \cap B = \{4,5\} \quad \text{(common to both)}\) \(A - B = \{1,2,3\} \quad \text{(in } A\text{, remove anything also in } B\text{)}\) \(A' = U - A = \{6,7,8,9,10\} \quad \text{(everything in } U \text{ not in } A\text{)}\)

2.2 Venn Diagrams

A Venn diagram represents sets as overlapping regions inside a rectangle (the universal set). For two sets $A, B$, the rectangle splits into four regions:

 ______________________________
|  U                           |
|     ______      ______       |
|    /  A   \    /   B   \     |
|   |  only  |__|  only   |    |
|   |  (A-B) |A∩B| (B-A)  |    |
|    \______/    \______/      |
|         outside both: (A∪B)'  |
|______________________________|

Venn diagrams are the fastest way to check an identity or compute a region by hand — shade the region described on both sides and compare.

2.3 Set Identities (Laws of Set Algebra)

Why De Morgan’s laws matter: they let you push a complement (negation) inside a union/intersection, flipping $\cup$ to $\cap$ and vice versa. This is exactly the set-theory version of “not (P or Q) = (not P) and (not Q)” in logic — you’ll use this pattern again when negating limit/continuity statements involving “for all” and “there exists.”

Worked Example 5: Verify De Morgan’s law $(A \cup B)’ = A’ \cap B’$ using $U = {1,\ldots,8}$, $A = {1,2,3,4}$, $B = {3,4,5,6}$.

\(A \cup B = \{1,2,3,4,5,6\} \qquad (A \cup B)' = \{7,8\} \quad \text{(LHS)}\) \(A' = \{5,6,7,8\} \qquad B' = \{1,2,7,8\} \qquad A' \cap B' = \{7,8\} \quad \text{(RHS)}\)

LHS $=$ RHS $= {7,8}$. Identity confirmed for this example.

2.4 Cartesian Product

Definition: The Cartesian product of $A$ and $B$ is \(A \times B = \{(a, b) : a \in A,\ b \in B\}\) — the set of all ordered pairs with first entry from $A$ and second entry from $B$.

Worked Example 6: Let $A = {1, 2}$, $B = {x, y, z}$. Find $A \times B$ and $B \times A$.

\(A \times B = \{(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)\} \qquad \lvert A \times B \rvert = 2 \cdot 3 = 6\) \(B \times A = \{(x,1), (x,2), (y,1), (y,2), (z,1), (z,2)\} \qquad \lvert B \times A \rvert = 3 \cdot 2 = 6\)

Note: $A \times B \neq B \times A$ as sets of pairs (order matters), even though $\lvert A \times B \rvert = \lvert B \times A \rvert$.

Why this matters: $\mathbb{R} \times \mathbb{R}$ (usually written $\mathbb{R}^2$) is the Cartesian plane. Every graph you draw in calculus — $y = f(x)$ — is literally a subset of $\mathbb{R} \times \mathbb{R}$, namely the set of pairs $(x, f(x))$. “Relation” (next section) and “function” are both defined as subsets of a Cartesian product.

3. Relations

3.1 Definition

A relation $R$ from a set $A$ to a set $B$ is any subset of $A \times B$: $R \subseteq A \times B$. If $(a, b) \in R$, we write $a\ R\ b$ and say “$a$ is related to $b$.”

When $A = B$, we call $R$ a relation on $A$.

Worked Example 7: Let $A = {1, 2, 3}$. Define $R = {(a,b) \in A \times A : a < b}$. List $R$.

Check all 9 pairs in $A \times A$:

$(1,1)$: $1<1$? No $\quad$ $(1,2)$: $1<2$? Yes $\quad$ $(1,3)$: $1<3$? Yes
$(2,1)$: $2<1$? No $\quad$ $(2,2)$: $2<2$? No $\quad$ $(2,3)$: $2<3$? Yes
$(3,1)$: No $\quad$ $(3,2)$: No $\quad$ $(3,3)$: No

3.2 Domain and Range of a Relation

For $R \subseteq A \times B$:

• Domain of $R$ $= {a \in A : (a,b) \in R \text{ for some } b \in B}$ — the first coordinates actually used
• Range of $R$ $= {b \in B : (a,b) \in R \text{ for some } a \in A}$ — the second coordinates actually used

Worked Example 8: For $R = {(1,2), (1,3), (2,3)}$ from Example 7, find the domain and range.

First coordinates used: $1, 1, 2$ $\to$ Domain $= {1, 2}$
Second coordinates used: $2, 3, 3$ $\to$ Range $= {2, 3}$

3.3 Properties of Relations (on a set A)

Let $R$ be a relation on $A$ ($R \subseteq A \times A$).

Worked Example 9: Let $A = {1,2,3,4}$ and $R = {(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)}$. Check reflexive, symmetric, transitive.

Reflexive? Need $(1,1),(2,2),(3,3),(4,4)$ all in $R$. All four are present. $\checkmark$ Reflexive.

Symmetric? For every $(a,b)$ in $R$, is $(b,a)$ in $R$?
$(1,2) \in R$ and $(2,1) \in R$ $\checkmark$ — all other pairs are of the form $(a,a)$, automatically symmetric. $\checkmark$ Symmetric.

Transitive? For every $(a,b),(b,c)$ in $R$, is $(a,c)$ in $R$?
$(1,2) \in R, (2,1) \in R \implies$ need $(1,1) \in R$. Yes. $\checkmark$
$(2,1) \in R, (1,2) \in R \implies$ need $(2,2) \in R$. Yes. $\checkmark$
(No other chains to check besides the trivial $(a,a),(a,a) \implies (a,a)$.) $\checkmark$ Transitive.

3.4 Equivalence Relations

Definition: $R$ is an equivalence relation on $A$ if $R$ is reflexive, symmetric, and transitive simultaneously.

Equivalence relations formalise “sameness in some respect.” Example 9’s relation $R$ is an equivalence relation on ${1,2,3,4}$ (it groups 1 and 2 together, and leaves 3, 4 alone).

Equivalence classes: For $a \in A$, the equivalence class of $a$ is $[a] = {x \in A : x\ R\ a}$. Equivalence classes partition $A$ — they are disjoint and their union is all of $A$.

Worked Example 10: Find the equivalence classes of $R$ from Example 9.

\([1] = \{x : x\ R\ 1\} = \{1, 2\} \quad \text{(since } (1,1) \text{ and } (2,1) \in R\text{)}\) \([2] = \{x : x\ R\ 2\} = \{1, 2\} \quad \text{(same class as } [1] \text{ — 1 and 2 are "linked")}\) \([3] = \{x : x\ R\ 3\} = \{3\} \qquad [4] = \{x : x\ R\ 4\} = \{4\}\)

Distinct classes: ${1,2}, {3}, {4}$. Check partition: ${1,2} \cup {3} \cup {4} = {1,2,3,4} = A$, and the three classes are pairwise disjoint. $\checkmark$

Common example: “Congruence mod $n$” on $\mathbb{Z}$ ($a \sim b$ if $n$ divides $a - b$) is an equivalence relation; its equivalence classes are the residue classes ${\ldots, \bmod n = 0}$, ${\bmod n = 1}$, etc. This idea reappears in the Data Structures course when discussing modular arithmetic.

3.5 Order Relations

Definition: $R$ is a partial order on $A$ if $R$ is reflexive, antisymmetric, and transitive. $(A, R)$ is then called a partially ordered set (poset).

The most familiar example: $\leq$ on $\mathbb{R}$ is a partial order (in fact a total order, since any two real numbers are comparable: for all $a, b$ either $a \leq b$ or $b \leq a$). $\subseteq$ on $P(A)$ is a partial order that is not total in general — e.g. ${1}$ and ${2}$ are both subsets of ${1,2,3}$ but neither is a subset of the other.

Worked Example 11: Is “divides” ($a \mid b$ means $b = ka$ for some integer $k$) a partial order on $\mathbb{N}$?

Reflexive: does $a \mid a$ for all $a \in \mathbb{N}$? $a = 1 \cdot a$. Yes. $\checkmark$

Antisymmetric: if $a \mid b$ and $b \mid a$, does $a = b$? \(a \mid b \text{ means } b = k_1 a; \quad b \mid a \text{ means } a = k_2 b \text{ for positive integers } k_1, k_2.\) Substituting: $a = k_2(k_1 a) = (k_1 k_2)a \implies k_1 k_2 = 1 \implies k_1 = k_2 = 1 \implies a = b$. $\checkmark$

Transitive: if $a \mid b$ and $b \mid c$, does $a \mid c$? \(b = k_1 a,\ c = k_2 b = k_2 k_1 a,\ \text{so } c = (k_1 k_2)a,\ \text{i.e. } a \mid c. \ \checkmark\)

All three hold: “divides” is a partial order on $\mathbb{N}$.
Not total: 2 and 3 are both in $\mathbb{N}$, but $2 \nmid 3$ and $3 \nmid 2$ — they are incomparable.

4. Summary

5. Practice Problems

1. List all elements of $A = {x : x \in \mathbb{Z}, -3 \leq x < 4}$.

2. Let $A = {1,2,3,4,5}$. Find $P(A)$ and verify $\lvert P(A) \rvert = 2^5$ using the counting fact.

3. Let $U = {1,\ldots,12}$, $A = {2,4,6,8,10,12}$, $B = {3,6,9,12}$. Find $A \cup B$, $A \cap B$, $A - B$, $B - A$, and verify $(A \cup B)’ = A’ \cap B’$ by computing both sides directly.

4. Prove using the double-subset method that if $A \subseteq B$ and $B \subseteq A$, then $A = B$, for $A = {x \in \mathbb{N} : x^2 < 10}$ and $B = {1,2,3}$.

5. Let $A = {a, b}$, $B = {1, 2, 3}$. Write out $A \times B$. How many elements does $(A \times B)$ have? Verify this matches $\lvert A \rvert \cdot \lvert B \rvert$.

6. Let $A = {1,2,3,4}$. Define $R = {(a,b) \in A \times A : a + b \text{ is even}}$. List $R$, then check whether $R$ is reflexive, symmetric, and transitive.

7. Is $R$ from Problem 6 an equivalence relation? If so, find its equivalence classes and verify they partition $A$.

8. On the set of all lines in a plane, define $R$ by $\ell_1\ R\ \ell_2$ if $\ell_1$ is parallel to $\ell_2$ (a line is considered parallel to itself). Show $R$ is an equivalence relation. What are the equivalence classes?

9. Define $R$ on $\mathbb{Z}$ by $a\ R\ b$ if $a - b$ is divisible by 3. Show $R$ is an equivalence relation and list the equivalence class of 0 (giving at least 5 elements).

10. Is the relation “$\leq$” on $\mathbb{N}$ reflexive, antisymmetric, and transitive? Is it a total order? Justify each answer.

11. Let $A = {1, 2, 3}$. Define $R = {(a,b) \in A \times A : a \text{ divides } b}$. Is $R$ a partial order on $A$? Is it a total order? Give a pair of incomparable elements if it is not total.

12. (Harder) Let $A$ and $B$ be finite sets with $\lvert A \rvert = m$, $\lvert B \rvert = n$. How many distinct relations are there from $A$ to $B$? (Hint: a relation is a subset of $A \times B$, and $\lvert A \times B \rvert = mn$.)

13. (Harder) Prove De Morgan’s law $(A \cap B)’ = A’ \cup B’$ in general (not just for a specific example), using the double-subset method: show every element of the LHS is in the RHS and vice versa.