Relations and Functions
1. Check this before you revise anything
"Binary operations" is mentioned but not actually taught in this chapter anymore. The book's own opening paragraph says the chapter covers "different types of relations and functions, composition of functions, invertible functions and binary operations," and the Summary repeats the same list — but between the introduction and the summary there is no section on binary operations at all. The chapter goes straight from "Composition of Functions and Invertible Function" (section 1.4) to the Miscellaneous Exercise.
No definition, no example, no exercise question anywhere in the current book actually teaches binary operations. This is left-over wording from an older edition that the syllabus rationalisation dropped the content for but didn't fully scrub from the framing text — treat it as noise, not a topic to revise.
The old stub taught binary operations as a full section anyway, complete with a table of properties and its own line in the exam-focus list. That entire section has been removed from this rebuild, along with the invented five-question "Self-Test" that stood in for real exercise coverage.
The book has three real problem sets instead — Exercise 1.1 (16 questions, all about classifying relations), Exercise 1.2 (12 questions, all about one-one/onto functions), and a Miscellaneous Exercise (7 questions) — 35 questions in total, none of which the old stub touched.
2. What this chapter covers
| Textbook section | Topic |
|---|---|
| 1.2 | Types of relations: empty, universal, reflexive, symmetric, transitive, equivalence; equivalence classes |
| 1.3 | Types of functions: one-one (injective), onto (surjective), bijective |
| 1.4 | Composition of functions; invertible functions |
3. Types of relations
A relation in a set is any subset of . Two extreme cases get names of their own: the empty relation (nothing is related to anything), and the universal relation (everything is related to everything).
| Property | Definition |
|---|---|
| Reflexive | for every |
| Symmetric | |
| Transitive | and |
| Equivalence | Reflexive and symmetric and transitive |
Worked, mirroring the textbook's own Example 5. on the set of integers . Reflexive since divides . Symmetric since . Transitive since , so if divides both and it divides their sum. So is an equivalence relation — and it splits into exactly two equivalence classes: the even integers and the odd integers .
That splitting isn't a coincidence of this one example. Any equivalence relation on a set partitions into disjoint equivalence classes whose union is all of — every element sits in exactly one class, and two elements are related exactly when they're in the same class.
This is a two-way street: an equivalence relation gives you a partition, and a partition (like splitting into "multiples of 3," "one more than a multiple of 3," "two more than a multiple of 3") gives you back an equivalence relation.
The two extreme relations, classified. The universal relation is an equivalence relation — it is trivially reflexive, symmetric and transitive, since every pair is present. The empty relation is symmetric and transitive vacuously (there are no pairs to violate the conditions), but it is not reflexive unless itself is empty, because is missing for every .
This asymmetry is a favourite exam question, and the reasoning is worth holding onto: symmetry and transitivity are conditional statements, so having no pairs satisfies them automatically, whereas reflexivity demands that certain pairs actually be present.
Why the three properties are independent. No two of them imply the third, and Exercise 1.1 is built almost entirely on constructing examples that have some but not others.
| Example on | R | S | T |
|---|---|---|---|
| yes | no | yes | |
| no | yes | no | |
| no | no | yes |
Checking the second row is instructive: it is symmetric, but transitivity would require to be present (from and ), and it is not.
Counting equivalence classes. For the relation " is divisible by " on , there are exactly equivalence classes, one for each possible remainder . The example above with giving the evens and the odds is the smallest case.
4. Types of functions
| Type | Condition | Book's own test |
|---|---|---|
| One-one (injective) | Distinct inputs give distinct outputs | |
| Onto (surjective) | Range Co-domain | Every in the co-domain has some with |
| Bijective | One-one and onto | Both hold together |
A quirk worth knowing for finite sets specifically: for on a finite set , one-one and onto are the same condition. If is onto but not one-one, two inputs would collapse onto one output, leaving too few images to cover all of — a contradiction. If is one-one but not onto, the images would fill fewer than slots while there are inputs demanding distinct images — also a contradiction.
This shortcut fails immediately for infinite sets: , is one-one but not onto (no odd number is ever hit).
Worked, mirroring the textbook's own Example 12. defined by if is odd, if is even. Every odd input and its paired even input map to each other's neighbours, so no two inputs share an image (one-one), and every natural number appears as someone's image (onto) — bijective, even though the formula looks asymmetric at first glance.
5. Composition and invertibility
For and , the composition is defined by — apply first, then .
A function is invertible if there exists with and (the identity functions). The single most useful fact in this section:
This is what makes invertibility checkable without ever constructing the inverse: prove one-one and onto, and invertibility follows for free.
Properties of composition. Composition is associative — — so a chain of three functions needs no brackets. It is not commutative: and are generally different functions, and may not even both be defined.
For the composition to make sense at all, the co-domain of the inner function must match the domain of the outer one. Checking this before computing is the first step in every composition question.
Composition preserves bijectivity. If and are both one-one, so is ; if both are onto, so is . Hence the composition of two bijections is a bijection, and therefore invertible.
The reversal law. When and are both invertible:
Note the order reverses. The intuition is the everyday one: to undo "put on socks, then shoes," you take off the shoes first. Writing instead is a standard error.
Inverting twice returns the original, , and the inverse of a bijection is itself a bijection.
The inverse is unique. If and both invert , then . This is why the notation is legitimate — there is only one thing it can mean.
A warning about notation. The symbol means the inverse function here, not the reciprocal . The two are unrelated, and the resemblance causes real confusion in later chapters.
Worked, mirroring the textbook's own Example 17. , , where . Solving for gives , so define . Checking both compositions: , and . Both identities hold, so is invertible with .
Summary
- A relation on is a subset of ; reflexive, symmetric, transitive are independent properties, and all three together make an equivalence relation.
- An equivalence relation on partitions into disjoint equivalence classes covering all of .
- One-one: distinct inputs, distinct outputs. Onto: every co-domain element is hit. Bijective: both.
- For a function from a finite set to itself, one-one and onto are equivalent conditions — this fails for infinite sets.
- : apply the inner function first.
- is invertible if and only if is bijective; when it is, solve for to get .
- The universal relation is an equivalence relation; the empty relation is symmetric and transitive vacuously but not reflexive (unless is empty).
- Reflexive, symmetric and transitive are mutually independent — no two imply the third, which is what Exercise 1.1 is built on.
- " divisible by " on has exactly equivalence classes, one per remainder.
- Composition is associative but not commutative, and needs the inner co-domain to match the outer domain.
- The composition of two bijections is a bijection; , with the order reversed.
- The inverse is unique, , and means the inverse function, never the reciprocal .
- "Binary operations" is named in the book's introduction and summary paragraphs but has no actual teaching section, example, or exercise question in the current edition — a leftover reference, not something to revise.
