Set Theory, Relations, Functions Preliminaries: II

Relations:

Concept of Order:

Let us say that we create a “table” of two columns in which the first column is the name of the father, and the second column is name of the child. So, it can have entries like (Yogesh, Meera), (Yogesh, Gopal), (Kishor, Nalin), (Kishor, Yogesh), (Kishor, Darshna) etc. It is quite obvious that “first” is the “father”, then “second” is the child. We see that there is a “natural concept of order” in human “relations”. There is one more, slightly crazy, example of “importance of order” in real-life. It is presented below (and some times also appears in basic computer science text as rise and shine algorithm) —-

Rise and Shine algorithm:

When we get up from sleep in the morning, we brush our teeth, finish our morning ablutions; next, we remove our pyjamas and shirt and then (secondly) enter the shower; there is a natural order here; first we cannot enter the shower, and secondly we do not remove the pyjamas and shirt after entering the shower. 🙂

Ordered Pair: Definition and explanation:

A pair $(a,b)$ of numbers, such that the order, in which the numbers appear is important, is called an ordered pair. In general, ordered pairs (a,b) and (b,a) are different. In ordered pair (a,b), ‘a’ is called first component and ‘b’ is called second component.

Two ordered pairs (a,b) and (c,d) are equal, if and only if $a=c$ and $b=d$ . Also, $(a,b)=(b,a)$ if and only if $a=b$ .

Example 1: Find x and y when $(x+3,2)=(4,y-3)$ .

Solution 1: Equating the first components and then equating the second components, we have:

$x+3=4$ and $2=y-3$

$x=1$ and $y=5$

Cartesian products of two sets:

Let A and B be two non-empty sets then the cartesian product of A and B is denoted by A x B (read it as “A cross B”),and is defined as the set of all ordered pairs (a,b) such that $a \in A$ , $b \in B$ .

Thus, $A \times B = \{ (a,b): a \in A, b \in B\}$

e.g., if $A = \{ 1,2\}$ and $B = \{ a,b,c\}$ , tnen $A \times B = \{ (1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$ .

If $A = \phi$ or $B=\phi$ , we define $A \times B = \phi$ .

Number of elements of a cartesian product:

By the following basic counting principle: If a task A can be done in m ways, and a task B can be done in n ways, then the tasks A (first) and task B (later) can be done in mn ways.

So, the cardinality of A x B is given by: $n(A \times B)= n(A) \times n(B)$ .

So, in general if a cartesian product of p finite sets, viz, $A_{1}, A_{2}, A_{3}, \ldots, A_{p}$ is given by $n(A_{1} \times A_{2} \times A_{3} \ldots A_{p}) = n(A_{1}) \times n(A_{2}) \times \ldots \times n(A_{p})$

Definitions of relations, arrow diagrams (or pictorial representation), domain, co-domain, and range of a relation:

Consider the following statements:

i) Sunil is a friend of Anil.

ii) 8 is greater than 4.

iii) 5 is a square root of 25.

Here, we can say that Sunil is related to Anil by the relation ‘is a friend of’; 8 and 4 are related by the relation ‘is greater than’; similarly, in the third statement, the relation is ‘is a square root of’.

The word relation implies an association of two objects according to some property which they possess. Now, let us some mathematical aspects of relation;

Definition:

A and B are two non-empty sets then any subset of $A \times B$ is called relation from A to B, and is denoted by capital letters P, Q and R. If R is a relation and $(x,y) \in R$ then it is denoted by $xRy$ .

y is called image of x under R and x is called pre-image of y under R.

Let $A=\{ 1,2,3,4,5\}$ and $B=\{ 1,4,5\}$ .

Let R be a relation such that $(x,y) \in R$ implies $x < y$ . We list the elements of R.

Solution: Here $A = \{ 1,2,3,4,5\}$ and $B=\{ 1,4,5\}$ so that $R = \{ (1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)\}$ Note this is the relation R from A to B, that is, it is a subset of A x B.

Check: Is a relation $R^{'}$ from B to A defined by x<y, with $x \in B$ and $y \in A$ — is this relation $R^{'}$ *same* as R from A to B? Ans: Let us list all the elements of R^{‘} explicitly: $R^{'} = \{ (1,2),(1,3),(1,4),(1,5),(4,5)\}$ . Well, we can surely compare the two sets R and $R^{'}$ — the elements “look” different certainly. Even if they “look” same in terms of numbers, the two sets $R$ and $R^{'}$ are fundamentally different because they have different domains and co-domains.

Definition : Domain of a relation R: The set of all the first components of the ordered pairs in a relation R is called the domain of relation R. That is, if $R \subseteq A \times B$ , then domain (R) is $\{ a: (a,b) \in R\}$ .

Definition: Range: The set of all second components of all ordered pairs in a relation R is called the range of the relation. That is, if $R \subseteq A \times B$ , then range (R) = $\{ b: (a,b) \in R\}$ .

Definition: Codomain: If R is a relation from A to B, then set B is called co-domain of the relation R. Note: Range is a subset of co-domain.

Type of Relations:

One-one relation: A relation R from a set A to B is said to be one-one if every element of A has at most one image in B and distinct elements in A have distinct images in B. For example, let $A = \{ 1,2,3,4\}$ , and let $B=\{ 2,3,4,5,6,7\}$ and let $R_{1}= \{ (1,3),(2,4),(3,5)\}$ Then $R_{1}$ is a one-one relation. Here, domain of $R_{1}= \{ 1,2,3\}$ and range of $R_{1}$ is $\{ 3,4,5\}$ .

Many-one relation: A relation R from A to B is called a many-one relation if two or more than two elements in the domain A are associated with a single (unique) element in co-domain B. For example, let $R_{2}=\{ (1,4),(3,7),(4,4)\}$ . Then, $R_{2}$ is many-one relation from A to B. (please draw arrow diagram). Note also that domain of $R_{1}=\{ 1,3,4\}$ and range of $R_{1}=\{ 4,7\}$ .

Into Relation: A relation R from A to B is said to be into relation if there exists at least one element in B, which has no pre-image in A. Let $A=\{ -2,-1,0,1,2,3\}$ and $B=\{ 0,1,2,3,4\}$ . Consider the relation $R_{1}=\{ (-2,4),(-1,1),(0,0),(1,1),(2,4) \}$ . So, clearly range is $\{ 0,1,4\}$ and $range \subseteq B$ . Thus, $R_{3}$ is a relation from A INTO B.

Onto Relation: A relation R from A to B is said to be ONTO relation if every element of B is the image of some element of A. For example: let set $A= \{ -3,-2,-1,1,3,4\}$ and set $B= \{ 1,4,9\}$ . Let $R_{4}=\{ (-3,9),(-2,4), (-1,1), (1,1),(3,9)\}$ . So, clearly range of $R_{4}= \{ 1,4,9\}$ . Range of $R_{4}$ is co-domain of B. Thus, $R_{4}$ is a relation from A ONTO B.

Binary Relation on a set A:

Let A be a non-empty set then every subset of $A \times A$ is a binary relation on set A.

Illustrative Examples:

E.g.1: Let $A = \{ 1,2,3\}$ and let $A \times A = \{ (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$ . Now, if we have a set $R = \{ (1,2),(2,2),(3,1),(3,2)\}$ then we observe that $R \subseteq A \times A$ , and hence, R is a binary relation on A.

E.g.2: Let N be the set of natural numbers and $R = \{ (a,b) : a, b \in N and 2a+b=10\}$ . Since $R \subseteq N \times N$ , R is a binary relation on N. Clearly, $R = \{ (1,8),(2,6),(3,4),(4,2)\}$ . Also, for the sake of completeness, we state here the following: Domain of R is $\{ 1,2,3,4\}$ and Range of R is $\{ 2,4,6,8\}$ , codomain of R is N.

Note: (i) Since the null set is considered to be a subset of any set X, so also here, $\phi \subset A \times A$ , and hence, $\phi$ is a relation on any set A, and is called the empty or void relation on A. (ii) Since $A \times A \subset A \times A$ , we say that $A \subset A$ is a relation on A called the universal relation on A.

Note: Let the cardinality of a (finite) set A be $n(A)=p$ and that of another set B be $n(B)=q$ , then the cardinality of the cartesian product $n(A \times B)=pq$ . So, the number of possible subsets of $A \times B$ is $2^{pq}$ which includes the empty set.

Types of relations:

Let A be a non-empty set. Then, a relation R on A is said to be: (i) Reflexive: if $(a,a) \in R$ for all $a \in A$ , that is, aRa for all $a \in A$ . (ii) Symmetric: If $(a,b) \in R \Longrightarrow (b,a) \in R$ for all $a,b \in R$ (iii) Transitive: If $(a,b) \in R$ , and $(b,c) \in R$ , then so also $(a,c) \in R$ .

Equivalence Relation:

A (binary) relation on a set A is said to be an equivalence relation if it is reflexive, symmetric and transitive. An equivalence appears in many many areas of math. An equivalence measures “equality up to a property”. For example, in number theory, a congruence modulo is an equivalence relation; in Euclidean geometry, congruence and similarity are equivalence relations.

Also, we mention (without proof) that an equivalence relation on a set partitions the set in to mutually disjoint exhaustive subsets.

Illustrative examples continued:

E.g. Let R be an equivalence relation on $\mathbb{Q}$ defined by $R = \{ (a,b): a, b \in \mathbb{Q}, (a-b) \in \mathbb{Z}\}$ . Prove that R is an equivalence relation.

Proof: Given that $R = \{ (a,b) : a, b \in \mathbb{Q}, (a-b) \in \mathbb{Z}\}$ . (i) Let $a \in \mathbb{Q}$ then $a-a=0 \in \mathbb{Z}$ , hence, $(a,a) \in R$ , so relation R is reflexive. (ii) Now, note that $(a,b) \in R \Longrightarrow (a-b) \in \mathbb{Z}$ , that is, $(a-b)$ is an integer $\Longrightarrow -(b-a) \in \mathbb{Z} \Longrightarrow (b-a) \in \mathbb{Z} \Longrightarrow (b,a) \in R$ . That is, we have proved $(a,b) \in R \Longrightarrow (b,a) \in R$ and so relation R is symmetric also. (iii) Now, let $(a,b) \in R$ , and $(b,c) \in R$ , which in turn implies that $(a-b) \in \mathbb{Z}$ and $(b-c) \in \mathbb{Z}$ so it $\Longrightarrow (a-b)+(b-c)=a-c \in \mathbb{Z}$ (as integers are closed under addition) which in turn $\Longrightarrow (a,c) \in R$ . Thus, $(a,b) \in R$ and $(b,c) \in R$ implies $(a,c) \in R$ also, Hence, given relation R is transitive also. Hence, R is also an equivalence relation on $\mathbb{Q}$ .

Illustrative examples continued:

E.g.: If $(x+1,y-2) = (3,4)$ , find the values of x and y.

Solution: By definition of an ordered pair, corresponding components are equal. Hence, we get the following two equations: $x+1=3$ and $y-2=4$ so the solution is $x=2,y=6$ .

E.g.: If $A = (1,2)$ , list the set $A \times A$ .

Solution: $A \times A = \{ (1,1),(1,2),(2,1),(2,2)\}$

E.g.: If $A = \{1,3,5 \}$ and $B=\{ 2,3\}$ , find $A \times B$ , and $B \times A$ , check if cartesian product is a commutative operation, that is, check if $A \times B = B \times A$ .

Solution: $A \times B = \{ (1,2),(1,3),(3,2),(3,3),(5,2),(5,3)\}$ whereas $B \times A = \{ (2,1),(2,3),(2,5),(3,1),(3,3),(3,5)\}$ so since $A \times B \neq B \times A$ so cartesian product is not a commutative set operation.

E.g.: If two sets A and B are such that their cartesian product is $A \times B = \{ (3,2),(3,4),(5,2),(5,4)\}$ , find the sets A and B.

Solution: Using the definition of cartesian product of two sets, we know that set A contains as elements all the first components and set B contains as elements all the second components. So, we get $A = \{ 3,5\}$ and $B = \{ 2,4\}$ .

E.g.: A and B are two sets given in such a way that $A \times B$ contains 6 elements. If three elements of $A \times B$ are $(1,3),(2,5),(3,3)$ , find its remaining elements.

Solution: We can first observe that $6 = 3 \times 2 = 2 \times 3$ so that A can contain 2 or 3 elements; B can contain 3 or 2 elements. Using definition of cartesian product of two sets, we get that $A= \{ 1,2,3\}$ and $\{ 3,5\}$ and so we have found the sets A and B completely.

E.g.: Express the set $\{ (x,y) : x^{2}+y^{2}=25, x, y \in \mathbb{W}\}$ as a set of ordered pairs.

Solution: We have $x^{2}+y^{2}=25$ and so

$x=0, y=5 \Longrightarrow x^{2}+y^{2}=0+25=25$

$x=3, y=4 \Longrightarrow x^{2}+y^{2}=9+16=25$

$x=4, y=3 \Longrightarrow x^{2}+y^{2}=16+9=25$

$x=5, y=0 \Longrightarrow x^{2}+y^{2}=25+0=25$

Hence, the given set is $\{ (0,5),(3,4),(4,3),(5,0)\}$

E.g.: Let $A = \{ 1,2,3\}$ and $B = \{ 2,4,6\}$ . Show that $R = \{ (1,2),(1,4),(3,2),(3,4)\}$ is a relation from A to B. Find the domain, co-domain and range.

Solution: Here, $A \times B = \{ (1,2),(1,4),(1,6),(2,2),(2,4),(2,6),(3,2),(3,4),(3,6)\}$ . Clearly, $R \subseteq A \times B$ . So R is a relation from A to B. The domain of R is the set of first components of R (which belong to set A, by definition of cartesian product and ordered pair) and the codomain is set B. So, Domain (R) = $\{ 1,3\}$ and co-domain of R is set B itself; and Range of R is $\{ 2,4\}$ .

E.g.: Let $A = \{ 1,2,3,4,5\}$ and $B = \{ 1,4,5\}$ . Let R be a relation from A to B such that $(x,y) \in R$ if $x<y$ . List all the elements of R. Find the domain, codomain and range of R. (as homework quiz, draw its arrow diagram);

Solution: Let $A = \{ 1,2,3,4,5\}$ and $B = \{ 1,4,5\}$ . So, we get R as $(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)$ . $domain(R) = \{ 1,2,3,4\}$ , $codomain(R) = B$ , and $range(R) = \{ 4,5\}$ .

E.g. Let $A = \{ 1,2,3,4,5,6\}$ . Define a binary relation on A such that $R = \{ (x,y) : y=x+1\}$ . Find the domain, codomain and range of R.

Solution: By definition, $R \subseteq A \times A$ . Here, we get $R = \{ (1,2),(2,3),(3,4),(4,5),(5,6)\}$ . So we get $domain (R) = \{ 1,2,3,4,5\}$ , $codomain(R) =A$ , $range(R) = \{ 2,3,4,5,6\}$

Tutorial problems:

If $(x-1,y+4)=(1,2)$ , find the values of x and y.
If $(x + \frac{1}{3}, \frac{y}{2}-1)=(\frac{1}{2} , \frac{3}{2} )$
If $A=\{ a,b,c\}$ and $B = \{ x,y\}$ . Find out the following: $A \times A$ , $B \times B$ , $A \times B$ and $B \times A$ .
If $P = \{ 1,2,3\}$ and $Q = \{ 4\}$ , find the sets $P \times P$ , $Q \times Q$ , $P \times Q$ , and $Q \times P$ .
Let $A=\{ 1,2,3,4\}$ and $\{ 4,5,6\}$ and $C = \{ 5,6\}$ . Find $A \times (B \bigcap C)$ , $A \times (B \bigcup C)$ , $(A \times B) \bigcap (A \times C)$ , $A \times (B \bigcup C)$ , and $(A \times B) \bigcup (A \times C)$ .
Express $\{ (x,y) : x^{2}+y^{2}=100 , x, y \in \mathbf{W}\}$ as a set of ordered pairs.
Write the domain and range of the following relations: (i) $\{ (a,b): a \in \mathbf{N}, a < 6, b=4\}$ (ii) $\{ (a,b): a,b \in \mathbf{N}, a+b=12\}$ (iii) $\{ (2,4),(2,5),(2,6),(2,7)\}$
Let $A=\{ 6,8\}$ and $B=\{ 1,3,5\}$ . Let $R = \{ (a,b): a \in A, b \in B, a+b \hspace{0.1in} is \hspace{0.1in} an \hspace{0.1in} even \hspace{0.1in} number\}$ . Show that R is an empty relation from A to B.
Write the following relations in the Roster form and hence, find the domain and range: (i) $R_{1}= \{ (a,a^{2}) : a \hspace{0.1in} is \hspace{0.1in} prime \hspace{0.1in} less \hspace{0.1in} than \hspace{0.1in} 15\}$ (ii) $R_{2} = \{ (a, \frac{1}{a}) : 0 < a \leq 5, a \in N\}$
Write the following relations as sets of ordered pairs: (i) $\{ (x,y) : y=3x, x \in \{1,2,3 \}, y \in \{ 3,6,9,12\}\}$ (ii) $\{ (x,y) : y>x+1, x=1,2, y=2,4,6\}$ (iii) $\{ (x,y) : x+y =3, x, y \in \{ 0,1,2,3\}\}$