Module 0a — Sets and Relations

← 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:

Method	Example
Roster (list) form	$A = \{1, 2, 3, 4, 5\}$
Set-builder form	$A = \{x : x \text{ is a natural number}, x \leq 5\}$
Descriptive	$A = $ “the set of natural numbers up to 5”

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

\[B = \{x : x = 2n,\ n \in \mathbb{N}\} = \{x \in \mathbb{N} : x \text{ is even}\}\]

Example 1 (Well-defined collection): Is “the collection of all prime numbers less than 20” a set?

For any object we name, we can decide with certainty whether it belongs: \(7 \to \text{prime, less than 20} \to 7 \text{ IS in the collection.}\) \(8 \to \text{not prime} \to 8 \text{ is NOT in the collection.}\) Every object gives a definite yes/no answer. $\checkmark$ Well-defined $\to$ it IS a set: $\{2, 3, 5, 7, 11, 13, 17, 19\}$.

Non-Example 1 (Well-defined collection): Is “the collection of all tall students in the class” a set?

Take a student who is 5’9”. Is 5’9” “tall”? Different people would answer differently — no fixed rule decides it. $\times$ “Tall” is not a precise, agreed-upon test, so membership is not determined with certainty for every object. This collection is NOT well-defined $\to$ NOT a set (it is a fuzzy/subjective grouping, not a set in the mathematical sense).

1.2 Special Sets

Symbol	Meaning
$\emptyset$ or $\{\}$	Empty set — contains no elements
$U$	Universal set — the “everything” set for a given discussion
$\mathbb{N}$	Natural numbers $\{1, 2, 3, \ldots\}$
$\mathbb{Z}$	Integers $\{\ldots, -2, -1, 0, 1, 2, \ldots\}$
$\mathbb{Q}$	Rational numbers
$\mathbb{R}$	Real numbers

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$.

Example 2 (Subset): Let $A = \{2, 4\}$, $B = \{1, 2, 3, 4, 5\}$. Is $A \subseteq B$?

Check every element of $A$: $2 \in A$ and $2 \in B$ $\checkmark$; $4 \in A$ and $4 \in B$ $\checkmark$. Every element of $A$ is also in $B$. $\checkmark$ $A \subseteq B$ (and in fact $A \subset B$, since $B$ has elements not in $A$).

Non-Example 2 (Subset): Let $A = \{2, 6\}$, $B = \{1, 2, 3, 4, 5\}$. Is $A \subseteq B$?

Check every element of $A$: $2 \in A$ and $2 \in B$ $\checkmark$; $6 \in A$ but $6 \notin B$ $\times$. Not every element of $A$ is in $B$ — one counterexample ($6$) is enough to break the subset condition. $A \not\subseteq B$.

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\}$

\[P(A) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{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.

Example 3 (Power set membership): Is $\{a, b\}$ an element of $P(\{a, b, c\})$?

$\{a, b\}$ is a subset of $\{a, b, c\}$: both $a$ and $b$ are in $\{a,b,c\}$. $\checkmark$ $P(A)$ contains every subset of $A$ as an element, so $\{a,b\} \in P(\{a,b,c\})$. $\checkmark$

Non-Example 3 (Power set membership): Is $\{a, d\}$ an element of $P(\{a, b, c\})$?

Is $\{a, d\}$ a subset of $\{a, b, c\}$? $a \in \{a,b,c\}$ $\checkmark$; $d \in \{a,b,c\}$? No — $d$ is not an element of $\{a,b,c\}$. $\times$ $\{a, d\}$ is NOT a subset of $\{a,b,c\}$ (it contains an element, $d$, outside $A$), so $\{a, d\} \notin P(\{a,b,c\})$.

---

2. Set Operations

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

2.1 Union, Intersection, Difference, Complement

Operation	Notation	Definition
Union	$A \cup B$	$\{x : x \in A \text{ or } x \in B\}$
Intersection	$A \cap B$	$\{x : x \in A \text{ and } x \in B\}$
Difference	$A - B$ (or $A \setminus B$)	$\{x : x \in A \text{ and } x \notin B\}$
Complement	$A’$ (or $A^c$)	$\{x \in U : x \notin A\} = U - A$

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{)}\)

Example 4 (Intersection membership): Using $U = \{1,\ldots,10\}$, $A = \{1,2,3,4,5\}$, $B = \{4,5,6,7\}$, is $4 \in A \cap B$?

$4 \in A$? Yes. $4 \in B$? Yes. Both hold $\implies$ $4 \in A \cap B$. $\checkmark$ Matches $A \cap B = \{4,5\}$ from Worked Example 4.

