Introduction to Relation

Relation:

A relation R from A to B is a subset of the Cartesian product A x B and is derived by describing a relationship between the first element (say x) and the other element (say y) of the ordered pairs in A & B.

Representation of Relation:

A relation is represented either by Roster method or by Set-builder method. Consider an example of two sets A = {9, 16, 25} and B = {5, 4, 3, -3, -4, -5}. The relation is that the elements of A are the square of the elements of B.

1. In set-builder form, R = {(x, y): x is the square of y, x ∈ A and y ∈ B}.
2. In roster form, R = {(9, 3), (9, -3), (16, 4), (16, -4), (25, 5), (25, -5)}.

Terminologies (Terms used):

1. Image:
   for any ordered pairs, in any Cartesian product (say A × B), the second element is called the image of the first element.
2. Domain:The set of all first elements of the ordered pairs in a relation R from a set A to a set B.
3. Range:The set of all second elements in a relation R from a set A to a set B is  called Range.
4. Co-domain:
   The whole set B is called Co-domain. Range ⊆ Co-domain.

Total Number of Relations:

For two non-empty set, A and B. If the number of elements in A is h i.e., |A| = h & that of B is k i.e., |B| = k, then the number of ordered pair in the Cartesian product will be |A × B| = hk. The total number of relations is 2^hk.

Types of Relations:

There are many types of relations.

Empty Relation:

If no element of set X is related or mapped to any element of Y, then the relation R in A is an empty relation, i.e, R = Φ.

Universal Relation:

A relation R, called universal relation if each element of A is related to every element of B.

Suppose A is a set of all natural numbers and B is a set of all whole numbers. The relation between A and B is universal as every element of A is in set B.

                    Empty relation and Universal relation are sometimes called trivial relation.

Inverse Relation:

Let R be a relation from set A to set B i.e., R ∈ A × B. The relation R^-1 is said to be an Inverse relation if R^-1 from set B to A is denoted by R^-1 = {(b, a): (a, b) ∈ R}.

Identity Relation:

In Identity relation, every element of set A is related to itself only. I = {(a, a), ∈ A}.

For example, If we throw two dice, we get 36 possible outcomes, (1, 1), (1, 2), … , (6, 6). If we define a relation as R: {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}, it is an identity relation.

Reflexive Relation:

If every element of set A maps to itself, the relation is Reflexive Relation. For every a ∈ A, (a, a) ∈ R.

Symmetric Relation:

A relation R on a set A is said to be symmetric if (a, b) ∈ R then (b, a) ∈ R, for all a & b ∈ A.

Transitive Relation:

A relation in a set A is transitive if, (a, b) ∈ R, (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A

Equivalence Relation:

A relation is said to be equivalence if and only if it is Reflexive, Symmetric, and Transitive.

Ordered Relation:

Partial Ordered Relation:
A relation R⊂X ✖️ X is called partial ordering if it is Reflexive,Anti-Symmetric, and Transitive, that is
   
             (x , x) ∈ R for all x ∈ X
             (x , y) ∈ R ,(y , x) ∈ R ⇒ x = y
             (x , y) ∈ R, (y , z) ∈ R ⇒ (x , z) ∈ R

Total Ordered Relation:
When all the elements of a partial order relation are comparable, the relation is called a total order Relation.
i.e;  a,b ∈ A and  a≤ b and b≤ a
[ ≤ is called relation ]

Linear Ordered:

That is, every element is related with every element one way or the other.
A total order is also called a linear order.

PreOrdered/Quasi Ordered:

A binary relation R on a set A is a quasi order if and only if it is
(1) irreflexive, { (x , x) ∈ R for all x ∉ X }
(2) transitive.  (x , y) ∈ R, (y , z) ∈ R ⇒ (x , z) ∈ R.


(minimal/maximal element):

Let < A, ≤ > be a poset, where ≤ represents an arbitrary partial order. Then an element   b ∈ A is a minimal element of A if there is no element  a ∈ A that satisfies a ≤ b. Similarly an element b ∈ A is a maximal element of A if there is no element a ∈ A that satisfies b ≤ a.
 
(least/greatest element):

Let < A, ≤ > be a poset. Then an element b ∈ A is the least element of A if for every element a ∈ A, b ≤ a.

(well order): A total order R on a set A is a well order if every non-empty subset of A has the least element.