Relations and FunctionsTypes of Relations

A relation in a set A is a subset of . So two relations sit at the very ends of the scale: the empty set , which contains no pair at all, and itself, which contains every pair there is.

Take and the relation . The largest difference between two elements of A is 3104, so no pair passes the test and R is the empty set.

Now take . A modulus is never negativepositivezero, so every pair passes and . These two extreme relations get names of their own.

Both are sometimes called trivial relations — not because they are unimportant, but because they carry no information. One says "nothing is related to anything", the other "everything is related to everything", so neither can tell two elements of A apart. Every interesting relation lies somewhere between them.

Example 1 : Let A be the set of all students of a boys' school. Show that the relation R in A given by R = {(a, b) : a is a sister of b} is the empty relation and R′ = {(a, b) : the difference between the heights of a and b is less than 3 metres} is the universal relation.

Solution : In a boys' school, no student can be the sister of any student. So no pairevery pairexactly one pair belongs to R, and is the empty relation.

No two people differ in height by 3 metres or more, so every pair of students belongs to R′. Hence is the universalemptyidentity relation.

Quick check. In a girls' hostel H, which of these relations in H is the empty relation?

Nobody in a girls' hostel is anybody's brother, so that relation is empty — the hostel version of Example 1.

Three Tests for Any Relation

Think of the relation "is the same height as" among the students of your class. Three things are true of it without measuring anyone: everyone is the same height as themselves; if Aman is the same height as Riya, then Riya is the same height as Aman; and if Aman matches Riya and Riya matches Kabir, then Aman matches Kabir. Those three facts have names, and they are the three tests every relation in this chapter will face.

On a grid of , each test has a picture. Reflexive: the whole diagonal, , is filled. Symmetric: the filled squares are a mirror image of themselves across that diagonal. Transitive: whenever and are filled, the shortcut is filled too.

An equivalence relation is mathematics' way of saying "these two things are not identical, but for our purpose they count as the same" — just like "is the same height as".

The relation lab. The grid is a relation in ; row a, column b is the pair . It starts as the relation of Example 4 below. Tap a square to put that pair in or take it out. The three tests update as you go, and a red outline marks the pair a test is missing. Build all four relations in the list.

Testing Relations

Example 2 : Let T be the set of all triangles in a plane, and let R be the relation in T given by . Show that R is an equivalence relation.

Solution : R is reflexive, since every triangle is congruent to itselfits mirror imageevery other triangle.

If , then is congruent to , so is congruent to and . Hence R is symmetrictransitiveempty.

If and are in R, then and , so and . So R is transitive too, and R is an equivalence relation.

Example 3 : Let L be the set of all lines in a plane and R the relation in L defined as . Show that R is symmetric but neither reflexive nor transitive.

Solution : A line is never perpendicular to itselfa line that crosses itany other line, so and R is not reflexive.

R is symmetric: if is perpendicular to , then is perpendicular to .

R is not transitive: if and , then is parallelperpendicular to . So and , but .

Example 4 : Show that the relation R in the set given by is reflexive but neither symmetric nor transitive.

Solution : and all lie in R, so R is reflexivesymmetricempty.

R is not symmetric, because but is not in Ris in R.

R is not transitive, because and , but (1, 3)(3, 1)(2, 2) is not in R.

Example 5 : Show that the relation R in the set Z of integers given by

is an equivalence relation.

Solution : For every integer a, 012a, and 2 divides 0. So R is reflexive.

If , then 2 divides , so 2 also divides . Hence and R is symmetrictransitiveempty.

If and , then and for some integers m, n. Adding,

,

which is evenodd. So , R is transitive, and R is an equivalence relation in Z.

Notice that each test used exactly one arithmetic fact: 0 is even; ; and even plus even is even.

Speed Round: Which Test Fails?

Every relation below fails at most one of the three tests. Find the one that fails — or say that all three hold. After each answer you will see the reason.

Get five right to move on.

Sorting Into Classes

E is called the equivalence class containing 0, written , and O is the equivalence class containing 1, written . Note that , while and for every — a class can be named after any of its members.

Now you sort. Use the relation "3 divides " instead. Drop each integer into the bin of the number it is related to.

What you just did works for every equivalence relation, not only these two. Given an arbitrary equivalence relation R in an arbitrary set X, R divides X into mutually disjoint subsets , called partitions or subdivisions of X, such that

(i) all elements of are related to each other, for all i;

(ii) no element of is related to any element of , ;

(iii) and , .

The subsets are called equivalence classes. Why can two classes never merely overlap? Suppose some c lay in both and , so a R c and b R c. By symmetry c R b, and then by transitivity a R b. So and are the same setdisjointempty — one shared element makes two classes collapse into one.

The road also runs the other way: a partition gives an equivalence relation. Split Z into the three disjoint subsets whose union is Z:

Define in Z. The argument of Example 5, with 3 in place of 2, shows that R is an equivalence relation — and its classes are exactly the bins you just filled: , , and is the class containing 230. In fact , and for every .

You use such a partition every day: a 12-hour clock shows the same position for 3, 15 and 27 hours, because they leave the same remainder on division by 12. Each position on the clock face is one equivalence class.

Example 6 : Let R be the relation defined in the set by R = {(a, b) : both a and b are either odd or even}. Show that R is an equivalence relation. Further, show that all the elements of the subset are related to each other and all the elements of the subset are related to each other, but no element of the subset is related to any element of the subset .

Solution : Any a in A has the same parity as itself, so and R is reflexivesymmetricempty.

If , then a and b are both odd or both even, so : R is symmetric. If , then a, b, c all share the parity of b, so : R is transitive. Hence R is an equivalence relation.

The elements of are all odd, so they are related to each other; the elements of are all even, so they are related to each other. An odd number and an even number never share a parity, so no element of the first subset is related to any element of the second. These two subsets are the equivalence classes and of R, and every element of A lies in exactly onebothneither of them.