Introduction: A binary relation on two sets A and B is a subset of A × B. For example, if A = {1, 3, 9}, B = {x, y}, then {(1, x), (3, y), (9, x)} is a binary relation on 2-sets. Binary relations on k–sets A1, A2,...,Ak can similarly be defined.
Another basic concept on sets is function. A function is an object that sets up an input-output relationship. That is, a function takes an input and produces the required output. For a function f, with input x, the output y, we write f(x) = y. We also say that f maps x to y. For example, addition is a function which produces the sum of the numbers that are input. The set of possible inputs to a function is called its “domain.” The output of a function comes from a set called its “range.” Let D be the domain and R be the range of a function f. We denote this description of a function as “f: D → R”. For example, f is a function with domain Z and range Z, we write it as f: Z → Z. A function that uses all the elements of the range is said to be onto (surjective). A function “f: D → R” is said to be one-to-one or 1–1 (injective) if for any two distinct elements a, b ∊ D, f (a)≠f (b). A function which is both one-to-one and onto is called a bijective function.
A binary relation K ⊆ A × B has an inverse, say K−1 ⊆ B × A defined as (b, a) ∊ K−1 if and only if (a, b) ∊ K. For example,
K={(x, y)|x ∊ S, y ∊ T, x is the student of y}
K−1={(y, x)|x ∊ S, y ∊ T, y is the teacher of x}
Note that the inverse of a function need not be a function. A function f: A → B may not have an inverse if there is some element b ∊ B such that f (a) =b for no a ∊ A. But every bijective‘f’ possesses an inverse f−1 (say), and f−1(f(a)) = a for each a ∊ A.
A binary relation R is an equivalence relation if R satisfies the following conditions:
Equivalence relation on a set A partitions A into equivalence classes. The number of equivalence classes is called the index or rank of an equivalence relation. Index can be finite or infinite.
Example: Let N be the set of non-negative integers. The relation ≡ is defined as follows: a ≡ b if and only if a and b leave the same remainder when divided by 3. This can be easily seen to be an equivalence relation of index 3.
An equivalence relation induces a partition on the underlying set. In the above example, the set of non-negative integers is partitioned into three equivalence classes:
E11={0, 3, 6, ...},
E12={1, 4, 7, ...},
E13={2, 5, 8, ...},
An equivalence relation E2 is a refinement of an equivalence relation E1 if every equivalence class of E2 is contained in an equivalence class of E1. For example, let E1 denote the mod 3 equivalence relation defined in this Example. Let E2 be an equivalence relation on the set of non-negative integers such that aE2b if a and b leave the same remainder when divided by 6. In this case there are 6 equivalence classes.
E21={0, 6, 12, ...}
E22={1, 7, 13, ...}
E23={2, 8, 14, ...}
E24={3, 9, 15, ...}
E25={4, 10, 16, ...}
E26={5, 11, 17, ...}
It can be seen that every E2j is completely included in an E1k, 1≤ j ≤ 6, 1 ≤ k ≤ 3. Hence, E2 is a refinement of E1.