Non-Example 4 (Intersection membership): Is $3 \in A \cap B$?

$3 \in A$? Yes. $3 \in B$? No ($B = \{4,5,6,7\}$). Intersection requires membership in BOTH sets; failing on $B$ is enough. $\times$ $3 \notin A \cap B$ — even though $3 \in A \cup B$, since belonging to $A$ alone already satisfies the “or” in union. This is the classic union/intersection mix-up.

Example 5 (Difference): Is $2 \in A - B$?

$2 \in A$? Yes. $2 \in B$? No. $A - B$ needs “in $A$ AND not in $B$” — both parts hold. $\checkmark$ $2 \in A - B$.

Non-Example 5 (Difference): Is $4 \in A - B$?

$4 \in A$? Yes. $4 \in B$? Yes. $A - B$ needs “in $A$ AND NOT in $B$” — the second part fails, since $4 \in B$. $\times$ $4 \notin A - B$ (it gets removed precisely because it’s also in $B$).

Example 6 (Complement): Is $8 \in A’$ (with $U = \{1,\ldots,10\}$)?

$8 \in U$? Yes. $8 \in A$? No ($A = \{1,2,3,4,5\}$). $A’ = \{x \in U : x \notin A\}$ — 8 satisfies this. $\checkmark$ $8 \in A’$.

Non-Example 6 (Complement): Is $3 \in A’$?

$3 \in U$? Yes. $3 \in A$? Yes. $A’$ requires $x \notin A$, but $3$ IS in $A$. $\times$ $3 \notin A’$ — an element can’t be in both a set and its complement.

Example 7 (Disjoint sets): Are $C = \{1, 2\}$ and $D = \{3, 4\}$ disjoint?

$C \cap D = \{\}$: no element of $C$ is also in $D$ ($1 \neq 3, 1 \neq 4, 2 \neq 3, 2 \neq 4$). $\checkmark$ $C \cap D = \emptyset$ $\implies$ $C$ and $D$ are disjoint.

Non-Example 7 (Disjoint sets): Are $A = \{1,2,3,4,5\}$ and $B = \{4,5,6,7\}$ (from above) disjoint?

$A \cap B = \{4,5\}$ (computed above) — not empty. $\times$ Since $A \cap B \neq \emptyset$, $A$ and $B$ are NOT disjoint (they share the elements 4 and 5).

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)

Law	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 for $\cap$
Distributive	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$; $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Identity	$A \cup \emptyset = A$, $A \cap U = A$
Complement	$A \cup A’ = U$, $A \cap A’ = \emptyset$
Double complement	$(A’)’ = A$
De Morgan’s Laws	$(A \cup B)’ = A’ \cap B’$, $(A \cap B)’ = A’ \cup B’$

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.

Example 8 (Cartesian product membership): Let $A = \{1, 2\}$, $B = \{x, y, z\}$. Is $(2, y) \in A \times B$?

Is $2 \in A$? Yes. Is $y \in B$? Yes. $A \times B$ requires the first coordinate from $A$ and the second from $B$ — both hold. $\checkmark$ $(2, y) \in A \times B$.

Non-Example 8 (Cartesian product membership): Is $(y, 2) \in A \times B$?

Is $y \in A$? No ($A = \{1,2\}$), $y$ is not a member of $A$. $\times$ Order matters in an ordered pair: the FIRST coordinate must come from $A$, and $y$ doesn’t belong to $A$. $(y, 2) \notin A \times B$ — though note $(y, 2) \in B \times A$ instead.

---

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$.

Example 9 (Relation): Let $A = \{1, 2, 3\}$. Is $S = \{(1,2), (2,3)\}$ a relation on $A$?

Check $S \subseteq A \times A$: every pair in $S$ must have both coordinates in $A$. $(1,2)$: $1 \in A$, $2 \in A$ $\checkmark$; $(2,3)$: $2 \in A$, $3 \in A$ $\checkmark$. $S \subseteq A \times A$. $\checkmark$ $S$ is a valid relation on $A$.

Non-Example 9 (Relation): Is $T = \{(1,2), (2,4)\}$ a relation on $A = \{1, 2, 3\}$?

Check $T \subseteq A \times A$: $(1,2)$: $1 \in A$, $2 \in A$ $\checkmark$; $(2,4)$: $2 \in A$, but $4 \notin A$ $\times$. $T \not\subseteq A \times A$, because the pair $(2,4)$ uses $4$, which is outside $A$. $T$ is NOT a relation on $A$ (it would only qualify as a relation from $A$ to some larger set containing $4$).

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

\[R = \{(1,2), (1,3), (2,3)\}\]

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$).

Property	Definition	Test
Reflexive	$(a,a) \in R$ for every $a \in A$	Every element related to itself
Symmetric	$(a,b) \in R \implies (b,a) \in R$	Relation “goes both ways”
Antisymmetric	$(a,b) \in R$ and $(b,a) \in R \implies a = b$	No two distinct elements relate both ways
Transitive	$(a,b) \in R$ and $(b,c) \in R \implies (a,c) \in R$	Relation “chains”

Example 10 (Reflexive): Let $A = \{1,2,3\}$, $R = \{(1,1),(2,2),(3,3),(1,2)\}$. Is $R$ reflexive?

Need $(1,1), (2,2), (3,3)$ all in $R$. $(1,1) \in R$ $\checkmark$; $(2,2) \in R$ $\checkmark$; $(3,3) \in R$ $\checkmark$. Every element relates to itself. $\checkmark$ $R$ is reflexive.

Non-Example 10 (Reflexive): Let $A = \{1,2,3\}$, $R = \{(1,1),(2,2),(1,2)\}$. Is $R$ reflexive?

Need $(1,1), (2,2), (3,3)$ all in $R$. $(1,1) \in R$ $\checkmark$; $(2,2) \in R$ $\checkmark$; $(3,3) \in R$? No. $\times$ Element $3$ is not related to itself — one missing pair is enough. $R$ is NOT reflexive.

Example 11 (Symmetric): Let $A = \{1,2,3\}$, $R = \{(1,2),(2,1),(3,3)\}$. Is $R$ symmetric?

For every $(a,b) \in R$, check $(b,a) \in R$: $(1,2) \in R \implies$ need $(2,1) \in R$. Yes. $\checkmark$ $(2,1) \in R \implies$ need $(1,2) \in R$. Yes. $\checkmark$ $(3,3) \in R \implies$ need $(3,3) \in R$. Yes (trivially). $\checkmark$ $R$ is symmetric.

Non-Example 11 (Symmetric): Let $A = \{1,2,3\}$, $R = \{(1,2),(2,3)\}$. Is $R$ symmetric?

$(1,2) \in R \implies$ need $(2,1) \in R$. $(2,1) \notin R$. $\times$ One failure is enough: $R$ is NOT symmetric (the relation only “points” one way here — 1 relates to 2, but 2 does not relate back to 1).

Example 12 (Antisymmetric): Let $A = \{1,2,3\}$, $R = \{(1,1),(1,2),(2,3)\}$. Is $R$ antisymmetric?

Need: whenever $(a,b) \in R$ and $(b,a) \in R$, then $a = b$. $(1,2) \in R$ — is $(2,1) \in R$? No, so no conflict to check. $(2,3) \in R$ — is $(3,2) \in R$? No, so no conflict to check. $(1,1) \in R$ — $a = b$ already, trivially fine. No pair $(a,b)$ with $a \neq b$ has its reverse $(b,a)$ also in $R$. $\checkmark$ $R$ is antisymmetric.

Non-Example 12 (Antisymmetric): Let $A = \{1,2,3\}$, $R = \{(1,2),(2,1),(3,3)\}$. Is $R$ antisymmetric?

$(1,2) \in R$ and $(2,1) \in R$ — both directions present, with $a=1$, $b=2$, and $a \neq b$. $\times$ Antisymmetry demands $a = b$ whenever both directions hold; here $1 \neq 2$, so the condition fails. $R$ is NOT antisymmetric (note: this same $R$ IS symmetric — antisymmetric is not “not symmetric,” they test different things).

Example 13 (Transitive): Let $A = \{1,2,3\}$, $R = \{(1,2),(2,3),(1,3)\}$. Is $R$ transitive?

Need: whenever $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$. $(1,2) \in R$ and $(2,3) \in R \implies$ need $(1,3) \in R$. Yes, $(1,3) \in R$. $\checkmark$ No other chains to check. $R$ is transitive.

Non-Example 13 (Transitive): Let $A = \{1,2,3\}$, $R = \{(1,2),(2,3)\}$. Is $R$ transitive?

$(1,2) \in R$ and $(2,3) \in R \implies$ need $(1,3) \in R$. $(1,3) \notin R$. $\times$ The chain $1 \to 2 \to 3$ exists, but the “shortcut” pair $(1,3)$ is missing. $R$ is NOT transitive.

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.

Example 14 (Equivalence relation): Is “has the same remainder mod 2” (i.e. same parity) an equivalence relation on $\mathbb{Z}$?

