Lesson 10 of 10 · 15 min
Chapter review
Watch a class
The whole chapter on YouTube
Loading the full lesson
Must-know facts
18 facts
- 01A relation on A is a subset of A × A; with n(A) = n there are 2^(n²) of them.
- 02Empty relation: R = φ. Universal relation: R = A × A. Both are trivial relations.
- 03Reflexive: (a, a) ∈ R for all a ∈ A.
- 04Symmetric: (a, b) ∈ R ⇒ (b, a) ∈ R.
- 05Transitive: (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R.
- 06Equivalence relation = reflexive + symmetric + transitive.
- 07Perpendicularity of lines: symmetric only. a ≤ b on R: reflexive and transitive, not symmetric.
- 08Congruence and similarity of triangles, and 'n divides a − b' on Z, are equivalence relations.
- 09Equivalence classes are pairwise disjoint and their union is the whole set; [a] = [b] ⇔ a R b.
- 102 | a − b on Z has two classes, [0] (evens) and [1] (odds); 3 | a − b has three, [0], [1], [2].
- 11One-one: f(x₁) = f(x₂) ⇒ x₁ = x₂. Many-one otherwise.
- 12Onto: range = codomain. Bijective: one-one and onto.
- 13f(x) = 2x: one-one not onto on N; bijective on R. x²: neither on R.
- 14[x], |x| and sgn x are neither one-one nor onto as maps R → R.
- 15For finite X, f : X → X is one-one ⇔ onto; there are n! such bijections of an n-element set.
- 16gof(x) = g(f(x)): f first. gof ≠ fog in general.
- 17f is invertible ⇔ f is one-one and onto; gof = I_X and fog = I_Y.
- 18f⁻¹ is found by solving y = f(x) for x; f⁻¹ ≠ 1/f.
Common traps
Where marks are lost
Formulas
10 to know
Relations on a set
number of relations on A = 2^(n²)
n(A) = n, since A × A has n² pairs.
Reflexive
(a, a) ∈ R ∀ a ∈ A
Every diagonal pair present.
Symmetric
(a, b) ∈ R ⇒ (b, a) ∈ R
Every pair has its mirror.
Transitive
(a, b), (b, c) ∈ R ⇒ (a, c) ∈ R
Every chain has its shortcut.
Equivalence class
[a] = {x ∈ X : x R a}
Classes are equal or disjoint.
One-one
f(x₁) = f(x₂) ⇒ x₁ = x₂
Injective.
Onto
∀ y ∈ Y, ∃ x ∈ X : f(x) = y
Surjective; range = codomain.
Bijections of a finite set
n(X) = n ⇒ n! one-one functions X → X
Each is also onto.
Composition
gof(x) = g(f(x))
f : A → B, g : B → C, gof : A → C.
Inverse
f⁻¹of = I_X, fof⁻¹ = I_Y
Exists exactly when f is one-one and onto.
Key terms
12 terms
- Empty relation
- The relation φ on a set: no element is related to any element.
- Universal relation
- The relation A × A: every element is related to every element.
- Reflexive relation
- One in which every element is related to itself.
- Symmetric relation
- One in which a related to b always means b related to a.
- Transitive relation
- One in which a related to b and b related to c always means a related to c.
- Equivalence relation
- A relation that is reflexive, symmetric and transitive.
- Equivalence class
- [a], the set of all elements related to a under an equivalence relation.
- One-one (injective)
- A function that never gives two different inputs the same output.
- Onto (surjective)
- A function whose range is its whole codomain.
- Bijective
- A function that is both one-one and onto.
- Composition
- gof, the function x ↦ g(f(x)): apply f, then g.
- Inverse function
- f⁻¹, the function that undoes f; it exists only for a bijection.