Mathematics is full of connections: this number divides that one, this student sits in that house, this input gives that output. This chapter gives those connections precise names and rules.
A relation is a list of pairs that you choose. You pick them from all the pairs that two sets can make.
Take two sets A and B. A relation R from A to B is any collection of the pairs in A × B that you choose. A relation in A is a subset of A × A.
The Cartesian product A × B is every possible ordered pair: the first element from A, the second from B.
So (a, b) ∈ R is written a R b. Read a R b as “a is related to b”.
A = students of Class 12, B = students of Class 11. Every pair (Priya, Arjun) where Priya is older than Arjun goes in R.
Pairs of neighbours are in R. People from different localities are not.
Mathematically we don't need a story behind the pairs. Any subset of A × B counts as a relation, even a random one like {(1, 4), (3, 2)}.
Think of A × B as a class photo with every possible handshake. A relation is simply a list of which handshakes actually happened. Order matters: (2, 3) means "2 is related to 3", which is different from (3, 2).
For a relation in a set A (a subset of A × A), there are two extreme choices. Together they are called the trivial relations.
No element of A is related to any element. All 16 pairs of A × A (A = {1, 2, 3, 4}) stay empty.
A = {1, 2, 3, 4}, R = {(a, b) : a − b = 10}. No two numbers in A are 10 apart, so R = φ.
Every element is related to every element, including itself. All 16 pairs are filled.
R′ = {(a, b) : |a − b| ≥ 0}. A distance is never negative, so every pair qualifies.
A = all students of a boys' school. R = {(a, b) : a is sister of b}, R′ = {(a, b) : heights of a and b differ by less than 3 m}.
These three tests are the heart of the chapter. Each one asks a simple question about the arrows of a relation.
Take a relation R in a set A. Picture each element of A as a dot and each pair (a, b) in R as an arrow from a to b. A pair (a, a) is a loop.
Every dot needs its own loop. Missing even one loop breaks it.
✓ "is congruent to": every triangle is congruent to itself.
✗ "is perpendicular to": no line is perpendicular to itself.
If a points to b, then b must point back to a.
✓ "is a classmate of": if Riya is Sam's classmate, Sam is Riya's.
✗ "is father of": the father of Sam is not Sam's son.
Whenever you can walk a → b → c, the direct arrow a → c must also be there.
✓ "is taller than": if A is taller than B and B than C, then A is taller than C.
✗ "is a friend of": your friend's friend may be a stranger.
Tap a check card to highlight its problem in the diagram. Rose arrows are the ones causing trouble. Dashed rose arrows are the ones that are missing.
"Transitive" can be true with nothing to check. In Exercise 1.1 Q1(ii), R = {(1, 6), (2, 7), (3, 8)}. For transitivity we need a chain (a, b), (b, c). But 6, 7 and 8 never appear first in any pair, so there is no chain at all. No chain means nothing can break the rule, so R is transitive. Try b = a + 1 in the lab: that one does have chains, and they break it.
Likewise, the empty relation is symmetric and transitive (nothing to fail), but it is not reflexive unless A itself is empty, because the loops are required.
Each proof follows the same pattern: check the three definitions one by one. To prove a property, argue for every case. To disprove it, one counterexample is enough.
T = all triangles in a plane, R = {(T₁, T₂) : T₁ is congruent to T₂}.
L = all lines in a plane, R = {(L₁, L₂) : L₁ is perpendicular to L₂}.
A = {1, 2, 3}, R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}.
R = {(a, b) : 2 divides a − b} on the integers ℤ.
When a relation passes all three tests, it sorts the set into separate groups, like socks sorted into drawers.
A relation with all three properties is an equivalence relation. It behaves like “is the same as, in some way”.
The equivalence class [a] is the class of everything related to a.
The classes never overlap, and together they fill A.
With n = 2 you get Example 5: evens and odds. With n = 3 you get the textbook's three classes A₁, A₂, A₃. Each colour is one drawer, and every integer lands in exactly one.
All elements of Ai are related to each other: 4, 10 and −2 all leave remainder 1 on division by 3.
No element of Ai is related to any element of Aj for i ≠ j. An even number is never related to an odd one.
The drawers are disjoint and together hold the whole set. This kind of split is called a partition.
A = {1, 2, 3, 4, 5, 6, 7}, R = {(a, b) : both a and b are odd, or both are even}.
It works backwards too. Start with any partition and define "a R b if they are in the same piece". That is always an equivalence relation.
The textbook splits ℤ into:
Sort a pile of socks by colour. Each sock matches itself (reflexive). If sock A matches sock B, then B matches A (symmetric). If A matches B and B matches C, then A matches C (transitive). The colour piles are the equivalence classes. Every sock ends up in exactly one pile.
Decide for yourself first, then open the answer. Every answer shows the reasoning, not just the verdict.
R = {(1, 3), (2, 6), (3, 9), (4, 12)}, since y = 3x must stay within 14.
(1, 1) ∉ R. (1, 3) ∈ R but (3, 1) ∉ R. (1, 3), (3, 9) ∈ R but (1, 9) ∉ R.
R = {(1, 6), (2, 7), (3, 8)}. (1, 1) ∉ R, and (6, 1) ∉ R.
No second element (6, 7, 8) appears as a first element, so there is no chain (a, b), (b, c) to test. The rule is never broken, so R is transitive.
Every x divides itself. 2 divides 4 but 4 doesn't divide 2. If x | y and y | z, then y = kx and z = my = mkx, so x | z.
The difference of two integers is always an integer, so this is the universal relation on ℤ, and therefore an equivalence relation.
Nobody is 7 cm taller than themselves. If x is 7 cm taller than y, y is 7 cm shorter. And 7 cm + 7 cm makes x 14 cm taller than z, not 7.
Compare (a) "work at the same place" and (b) "live in the same locality": both are equivalence relations.
Reflexive fails at a = ½: is ½ ≤ ¼? No.
Symmetric fails: 1 ≤ 2² = 4, but 2 ≤ 1² = 1 is false.
Transitive fails: 3 ≤ 2² and 2 ≤ 1.5² = 2.25, but 3 ≤ 1.5² = 2.25 is false.
a ≤ a always. 1 ≤ 2 but 2 ≰ 1. If a ≤ b ≤ c then a ≤ c. Load "a ≤ b" in the lab to see this on {1, 2, 3, 4}.
Similarity is reflexive, symmetric and transitive. T₃'s sides are exactly 2 × T₁'s (6 : 8 : 10 = 3 : 4 : 5), so T₁ R T₃. T₂ has ratio 5 : 12 : 13, which matches neither.
Taking "every line is parallel to itself", the relation is reflexive, symmetric and transitive. Parallel lines share a slope, so the class of y = 2x + 4 is every line y = 2x + c, c ∈ ℝ.
A function gives every input exactly one arrow out. Now we look at where the arrows land.
A relation where every input in X has exactly one arrow out. The new questions are about the arrival side, Y.
Do arrows ever land on the same element? If never, f is one-one.
Does every element of Y get at least one arrow? If yes, f is onto.
No two arrows share a landing spot, but e and f in X₂ get nothing.
1 and 2 both land on b. And a, e, f are never reached.
Each of a, b, c is reached, but a is reached twice.
Every element of X₄ gets exactly one arrow. This is a bijection.
| Type | Other name | Definition | Arrow picture | Everyday picture |
|---|---|---|---|---|
| One-one | Injective | f(x₁) = f(x₂) ⇒ x₁ = x₂ | No landing spot receives two arrows | Roll numbers: no two students share one |
| Many-one | Not injective | Some x₁ ≠ x₂ with f(x₁) = f(x₂) | Two arrows meet at one spot | Birthday month: many students share March |
| Onto | Surjective | For every y ∈ Y there is an x with f(x) = y. Equivalently, range = Y | Every spot in Y receives an arrow | Every seat in the hall is occupied |
| Bijective | One-one correspondence | One-one and onto | Exactly one arrow into every spot | Each guest gets exactly one of the chairs, and no chair is empty |
Same formula, different sets, different answers. 2x is a bijection on ℝ but not on ℕ (Examples 8 and 9). The domain and codomain are part of the function.
f : A → ℕ, where A = the 50 students of Class X and f(x) = roll number of x.
f : ℕ → ℕ, f(x) = 2x.
f : ℝ → ℝ, f(x) = 2x.
f : ℕ → ℕ with f(1) = f(2) = 1 and f(x) = x − 1 for x > 2.
f : ℝ → ℝ, f(x) = x².
f : ℕ → ℕ, f(x) = x + 1 if x is odd, x − 1 if x is even.
Examples 13 and 14: for a function from a finite set to itself, one-one and onto always come together.
If two inputs shared an output, only two outputs would be used, leaving one of the three empty. That contradicts onto.
Three inputs with three different outputs must use all three elements of {1, 2, 3}.
2x on ℕ is one-one but not onto (Example 8). Example 10's function is onto but not one-one. With infinitely many seats you can fill a seat for every guest and still have seats left over. That surprising behaviour is a key difference between finite and infinite sets.
Use the proof recipes above. For "not" answers, a single counterexample is all you need.
1/x₁ = 1/x₂ ⇒ x₁ = x₂. For any y ≠ 0, x = 1/y works.
With domain ℕ it stays one-one, but it's not onto: 2 ∈ ℝ* would need x = ½ ∉ ℕ.
(i) ℕ → ℕ, x²: one-one, not onto (2 is not a square). (ii) ℤ → ℤ, x²: neither ((−1)² = 1²). (iii) ℝ → ℝ, x²: neither. (iv) ℕ → ℕ, x³: one-one, not onto. (v) ℤ → ℤ, x³: one-one, not onto (2 is not a cube).
All five are in the horizontal line test above. Check them there.
[1.2] = [1.7] = 1. Outputs are always integers, so 0.7 is never reached.
f(1) = f(2) = 1. The range is only {−1, 0, 1}, so 2 is never reached.
(i) Bijective. 3 − 4x₁ = 3 − 4x₂ ⇒ x₁ = x₂. For any y, x = (3 − y)/4.
(ii) Neither. f(1) = f(−1) = 2, and 1 + x² ≥ 1, so 0 is never reached.
f(1) = 1 = f(2), so it is not bijective. Any m is reached from 2m, so it is onto.
Cross-multiplying (x₁ − 2)(x₂ − 3) = (x₂ − 2)(x₁ − 3) simplifies to x₁ = x₂.
Solve y = (x − 2)/(x − 3): x = (3y − 2)/(y − 1), which is defined because y ≠ 1, and never equals 3.
Feed the output of one function straight into another. The two machines together make one new function.
For f : A → B and g : B → C, the combined machine is g∘f. Read it as “g of f”. The textbook writes it as gof.
f acts first, then g.
The range of f needs to sit inside the domain of g, so that g can take every output of f.
Result: g∘f = {(2, 7), (3, 7), (4, 11), (5, 11)}. Note that 9 and 15 are never used on this route.
f(x) = cos x, g(x) = 3x², both ℝ → ℝ.
Machine f: "put on socks". Machine g: "put on shoes".
Some functions can be run backwards: a second function undoes the first. That undo function is called the inverse.
f : X → Y is invertible if there is a function g : Y → X that undoes it like this. That g is the inverse, f−1. Here IX is the identity: IX(x) = x.
f−1 reverses every arrow of f. The two cards below show why both conditions are needed.
The −1 means “undo f”, not “one over f”.
For x², both −2 and 2 go to 4. Reversed, 4 would need two outputs, and a function allows only one.
For 2x on ℕ, the number 3 is never reached. The reverse machine would have no answer for input 3.
Blue: f. Orange: f−1. Grey dashes: the mirror y = x.
f : ℕ → Y, f(x) = 4x + 3, where Y = {7, 11, 15, 19, …} is exactly the set of values 4x + 3 takes.
Some of the trickiest exam questions ask you to count relations or functions. Drawing every case is the safest way to count.
A one-one function here is just a reordering (a permutation) of 1, 2, 3. There are 3 choices for f(1), then 2 left for f(2), then 1 for f(3): 3 × 2 × 1 = 3! = 6.
By Example 13, each of these is also onto. So the number of onto functions from {1, 2, …, n} to itself is n! (Miscellaneous Exercise Q4).
On A = {1, 2, 3}, how many relations contain (1, 2) and (2, 3) and are reflexive and transitive but not symmetric?
How many equivalence relations on {1, 2, 3} contain (1, 2) and (2, 1)?
Iℕ(x) = x is onto. But (Iℕ + Iℕ)(x) = 2x is not onto, because 3 is never reached.
On [0, π/2], sin x and cos x are each one-one. But (sin + cos)(0) = 0 + 1 = 1 and (sin + cos)(π/2) = 1 + 0 = 1.
These are the multiple-choice questions from the chapter's exercises. Tap an option to see if you're right and why.
A relation from A to B is any subset of A × B. Empty: R = φ. Universal: R = A × A.
Reflexive: every loop (a, a). Symmetric: every arrow has a return arrow. Transitive: every two-step path has a shortcut.
All three together make an equivalence relation, which splits the set into non-overlapping equivalence classes [a].
One-one: f(x₁) = f(x₂) ⇒ x₁ = x₂. Onto: range = codomain. Bijective: both.
For a finite set X, f : X → X is one-one exactly when it is onto. This fails for infinite sets.
(g∘f)(x) = g(f(x)), usually ≠ f∘g. A function has an inverse exactly when it is bijective.
From the textbook's historical note: the word "function" changed meaning over about 250 years.
Uses "function" for a power xn while studying curves.
A quantity built from others by repeated algebraic operations.
Quantities varying along a curve, such as slope. Later, the phrase "function of x".
First writes φx for a function of x.
Makes symbols like f, F, φ, ψ standard.
Uses notation such as f(x) and F(x).
Gives the definition used until set theory arrived.
Set theory makes today's "set of ordered pairs" definition possible.
Each textbook example is a small animated story. Press Next step (or Play) and watch the picture build up the solution. Under the controls, each step is explained in detail, with links to the exact basics it uses. After reading a basic, press ← Back to return to the same step. Many examples also have a Try it panel for testing your own numbers.
Watch each property being tested arrow by arrow, square by square.
See arrows land, collide, or miss. That is one-one and onto, made visible.
Follow values through machines, forwards and backwards.
The harder ones, including counting problems and combined relations, unpacked visually.
Social apps, clocks, hospitals, car parks, online shops and secret codes all run on relations and functions. Here are seven scenes where the chapter shows up.
A clock can't tell 2, 14 and 26 hours apart: the hour hand points to 2 every time. "Hours a and b look the same on the clock" means 12 divides a − b. That is an equivalence relation with 12 classes.
Each column is one equivalence class. Every hour in the highlighted column puts the hand in the same place.
Days that are a multiple of 7 apart fall on the same weekday. So to jump N days ahead, only the remainder of N ÷ 7 matters.
Calendars, cricket match schedules and timetables all use this "remainder" equivalence. It is the same as the lesson's "n divides a − b", with n = 7.
Take a class of 16 students. "Has the same blood group as" is an equivalence relation, so it sorts everyone into drawers. "Can donate blood to" is a different relation on the same set, and it is not symmetric.
Result: an equivalence relation. The four groups O, A, B and AB are its equivalence classes. They don't overlap, and together they include every student.
Simplified: real transfusions also match the Rh (+/−) factor and other tests, and doctors make the final decision. Relations that are reflexive and transitive but not symmetric are called orders. You'll meet them in higher maths.
Every car must get exactly one slot, so "car → slot" is a function. Whether it can be one-one (no sharing) or onto (no empty slots) depends only on how many cars and slots there are.
Every car can have its own slot, but some slots must stay empty.
Pigeonhole principle: 6 cars in 5 slots means at least two cars must share.
For equal finite sets, one-one and onto come together. That's Examples 13 and 14 from the lesson.
A shop applies two functions to your price: a ₹100 coupon, f(x) = x − 100, and 18% GST, g(x) = 1.18x. The order you compose them in changes the bill.
g∘f(x) − f∘g(x) = (1.18x − 118) − (1.18x − 100) = −18. So f∘g always costs ₹18 more, whatever the price. Composition is not commutative.
But converting ₹ → $ → € in either order gives the same answer, because two multiplications do commute. It's mixing a shift (− 100) with a scaling (× 1.18) that makes the order matter.
The Caesar cipher shifts every letter k places along the alphabet. It is a bijection on the 26 letters, so it has an inverse: shift back by k. That's how your friend decodes the message.
Outer ring: plain letter. Inner ring: its code. Every letter has exactly one partner and none is left over, so the cipher is one-one and onto.
Websites store a hash of your password: a function built to be many-one, so it cannot be reversed. Here is a toy hash: add up letter positions (A = 1, …, Z = 26) and keep the last digit.
CAT and ACT give the same hash, so from the hash alone you can't tell which word it came from. No inverse exists, and that's exactly the point. Real hashes (such as SHA-256) are far more complex, but the idea is the same.
Slide to −40: both scales read the same. That's where the graph of f crosses the mirror line y = x from the lesson.
Decide for each rule: is it a function? If yes, is it one-one, onto, or both? Then tap the card to check.
Every question that asks you to show, check or find something has an animated walkthrough here; the multiple-choice questions are in the Lesson’s self-check. Pick a question from the chips above each player. Press Play to watch it solved, or step through with Next. Small sets are drawn as arrows or grids; functions on ℝ get a graph with a horizontal-line test; relations described in words get three property cards that turn green or red.
For each relation, check the three properties one at a time: a loop on every dot, a return arrow for every arrow, a shortcut for every chain. (Q15–Q16 are in the self-check quiz.)
Look for two inputs sharing an output, and for an output nobody reaches. Then back the picture up with algebra. (Q11–Q12 are in the quiz.)
A squeezing function, a cube, the subset relation, counting onto functions, and two formulas that turn out to be the same function. (Q6–Q7 are in the quiz.)
Relations and functions are built from a few older ideas: sets, pairs, even and odd numbers, and the difference between proving something and disproving it. Here each one is explained from its roots: not just what it is, but why it is defined that way. Every example and exercise links back here exactly where you need it, and a button takes you straight back to the problem.
A set is a collection of distinct objects, called its elements. Order and repetition inside a set do not matter.
Read it as “a is an element of A”.
The same elements in any order make the same set.
The number sets used all through this chapter
ℝ includes fractions and decimals like ½ and √2.
Sometimes order is the whole point. "Ravi is the father of Arjun" is not the same statement as "Arjun is the father of Ravi". So we use an ordered pair (a, b), where a is first and b is second. (1, 2) ≠ (2, 1), even though the sets {1, 2} and {2, 1} are equal.
The Cartesian product A × A is the set of all ordered pairs (a, b) with a and b from A. If A has n elements there are n choices for a and n choices for b, so A × A has n × n = n² pairs. Laid out as a grid, row a and column b meet at the square (a, b).
An integer is even when it is 2 times an integer (…, −4, −2, 0, 2, 4, …) and odd otherwise. Zero is even, because 0 = 2 × 0. Being even or odd is called a number’s parity.
"n divides m" means m = n × k for some integer k: m is a multiple of n. So "2 divides a − b" says the gap between a and b is even, and "3 divides a − b" says the gap is a multiple of 3. Negative gaps count too: −6 = 3 × (−2).
Divide any integer by n and the remainder is one of 0, 1, …, n − 1. Place the numbers round a clock with n positions: 0, 1, 2, … and then back to the start. Two numbers sit at the same position exactly when their gap is a multiple of n. That is why "n divides a − b" always sorts the integers into n groups.
In everyday speech a relation is a link between two things: "is a sister of", "is taller than", "divides". Mathematics strips this down to its essence. A relation R on a set A is simply a subset of A × A: the collection of pairs (a, b) for which the link holds. We write (a, b) ∈ R, or a R b.
Shade the chosen squares of the A × A grid, or draw each chosen pair as an arrow a → b between dots. The grid is good for spotting mirror patterns; the arrows are good for following chains.
Choosing no squares gives the empty relation φ: nothing is related to anything. Choosing every square gives the universal relation A × A: everything is related to everything. Every other relation lies in between.
Some links behave like "equals", and some don’t. Three simple questions capture the difference.
(a, a) ∈ R for every a. "Has the same birthday as" is reflexive: you share your own birthday. "Is taller than" is not: nobody is taller than themselves. In the grid, the whole diagonal is shaded; in arrows, every dot has a loop.
(a, b) ∈ R ⇒ (b, a) ∈ R. "Is a classmate of" is symmetric. "Is the father of" is not. In the grid, the picture is its own mirror image across the diagonal; in arrows, every arrow has a return arrow.
(a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. "Is older than" is transitive. "Is a friend of" usually is not: your friend’s friend may be a stranger. In arrows, every two-step path a → b → c has the direct arrow a → c.
Each property is a promise about every element or every pair. One case that breaks the promise shows the property fails. To show it holds, you need an argument that covers all cases.
Transitivity says "if a → b and b → c, then a → c". If a relation has no two-step path at all, the "if" never happens, so the promise is never broken. Such a relation counts as transitive. Mathematicians say it is true vacuously. For example, R = {(1, 6), (2, 7), (3, 8)} is transitive.
Reflexive: everyone is linked to themselves. Symmetric: every link is two-way. Transitive: linked to someone who is linked means directly linked. A relation with all three is an equivalence relation, and it behaves like "is the same as" in some respect.
Sort socks into drawers by colour. "Is in the same drawer as" is reflexive (every sock is in its own drawer), symmetric and transitive. And every equivalence relation works like this: the equivalence class [a] is the drawer holding a, that is, everything related to a. Different drawers never overlap, and together they hold everything.
A function f : X → Y takes each element x of the domain X and gives back exactly one element f(x) of the codomain Y. The outputs actually produced form the range, which may be smaller than the codomain. A function is a special relation: every x appears in exactly one pair (x, f(x)).
Feed the output of f into g and you get the composition g∘f: (g∘f)(x) = g(f(x)), f first. To undo a machine you run its steps backwards in reverse order, as in socks and shoes. A machine can only be undone if it never sends two inputs to the same output and it reaches every output. That is the next step.
f(x₁) = f(x₂) forces x₁ = x₂. Like seats in an exam hall: no two students share a seat. On a graph, every horizontal line meets it at most once.
For every y in the codomain there is some x with f(x) = y. No seat is left empty. On a graph, every horizontal line at a codomain height meets it at least once.
Both together make f bijective: a perfect pairing of inputs and outputs, which is exactly when f can be undone (has an inverse).
Most questions in this chapter say "show that R is reflexive" or "show that f is not onto". These are two different jobs.
Let x be any element, and reason using only what every element has. Checking 5 cases, or 500, is not a proof: case 501 might fail.
One concrete case where the statement fails is enough. "x² ≥ x for all real x" is false: x = ½ gives ¼ < ½.
"P if and only if Q" (P ⇔ Q) is two statements: P ⇒ Q and Q ⇒ P. You must prove both directions.
When you make one choice and then another, multiply the number of ways. This is the multiplication principle.
If a first choice can be made in m ways and, after it, a second choice in n ways, the pair can be made in m × n ways. Each first choice starts its own branch of n options.
When the choices shrink by one each time, the product is called n factorial, written n!.
Each game is built from real problems in this chapter. The rules of the game are the definitions, the levels are the book’s examples and exercises, and the winning move is the answer. Play a level, then open the worked solution: you will find you already know it.
Numbers fall one at a time. Drop each into the basket of numbers it is related to, or into an empty basket if it is related to none of them. When the level ends, the baskets you filled are the equivalence classes.
To decide where a number goes you compare it with one number already in a basket. That only works because the relation is an equivalence relation: if 5 R 1 and 1 R 3, transitivity guarantees 5 R 3, so checking one member of a basket checks them all.
Watch outIn Example 5 the set is ℤ, so negatives and 0 fall too. 0 is even, and −3 − 1 = −4 is divisible by 2, so −3 goes with 1.
Three relations from the book appear as arrow diagrams. For each property you rule “holds” or “fails”. A “fails” ruling must be proved by tapping the evidence: a dot with no loop, an arrow with no way back, or two arrows in a row whose shortcut is missing.
“Holds” is a promise about every case, so the game checks them all for you, one after another. “Fails” needs only one counterexample, so you must point to it. That is exactly how Example 4 is written: one missing pair for each “not”.
The maths behind itReflexive: (a, a) ∈ R for every a ∈ A. Symmetric: (a, b) ∈ R ⇒ (b, a) ∈ R. Transitive: (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R. A chain like 1 → 2 → 1 counts too: it needs the loop (1, 1).
Choose an input n and fire: the dart pops balloon f(n). A balloon hit by two different inputs proves the function is not one-one. A balloon that no input can ever hit proves it is not onto. Then give your verdict on both.
One-one means no balloon is shared. Onto means no balloon is left out. Bijective means both: every balloon is hit by exactly one input.
Watch outThe screen shows only balloons 1 to 12, but inputs go on for ever. In Exercise 1.2 Q9 balloon 9 looks unreachable if you only try small inputs, yet f(17) = 9. Before saying “never”, solve f(n) = y.
The 3 × 3 board holds every ordered pair of {1, 2, 3}. Switch pairs on and off; three lights show whether your relation is reflexive, symmetric and transitive. Each new relation that fits the question becomes a trophy. Then answer the book’s multiple-choice question.
Each property forces pairs. Reflexive forces the three loops, symmetric forces the mirror of every pair. Start from what is forced, then try one extra pair and watch how many others it drags in. That is the whole method of Example 24.
Going deeperThe bonus level counts all equivalence relations on {1, 2, 3}: there are 5, one for each way of sorting three objects into baskets. These counts are the Bell numbers 1, 2, 5, 15, 52, …
Leave your email and we will write when a new chapter or a new set of worked solutions is ready. That is all we use it for, and you can ask to be taken off the list at any time.
You are on the list. We will email you when new chapters are added, and for nothing else.