Reflexive: does every $n$ have the same remainder mod 2 as itself? Yes, trivially. $\checkmark$ Symmetric: if $n$ and $m$ have the same remainder, so do $m$ and $n$ (order doesn’t matter). $\checkmark$ Transitive: if $n,m$ have the same remainder, and $m,k$ have the same remainder, then $n,k$ have the same remainder (all three equal the same value). $\checkmark$ All three hold. $\checkmark$ “Same parity” is an equivalence relation — its classes are “even numbers” and “odd numbers.”

Non-Example 14 (Equivalence relation): Is “$\leq$” an equivalence relation on $\mathbb{R}$?

Reflexive: $a \leq a$ for all $a$. $\checkmark$ Symmetric: does $a \leq b$ imply $b \leq a$? Take $a=1, b=2$: $1 \leq 2$ is true, but $2 \leq 1$ is false. $\times$ Symmetry already fails, so “$\leq$” is NOT an equivalence relation — it is reflexive and transitive, but not symmetric (it turns out to be a different structure: an order, see below).

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.

Example 15 (Partial order): Is $\subseteq$ a partial order on $P(\{1,2\})$?

Reflexive: $A \subseteq A$ for every $A$. $\checkmark$ Antisymmetric: if $A \subseteq B$ and $B \subseteq A$, then $A = B$ (the double-subset test). $\checkmark$ Transitive: if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$. $\checkmark$ All three hold. $\checkmark$ $\subseteq$ is a partial order on $P(\{1,2\}) = \{\emptyset,\{1\},\{2\},\{1,2\}\}$.

Non-Example 15 (Partial order): Is “$\neq$” (not equal) a partial order on $\mathbb{Z}$?

Reflexive: does $a \neq a$ hold for every $a$? No — $a \neq a$ is always FALSE. $\times$ Reflexivity already fails (every element must relate to itself, but here no element does), so “$\neq$” is NOT a partial order — regardless of the other two properties.

Example 16 (Total order): Is $\leq$ a total order on $\mathbb{R}$?

$\leq$ is already a partial order (reflexive, antisymmetric, transitive — checked above for the general case). Comparability: for ANY $a, b \in \mathbb{R}$, is $a \leq b$ or $b \leq a$? Take $a = -3, b = 7$: $-3 \leq 7$ holds. $\checkmark$ Take $a = 5, b = 5$: $5 \leq 5$ holds. $\checkmark$ In general, any two real numbers can be compared — there’s no pair that’s “incomparable.” $\checkmark$ $\leq$ is a total order on $\mathbb{R}$.

Non-Example 16 (Total order): Is $\subseteq$ a total order on $P(\{1,2,3\})$?

$\subseteq$ is a partial order (checked above, generalises to any $P(A)$). Comparability: take $A = \{1\}$, $B = \{2\}$. Is $A \subseteq B$? Is $1 \in \{2\}$? No. $\times$ Is $B \subseteq A$? Is $2 \in \{1\}$? No. $\times$ Neither $A \subseteq B$ nor $B \subseteq A$ — $\{1\}$ and $\{2\}$ are incomparable. $\times$ $\subseteq$ is NOT a total order on $P(\{1,2,3\})$ (it is only a partial order — some pairs of subsets simply cannot be compared).

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

Concept	Key Idea	Worked Example
Set	Well-defined collection of distinct objects	$A = \{x : x \in \mathbb{N}, x \leq 5\}$
Subset	Every element of $A$ is in $B$	$\{1,2\} \subseteq \{1,2,3\}$
Power set	Set of all subsets, size $2^n$	$\lvert P(\{a,b,c\}) \rvert = 8$
Union/intersection	Combine or overlap sets	$A \cup B$, $A \cap B$ for $A=\{1..5\}$, $B=\{4..7\}$
De Morgan’s laws	Push complement through $\cup/\cap$, flipping the operation	$(A \cup B)’ = A’ \cap B’$
Cartesian product	Set of ordered pairs	$A \times B$ for $A=\{1,2\}$, $B=\{x,y,z\}$: 6 pairs
Relation	Any subset of $A \times B$	$R = \{(a,b): a<b\}$ on $\{1,2,3\}$
Reflexive/symmetric/transitive	Structural properties of a relation	Checked directly against the pair list
Equivalence relation	Reflexive $+$ symmetric $+$ transitive	Partitions $A$ into equivalence classes
Partial order	Reflexive $+$ antisymmetric $+$ transitive	“Divides” on $\mathbb{N}$

---

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.

---

Course Home Next Module →