Relations And Functions

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:

• R is reflexive i.e., for every x, (x, x) ∊ R.
• R is symmetric i.e., for every x and y, (x, y) ∊ R implies (y, x) ∊ R.
• R is transitive i.e., for every x,y and z, (x, y) ∊ R and (y, z) ∊ R implies (x, z) ∊ R.

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.