Concepts: relations, equivalence and counting: Relations and Functions

2.1 Relations as sets of ordered pairs

Start with two sets. The Cartesian product A × B collects every ordered pair (a, b) with a in A and b in B. A relation from A to B is any subset of this product, so one relation can be larger than another without either being right or wrong.

Take A = {1, 2, 3} and B = {2, 4, 6} with the rule "a is related to b when b = 2a". The relation is the set {(1, 2), (2, 4), (3, 6)}. Its domain is A, its range is B, and the relation is a function because each input appears once. Change the rule to "a is related to b when a < b" and the ordered pairs become (1, 2), (1, 4), (1, 6), (2, 4), (2, 6), (3, 4), (3, 6). The first element 1 now appears three times, so this relation is not a function.

The definition does not care whether the rule has a formula. A relation can come from a sentence, a graph, a table or a condition on coordinates. For example, on the real line the condition "a is the negative of b" gives the relation containing every pair (t, -t).

2.1.1 Reading a relation

The domain is the set of all first entries that actually occur. The range is the set of all second entries that actually occur. The codomain is B, the set the relation was declared from A to B. For the relation on A = {1, 2, 3} given by (1, 1), (2, 2), the domain is {1, 2}, not all of A, and the range is also {1, 2}. Students often write the codomain as the range. The two coincide only for surjective functions.

2.1.2 Counting relations

If A has m elements and B has n elements, the product A × B has mn pairs. Every subset of the product is a relation, so there are 2 power (mn) relations from A to B. The number of functions from A to B is n power m, because each of the m inputs has n independent choices. Out of these, the number of one-one functions is n(n - 1) (n - 2) ... (n - m + 1), which requires n at least m.

2.1.3 Geometric picture

A relation between points written as perpendicular lines is drawn as a set diagram: the lines are elements and the perpendicularity condition becomes a relation on that set. The NCERT chapter uses exactly this picture to show that a relation can be geometric rather than numeric.

2.2 Types of relations on a set

A relation on a set is a subset of A × A, so both ends come from the same set. The standard families are easy to confuse, so compare them on one running example. Let A = {1, 2, 3}.

• Empty relation: no pair at all. On A the empty set is a relation.
• Universal relation: the whole of A × A, which contains (1, 1), (1, 2), (1, 3) and so on.
• Identity relation: only the pairs (x, x), so {(1, 1), (2, 2), (3, 3)} on A.
• Reflexive: contains (x, x) for every x in A. The identity relation qualifies, and a larger relation can also qualify.
• Symmetric: whenever (a, b) is present, (b, a) must also be present.
• Transitive: whenever (a, b) and (b, c) are present, (a, c) must be present.

The identity relation is reflexive, symmetric and transitive at the same time, so it is an equivalence relation. Reflexive and symmetric do not force transitivity, and one counterexample is enough to disprove any property.

2.3 Equivalence relation and classes

An equivalence relation separates a set into non-overlapping groups called equivalence classes. The class of an element a is the set of all elements related to a, written [a]. Every element lies in exactly one class, and the classes together rebuild the whole set. This is why an equivalence relation is sometimes described as a way of sorting a set without losing or duplicating an element.

Two standard examples carry regular marks. Take the rule that links two integers when their difference is a multiple of 2. All three tests pass, and the classes contain the evens and the odds. Take similarity of triangles next. Each triangle matches itself, similarity is mutual, and a chain of similarities still ends in similar triangles.

2.4 Worked check

Take the rule that puts two integers in relation when one minus the other is a multiple of 2.

Reflexivity: subtracting an integer from itself gives zero, and zero is a multiple of 2, so each diagonal pair qualifies. Symmetry: swapping the two integers changes the sign of the difference, and a sign change keeps a multiple of 2 still a multiple of 2. Transitivity: if the first gap and the second gap are both multiples of 2, their sum, which is the overall gap between the first and third integers, is also a multiple of 2. All three tests pass.

2.4.1 Common mistakes

Writing a relation as a formula when a set of ordered pairs is asked, forgetting to list the domain fully, and checking symmetry before reflexivity (a single missing diagonal pair already kills the equivalence claim). In the transitive step, choose b from the second entry of the first pair and the first entry of the second pair, not any random element.