Relations and Functions — revision notes
1. Relations
A relation \(R\) on a set \(A\) is a subset of \(A \times A\). For \(A\) with \(n\) elements there are \(2^{n^2}\) relations.
- Reflexive: \((a, a) \in R\) for every \(a \in A\).
- Symmetric: \((a, b) \in R \Rightarrow (b, a) \in R\).
- Transitive: \((a, b), (b, c) \in R \Rightarrow (a, c) \in R\).
- Equivalence: all three. Empty relation: symmetric and transitive (vacuously), not reflexive on a non-empty set. Universal relation \(A \times A\): equivalence.
2. Equivalence classes
\([a] = \{x \in A : x\,R\,a\}\). Two classes are either identical or disjoint, and together they cover \(A\) (a partition). Example: “\(a - b\) divisible by \(m\)” on \(\mathbb{Z}\) has \(m\) classes (remainders \(0, 1, \ldots, m - 1\)).
3. Functions
- One-one (injective): \(f(x_1) = f(x_2) \Rightarrow x_1 = x_2\). Test: solve \(f(x_1) = f(x_2)\); or find two different inputs with the same output to disprove. A strictly increasing/decreasing function is one-one.
- Onto (surjective): range \(=\) codomain. Test: for arbitrary \(y\) in the codomain, solve \(y = f(x)\) and check that \(x\) lies in the domain.
- Bijective: one-one and onto.
- Counting (\(|A| = m\), \(|B| = n\)): functions \(n^m\); one-one functions \(n(n-1)\cdots(n-m+1)\) if \(m \le n\), else \(0\); onto functions from a \(3\)-set to a \(2\)-set: \(2^3 - 2 = 6\).
Worked example 1
On \(\{1, \ldots, 6\}\), \(a\,R\,b \iff 3 \mid (a - b)\): classes \(\{1, 4\}, \{2, 5\}, \{3, 6\}\).
Worked example 2
\(f : \mathbb{R} \to \mathbb{R}\), \(f(x) = 4 - 3x\): \(f(x_1) = f(x_2) \Rightarrow x_1 = x_2\) (one-one); for any \(y\), \(x = \dfrac{4 - y}{3}\) works (onto). Bijective.
Worked example 3
\(f : \mathbb{N} \to \mathbb{N}\), \(f(n) = n^2 + 1\): one-one (as \(n > 0\)), not onto (\(1\) and \(3\) have no pre-image).
Common errors
- Checking reflexivity for only the elements that appear in \(R\) instead of all of \(A\).
- Showing onto by solving for \(x\) but not checking that \(x\) lies in the domain (e.g. \(x \in \mathbb{N}\), \(x \ne 2\)).
- Forgetting that the answer depends on the domain and codomain: \(x^2\) is not one-one on \(\mathbb{R}\) but is one-one on \([0, \infty)\).
- Giving an “example” instead of a proof when asked to show a property holds; a single counter-example is enough only to show it fails.
Board-exam tips
- Write each of reflexive, symmetric, transitive under its own heading with a one-line reason.
- For a “not” answer, always give a specific counter-example pair.
- Composite and inverse functions are not in the current syllabus — do not spend time on \(g \circ f\) or \(f^{-1}\).
Topics in this chapter: Types of relations · Counting relations and functions · Equivalence relations and equivalence classes · One-one and onto functions.