Basic Set Theory: Relations

Among the various kinds of relations, we are familiar with, father, mother, son, brother, sister, husband, wife, less than, equal to, parallel to, etc., are a few examples. We would like to fix our ideas as to what exactly is meant by a relation. Let us see how we use the terms in common parlance. We say Dasaratha is the father of Rama. Similarly, Babar is the father of Humayun and Janaka is the father of Sita. The above statements like Dasaratha is the father or Rama are but examples fatherhood. But, what do we exactly mean by fatherhood? We may attempt to define fatherhood as the collection of pairs like Dasaratha and Rama, Babar and Humayun, Janaka and Sita, etc. But in our usage “Dasaratha is the father of Rama” we cannot interchange the positions of Dasaratha and Rama. Indeed the statement “Rama is the father of Dasaratha” does not convey the same meaning as the statement “Dasaratha is the father of Rama”. Again, in the statement “Dasaratha is the father of Rama”, if we drop  the word Rama, then too it won’t mean anything. For the statement about fatherhood, what is important is a pair in a definite order: (Dasartha, Rama). Thus, a certain collection of ordered pairs stands for a definite relation, as in this case the ordered pairs

(Dasaratha, Rama), (Babar, Humayun), (Janaka, Sita)

are examples of relation of fatherhood. So fatherhood would stand for a certain collection of ordered pairs of human beings. Similarly, the relation of brotherhood would stand for a certain other collection of ordered pairs. So would sisterhood, etc. In each case, they are different collections of ordered pairs. Now we proceed to define the term relation formally. For that we need the notion of a cartesian product.

Cartesian Product.

For sets A and B, the set of all ordered pairs formed by the first element from A and the second element from B, is called the Cartesian product of A and B. It is denoted by A \times B. We have

A \times B= \{ (a,b): a \in A \hspace{0.1in} \textup{and} \hspace{0.1in} b \in B\}

Relation. 

By a relation or correspondence between the elements of a set A and those of a set B, we mean a subset f of the Cartesian product A \times B. Thus, f is a relation between set A and set B if

f \subset A \times B

If (a,b) \in f, then we say that a is related to b through f. We write this as afb. Thus, if f is the set of all human beings and M is the set of all male human beings, then fatherhood is a subset of M \times H, whereas brotherhood is another subset of M \times H. Motherhood is a subset of W \times H, where

W = \{ w: w is a woman\}. So if f \subset M \times H is the fatherhood relation, (a,b) \in f means a is the father of b. Similarly, if g \in M \times H is the brotherhood relation, then (a,b) \in G means a is a brother of b. (Observe that a is a brother of b does not imply b is a brother of a since b could be a sister of a. )

Definition:

For sets A and B if f \subset A \times B, then \{ x: (x,u) \in f \hspace{0.1in} \textup{for some} \hspace{0.1in} u \in B\} is called the domain of the relation f, and \{ y: (x,y) \in f \hspace{0.1in textup{for some} \hspace{0.1in} x \in A}\} is called the range of the relation f.

It is quite obvious that the domain of f, above, is a subset of A and the range. a subset of B.

In the above example of fatherhood, its domain cannot contain a woman. Nor did it contain all men. Indeed many men are not fathers.

Like father, mother, brother, sister we also have the relation less than, equal to, greater than, similar to, congruent to, perpendicular to, etc.

For the set A=\{ 1,2,3,4\}, let f \subset A \times A be defined by

f=\{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)\}.

We see that the relation f here is the relation less than in the set A. Here the domain of f is \{ 1,2,3\} whereas the range is \{ 2,3,4\}.

In case, f \subset A \times A, we call f a relation in A. For A, the set of all lines parallel to is a subset of

A \times A. Similarly, for the set T of all triangles, similarity and congruence are subsets of T \times T. We enumerate a few relations.

1) A relation f in A{ that is, f \subset A \times A is called a symmetric relation if afb \Longleftrightarrow bfa.

2) f \subset A \times A is called a reflexive relation if afa for all a \in A.

3) f \subset A \times A is called an antisymmetric relation if afb \hspace{0.1in} \textup{and} \hspace{0.1in} bfa \Longrightarrow a=b

4) A relation f \subset A \times A is called a transitive relation if afb, bfc \Longrightarrow afc.

Examples.

a) Similarity of triangles is reflexive, symmetric and transitive.

b) Fatherhood is neither reflexive, nor symmetric, nor transitive.

c) “Ancestor of” is transitive but is neither reflexive nor symmetric.

d) The relationship “a is the spouse of b” is symmetric but neither reflexive nor symmetric.

e) “Less than” is transitive but not reflexive.

f) “Less than or equal to” is reflexive, antisymmetric and transitive.

g) If X is a class of sets, let R \subset X \times X be defined by ARB if A \subset B. We see that R is a reflexive, antisymmetric and transitive relation.

Digression.

The way we have defined relation should strictly be called binary relation as it consists of ordered pairs. But, we have other kinds of relations too. Like collinearity of points, concurrence of lines, etc. They are not binary relations. But we don’t go into them here.

Equivalence relation.

A relation \sim on A is called an equivalence relaiton if it is reflexive, symmetric and transitive, that is,

i) a \sim a for all a \in A.

ii) a \sim b \Longleftrightarrow b \sim a

iii) a \sim b \hspace{0.1in} \textup{and} \hspace{0.1in} b \sim c \Longrightarrow a \sim c.

Examples.

a) Equality is certainly an equivalence relation.

b) Similarity between triangles is an equivalence relation.

c) Congruence of triangles is an equivalence relation.

d) Parallelism between lines is an equivalence relation if we agree that a line is parallel to itself.

e) Define a relation \equiv (\mod 5) on Z by m \equiv n (\mod 5) if m - n is divisible by 5. Note that this is an equivalence relation.

More later,

Nalin Pithwa

 

 

One Comment

  1. Posted May 27, 2015 at 11:26 am | Permalink | Reply

    Good one! Keep it up!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: