Sorted Into Buckets

Consider the relation 'has the same birthday month as' on a set of people. It is reflexive: everyone shares a birthday month with themselves. It is symmetric: if person A shares a birthday month with B, then B shares one with A. It is transitive: if A shares a month with B, and B shares a month with C, then A shares that same month with C. Contrast this with 'is taller than' on the same set: it is NOT reflexive (nobody is taller than themselves), NOT symmetric (if A is taller than B, B is certainly not taller than A), but it IS transitive (if A is taller than B, and B is taller than C, then A is taller than C). A relation can have any combination of these three properties, independently of the others.

A relation that is reflexive, symmetric, AND transitive all at the same time earns a special name: an equivalence relation. A genuinely important example lives inside ordinary fractions: define a/b as equivalent to c/d exactly when ad = bc (this is exactly the cross-multiplication rule used to check if two fractions are equal, like 1/2 and 2/4). This relation is reflexive (a/b is equivalent to itself, since ab=ba), symmetric (if ad=bc then cb=da, so c/d is equivalent to a/b too), and transitive (if a/b~c/d and c/d~e/f, careful algebra confirms a/b~e/f as well). This is not just an analogy: it is literally how a fraction's true identity, its 'value', is formally defined in mathematics: as an entire equivalence class of equal-looking fractions, not any single one of them.

Define a relation on the integers: a is related to b exactly when 4 divides (a-b), meaning a and b leave the same remainder when divided by 4. This is a genuine equivalence relation. It sorts every integer into exactly one of 4 buckets: [0] = {..., -4, 0, 4, 8, ...}, [1] = {..., -3, 1, 5, 9, ...}, [2] = {..., -2, 2, 6, 10, ...}, and [3] = {..., -1, 3, 7, 11, ...}. Every integer belongs to exactly one bucket (the buckets are disjoint), and together the four buckets cover every integer there is (their union is all of Z). This is exactly what any equivalence relation does to its set: it partitions it into equivalence classes, groups where everything inside a group relates to everything else inside it, and nothing relates across groups.

A function f is one-one (or injective) if distinct inputs always produce distinct outputs: no two different inputs ever share an output. A function f is onto (or surjective) if every element of the codomain gets hit by something: nothing in the target set is left unused. These are genuinely separate questions. f(x)=x+5 from Z to Z is BOTH one-one and onto: every integer shifts to a unique new integer, and every integer is reached by shifting some other integer by 5. g(x)=2x from Z to Z is one-one (different inputs double to different outputs) but NOT onto (odd numbers like 3 are never twice an integer). h(x)=x^2 from Z to Z is NEITHER one-one (h(3)=h(-3)=9) NOR onto (-4 is never a perfect square). And k(x)=|x| from Z to the non-negative integers is onto (every non-negative integer is some number's absolute value) but NOT one-one (k(3)=k(-3)=3).

A function that is both one-one and onto is called bijective. Consider f: {1,2,3,4} to {1,2,3,4} defined by f(1)=3, f(2)=4, f(3)=1, f(4)=2: since all four outputs (3,4,1,2) are distinct, f is automatically one-one, and because it maps a FINITE set to itself, one-one automatically forces onto as well (there is nowhere else for the fourth output to 'overflow' to). This shortcut is special to finite sets mapping to themselves: it completely fails for infinite sets, since g(x)=2x from Z to Z is one-one without being onto at all, showing that on an infinite set, one-one and onto genuinely must be checked separately.

A function f from X to Y is invertible if there exists a function g from Y back to X that perfectly undoes it in both directions: g(f(x))=x for every x, and f(g(y))=y for every y. The key theorem is this: f is invertible exactly when f is bijective, no more and no less. Consider f: N to Y defined by f(x) = 3x+7, where Y is exactly the set of values this rule produces. Given any y in Y, solving y=3x+7 for x gives x=(y-7)/3, so define g(y)=(y-7)/3. Checking: g(f(x)) = g(3x+7) = ((3x+7)-7)/3 = x, and f(g(y)) = f((y-7)/3) = 3 times (y-7)/3 + 7 = (y-7)+7 = y. Both directions undo each other perfectly, confirming f is invertible with inverse g.

The composition of f and g, written gof, is defined by gof(x) = g(f(x)): apply f first, then feed the result into g. Order matters enormously. Let f(x)=x+2 and g(x)=3x. Then gof(x) = g(f(x)) = g(x+2) = 3(x+2) = 3x+6, while fog(x) = f(g(x)) = f(3x) = 3x+2. Since 3x+6 is not the same expression as 3x+2, gof and fog are genuinely different functions. This is exactly why the invertibility theorem is stated so carefully with BOTH conditions, gof equal to the identity on X AND fog equal to the identity on Y: undoing a function correctly requires getting the order of composition exactly right in both directions, not just one.