2.1 Binary Relations
A binary relation R from set A to set B is a subset of the Cartesian product A × B.
Notation and Properties:
- R ⊆ A × B - R is a relation from A to B
- aRb or (a,b) ∈ R - a is related to b
- Reflexive: ∀a ∈ A, aRa
- Symmetric: aRb ⟹ bRa
- Transitive: aRb ∧ bRc ⟹ aRc
2.2 Equivalence Relations
An equivalence relation is a relation that is reflexive, symmetric, and transitive.
Key Properties:
- Partitions the set into disjoint equivalence classes
- Each element belongs to exactly one equivalence class
- Equivalence class of a: [a] = {x ∈ A | xRa}
2.3 Functions
Function Types
Injective (One-to-one)
Different inputs produce different outputs
f(a) = f(b) ⟹ a = b
Surjective (Onto)
Every element in codomain is mapped to
∀y ∈ B, ∃x ∈ A: f(x) = y
Bijective
Both injective and surjective
Has an inverse function
Function Composition
For functions f: A → B and g: B → C:
(g ∘ f)(x) = g(f(x))
The composition g∘f maps from A to C
Inverse Functions
If f is bijective, then f⁻¹ exists such that:
- f⁻¹(f(x)) = x
- f(f⁻¹(y)) = y
2.4 Practice Problems
Problem 1: Relation Properties
Consider the relation R on ℤ defined by: aRb ⟺ a ≡ b (mod 3)
Determine if R is reflexive, symmetric, and transitive.
Solution:
- Reflexive: ✓ (a ≡ a (mod 3) for all a)
- Symmetric: ✓ (if a ≡ b (mod 3), then b ≡ a (mod 3))
- Transitive: ✓ (if a ≡ b and b ≡ c (mod 3), then a ≡ c (mod 3))
- Conclusion: R is an equivalence relation
Problem 2: Function Analysis
Let f: ℝ → ℝ be defined by f(x) = x²
Determine if f is injective, surjective, or bijective.
Analysis:
- Injective: ✗ (f(-2) = f(2) = 4, but -2 ≠ 2)
- Surjective: ✗ (no x ∈ ℝ such that f(x) = -1)
- Bijective: ✗ (neither injective nor surjective)