🎯 Key Points
- Reflexive: (a, a) ∈ R for every a ∈ A. Symmetric: (a, b) ∈ R ⟹ (b, a) ∈ R. Transitive: (a, b), (b, c) ∈ R ⟹ (a, c) ∈ R
- An equivalence relation is all three at once; it partitions the set into disjoint equivalence classes
- One-one (injective): f(x₁) = f(x₂) ⟹ x₁ = x₂. Onto (surjective): range = codomain. Bijective: both
- For a function between two finite sets of the same size, one-one ⟺ onto - but this equivalence fails for infinite sets
- Composition: (g∘f)(x) = g(f(x)) - apply f first. Composition is associative but not commutative
- f is invertible if and only if f is bijective, and then (f⁻¹)⁻¹ = f
- (g∘f)⁻¹ = f⁻¹∘g⁻¹ - the order reverses
- The empty relation is symmetric and transitive but not reflexive (on a non-empty set); the universal relation is all three
Types of Relations
A relation R on a set A is a subset of A × A. The three properties that matter:
- Reflexive - every element relates to itself
- Symmetric - the relation never has a preferred direction
- Transitive - relations chain together
Two special cases: the empty relation R = ∅ (nothing relates to anything) and the universal relation R = A × A (everything relates to everything).
Equivalence Relations and Classes
A relation that is reflexive, symmetric and transitive is an equivalence relation. Its real power is structural: it splits A into non-overlapping equivalence classes, where [a] = { x ∈ A : (x, a) ∈ R }. Every element belongs to exactly one class, and the classes together make up all of A.
A standard example: on the integers, "a is related to b if a − b is divisible by 3" is an equivalence relation, and it produces exactly three classes - the remainders 0, 1 and 2.
Types of Functions
- One-one (injective) - distinct inputs give distinct outputs. Test: assume f(x₁) = f(x₂) and derive x₁ = x₂. Graphically, no horizontal line meets the graph twice.
- Onto (surjective) - every element of the codomain is hit, so range = codomain.
- Bijective - one-one and onto together.
Counting note: if A has m elements and B has n, the number of one-one functions A → B is nPm (needing n ≥ m), and a bijection exists only when m = n.
Composition of Functions
For f : A → B and g : B → C, the composite g∘f : A → C is defined by (g∘f)(x) = g(f(x)) - the inner function acts first. Key facts:
- Composition is associative: (h∘g)∘f = h∘(g∘f)
- It is generally not commutative: g∘f ≠ f∘g
- If f and g are both one-one, so is g∘f; if both are onto, so is g∘f
Invertible Functions
f : A → B is invertible if there exists g : B → A with g∘f = IA and f∘g = IB. Such a g is unique and is written f⁻¹.
f is invertible ⟺ f is bijective
To find f⁻¹: write y = f(x), solve for x in terms of y, then swap the names.
💡 Advanced Edge
- The three properties are independent - a relation can hold any combination. "Is perpendicular to" on lines is symmetric but neither reflexive nor transitive.
- Restricting the codomain can force ontoness: f(x) = x² is not onto as a map ℝ → ℝ, but it is onto as a map ℝ → [0, ∞).
- Restricting the domain can force injectivity: f(x) = x² is not one-one on ℝ, but is on [0, ∞) - exactly the trick used to define √x.
- On infinite sets, one-one no longer implies onto: f : ℕ → ℕ with f(n) = 2n is injective but misses every odd number.
- If g∘f is one-one then f must be one-one, but g need not be - a common exam distractor.
Example 1 - Checking an equivalence relation
Q: On ℤ, define aRb if a − b is divisible by 5. Show R is an equivalence relation.
Reflexive: a − a = 0, and 0 is divisible by 5 ✓
Symmetric: if 5 | (a − b) then 5 | (b − a), since b − a = −(a − b) ✓
Transitive: if 5 | (a − b) and 5 | (b − c), then their sum a − c is divisible by 5 ✓
Answer: R is an equivalence relation, with 5 classes - the remainders 0, 1, 2, 3 and 4.
Example 2 - One-one and onto
Q: Is f : ℝ → ℝ, f(x) = 3x + 5, bijective?
One-one: 3x₁ + 5 = 3x₂ + 5 ⟹ 3x₁ = 3x₂ ⟹ x₁ = x₂ ✓
Onto: for any y ∈ ℝ take x = (y − 5)/3, which is real and gives f(x) = y ✓
Answer: f is bijective, and f⁻¹(y) = (y − 5)/3.
Example 3 - Composition
Q: If f(x) = x + 1 and g(x) = x², find g∘f and f∘g, and comment.
Step 1 - (g∘f)(x) = g(f(x)) = g(x + 1) = (x + 1)².
Step 2 - (f∘g)(x) = f(g(x)) = f(x²) = x² + 1.
Answer: (x + 1)² and x² + 1. They differ - for instance at x = 1 they give 4 and 2 - confirming composition is not commutative.
Empty, Universal, and Identity Relations
- A relation R on a set A is a subset of the Cartesian product A × A
- The empty relation R = ∅ relates no element to any element (no pair belongs to R)
- The universal relation R = A × A relates every element to every element
- Both the empty and universal relations are called trivial relations
- The identity relation is R = {(a, a) : a ∈ A}, relating each element only to itself
- Example: on A = {1, 2, 3}, the relation "x = y" is the identity relation {(1,1), (2,2), (3,3)}
One-One and Onto - Deciding in Practice
- A function f is one-one (injective) if f(x₁) = f(x₂) forces x₁ = x₂ - distinct inputs give distinct outputs
- A function f is onto (surjective) if every element of the co-domain is the image of some element, i.e. range = co-domain
- A function that is both one-one and onto is a bijection
- To test one-one algebraically: assume f(x₁) = f(x₂) and show x₁ = x₂; to test onto: solve y = f(x) for x within the domain for every y in the co-domain
- Graphically, a one-one function passes the horizontal line test - no horizontal line meets the graph more than once
- Example: f(x) = 2x + 3 from R to R is both one-one and onto, hence a bijection
Number of Functions Between Finite Sets
- If set A has m elements and set B has n elements, the total number of functions from A to B is nᵐ
- The number of one-one functions from A to B (with m ≤ n) is n·(n−1)·…·(n−m+1), i.e. the arrangement nPm
- If m is greater than n, no one-one function from A to B can exist (Pigeonhole Principle)
- The number of bijections from a set of n elements to itself is n!
- Onto functions exist from A to B only when m ≥ n
- These counting results are frequent in JEE objective questions on functions
Binary Operations
- A binary operation ∗ on a set A is a function ∗ : A × A → A, assigning to each ordered pair (a, b) a unique element a ∗ b of A
- The key requirement is closure: a ∗ b must again lie in A for all a, b in A
- Example: ordinary addition and multiplication are binary operations on the set of natural numbers
- Subtraction is a binary operation on integers but not on natural numbers (2 − 5 is not natural), so closure can fail
- Division is not a binary operation on the whole set of real numbers because division by 0 is undefined
- An operation may be displayed for a small finite set using an operation (Cayley) table
Properties of Binary Operations
- Commutative: a ∗ b = b ∗ a for all a, b in A
- Associative: (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c in A
- Identity element e: an element with a ∗ e = e ∗ a = a for every a; for addition e = 0, for multiplication e = 1
- Inverse of a: an element b with a ∗ b = b ∗ a = e; it can exist only when an identity exists
- Addition on R is commutative and associative with identity 0 and inverse −a
- The identity element, when it exists, is unique, and so is the inverse of a given element