Practice English Speaking&Listening with: Lecture 20 - Closure of Relations (Contd.)

Normal
(0)
Difficulty: 0

So we were considering the reflexive closure of a, binary relation, symmetric closure and

transitive closure. Let us recall the definition. Let R be a, binary relation on a set A, the

reflexive closure of R is the relation R dash such that R dash is reflexive, R dash contains

R, for any reflexive relation R double dash if R double dash contains R then R double

dash contains R dash. That is the reflexive closure of a relation R is the smallest reflexive

relation containing R. Similarly, we can define symmetric closure and transitive closure.

As a graph we have seen that if you have binary relation represented by a graph to get the

reflexive closure we have to add the self loops at every node. And to get the symmetric

closure if there is an arc in one direction you must add the arc in the other direction.

To get the transitive closure if there is a path between some nodes then you have to

add the arc corresponding to the path. This is what we have seen in a rough manner and

we considered the reflexive closure.

Let R be a binary relation on the set A then reflexive closure of R is denoted by R union

E. Then we have also seen what is meant by the converse of a relation. If R is a, binary

relation whenever you have a pair x, y in R you have the pair y, x in R power c. Then

we also considered some properties of converse relations.

This also we have already seen, if R is a, binary relation on a set A then R is symmetric

if and only if R is equal to R power c. Now, let us consider this portion, how do you define

the symmetric closure? What is the symmetric closure of binary relation R? Let R be a,

binary relation on the set A then the symmetric closure of R is R union R power c. R is a,

binary relation on a set A then the symmetric on A the symmetric closure of R is given by

R union R power c.

How do you prove? What is the symmetric closure? The symmetric closure should contain R it

should be symmetric and any other symmetric relation should contain the symmetric closure

of R. suppose R dash is equal to R union R power c then we have to show that symmetric

closure is R dash the symmetric closure of R is R dash. Now what are properties of R

dash? R dash contains R this is the first property that is true and R dash is symmetric

why, because look at this result, R is symmetric if and only if R is equal to R power c. Now

what can you say about R union Rcc the converse of this by the results you have seen earlier

let us see R1 union R2 powerc is R1 power c union R2 power c. Making use of this property

R union Rcc is Rc union Rcc and that is nothing but Rc union R. So the converse of this is

equal to this so R dash is symmetric.

Now the third part is, let R double dash be a symmetric relation containing R. Then we

have to prove R double dash contains R dash. Now let a, b belong to R dash. What is R dash?

R dash is R union R power c. So if a, b belongs to R dash there are two possibilities a, b

belongs to R or a, b belongs to R power c. Now R double dash contains R so a, b belongs

to R means a, b will belong to R double dash because R double dash is a symmetric relation

containing R so if a, b belongs to R R double dash will contains that pair so a, b belongs

to R double dash. Now, if a, b belongs to R power c what does that mean? b, a, belongs

to R and because R double dash contains R from this you will conclude b, a, belongs

to R double dash but R double dash is a symmetric relation so from this you conclude a, b belongs

to R. So whenever you take a pair a, b belonging to R double dash it also belongs to R double

dash so R double dash contains R dash. So the third property also satisfied so the symmetric

closure of a relation is given by s(R) is equal to R union R power c.

Now, let us consider the transitive closure. What is the transitive closure? When we you

have a path as when you represent a relation as a graph when you have path between some

nodes a transitive closure will contain the R between the two nodes. This is the idea

of a transitive closure. We have already seen that in a, communication network if direct

connection is denoted by an arc then the transitive closure represents all the pairs of nodes

by which from the first node you can send the communication to the second node. This

transitive closure has lots of practical applications. Now the transitive closure is given by this.

Let R be a, binary relation on the set A then the transitive closure of R is union i is

equal to 1 to infinity R power i that is equal to R union R squared union R cubed union etc.

Now, we have to prove this equality, that is t(R) is equal to R union R squared union

R cubed union etc and this you represent i is equal to 1 to infinity R power i. Now,

we will prove it in two parts, first this is contained in this and then this is contained

in this, so first part is we prove that union i is equal to 1 to infinity R power i is contained

in t(R) this is what we have to prove. Now to prove this part use induction R is contained

in t(R) by definition because the definition of R is, if it contains R it is transitive

and it is the smallest such relation this is the basis clause. Now, the induction portion

also suppose R power n belongs to t(R) to show R power n plus 1 belongs to t(R) this

is the induction portion of it.

Now, let a, b belong to R power n plus 1 that is R power cross R when can you say that a,

b belongs to R power n plus 1? When there exist c such that a, c belongs to R power

n and c, b belongs to R. When you say a, b belongs to R power n plus 1 that means there

should be c in A these are all defined on a set A so a, c belongs to R power n and c,

b belongs to R. now, by induction hypothesis this belongs to t(R) and this also belongs

to t(R) because anyway R is contained in t(R) so a, c belongs to t(R) and c, b also belongs

to t(R) but t(R) is a transitive relation t(R) is transitive therefore a, b belongs

to t R. So we have seen that if you assume R power n belongs to t(R) R power n plus 1

also belongs to t(R) so union of i is equal to 1 to infinity R power i is contained in

t R. So we have proved this portion.

The other way around we have to show that t(R) is contained in union of i is equal to

1 to infinity R power i this is second portion. How do you prove that? First you prove that

union of i is equal to 1 to infinity R power i is transitive, how to prove this? Suppose

you have a, b belonging to some R power s and then b, c belongs to some R power t a,

b belongs to R power s means a, b belongs to this union; b, c belongs to R power t it

also belongs to this. Now what can you say about a, c? In that case a, c will belong

to R power s cross R power t that is equal to R power s plus t a, c will belong to R

power s plus t. That is a, c will also will belong to union of i is equal to 1 to infinity

R power i. so when you have two pairs a, b and b, c belonging to this you also have a,

c belonging to this and when this condition is satisfied you say that the transitive property

is satisfied. So, we have proved that i is equal to 1 to infinity R power i is transitive.

And i is equal to 1 to infinity R power i obviously it contains R power 1 so this is

a transitive relation containing R. And by the definition of t(R) t(R) is contained in

any transitive relation containing R. It is the smallest transitive relation. So this

is the transitive relation containing R and by definition of t(R) any transitive relation

containing R should contain t(R) so we get this result t(R) is contained in union of

i is equal to 1 to infinity R power i. So these a and b together give us this result.

That is t(R) is equal to union of i is equal to 1 to infinity R power i R union R squared

R cubed etc. let us consider some examples. Consider the set of non negative integers

and a relation R such that x is related to y if y is equal to x plus 1. That is any number

i will be related i plus 1 define R like that on natural numbers, what is the transitive

closure of this? What is the transitive closure of R? Now, we have seen that R squared means

x will be related to x plus 2 for any x; R power s is x is related to x plus s and so

on and t(R) is union of i is equal to 1 to infinity R power i so what is that relation

it is less than relation so t(R) is the less than relation.

Now, if you have this relation set of human beings then R denotes the relationship x related

to y. x is the child of y then what is the transitive closure? What is the t R? This

is the relation this represents a relation x is the descendant of z x t(R) z means x is the descendant of

z.

Now what about this? n we have considered this infinite set what about the finite set?

Let R be a, binary relation on a set A where A has n elements. Then you can show that t(R)

is equal to union of i is equal to 1 to 2 power n squared R I where R is a binary relation

on a set A and A has n elements where n is a finite number. Earlier we have seen that

with n elements if you look at it as a graph you can see that with n elements you have

a graph if its a relation the ordered pairs will be represented by arcs so you can have

maximum n squared arcs in such a graph that the maximum number of ordered pairs in a relation

is n squared and any relation you can have each one of the pair present or not present,

there are two possibilities there can be maximum n squared pairs and each one of them may be

present or may not be present in a relation so that gives you 2 power n squared possibilities

so maximum you can have two power n squared distinct relation on A. So this R power R,

R power 0 is the equality relation that we are not bothered about now, in transitive

closure we start from 1 to 1. So if you consider R, R squared, R cubed etc up to R power 2

n squared R power 2 power n squared plus 1 among this set this will get repeated so you

can at the most 2 power n squared distinct relation. If you consider R power 2 power

n squared plus 1 this will be one of these relations only. So it is not necessary to

consider more than this.

So t(R) is given by this, t(R) is union of i is equal to 1 to 2 power n squared R power

i. Not only that you can see that in this case t(R) is union of i is equal to 1 to n

R you need not even consider up to when n is finite when the underlined set is a finite

set t(R) you have to consider only i is equal to 1 to n R power I, why? You can see that

t(R) is nothing but i is equal to 1 to n you need not even consider up to i is equal to

2 power n squared it is enough if you consider up to n, why because what is really t(R) is

it transitive closure? That means if R is represented by a directed graph like this

that is in t(R) any path you also have an arc that is t. Now, any path in R power 2 power n squared

if an element is R power i if ordered pair x, y is in R power i that means between x

and y there is a path of length i that is what it means. Now this is R, we will consider

the transitive closure but before that if this represents R x, y is an ordered pair

in R power i means in R there is a path between x and y of length i.

Now, if you have a path between two nodes if you have a path between two nodes something

like this from x to y directed path remove all the cycles from that remove still there

is a directed path from x to y. Earlier we had a path like that a directed path which

was not simple like this, now remove the cycles from this then you get a directed simple path

from x to y. so whenever there is a path between x and y directed path between x and y you

can get a simple path between x and y by removing the cycles and what can say about the length

of this simple path? Even if it visits all the nodes and comes back to x it will be of

length n only. So the length of such a simple path will be at the most n when you have n

elements in A.

So we need not even consider up to 2 power n squared, it is enough if you consider i

is equal to 1 to n. So in the definition of t(R) whenever there is a directed path it

should be replaced by an arc. But we know that if you have the directed path by removing

the cycles you can get a simple path between x and y of length less than or equal to n

so you can add the arc in the transitive closure. So t(R) is nothing but i is equal to 1 to

n R power i. this give us a very simple procedure to find the t R.

Now we have already seen that, take that simple one, simple binary relation having just two

paths, so what is the transitive closure of R? This is R and what will be the transitive

closure of R? Whenever there is a directed path you have to add the arc so the transitive

closure will be this a, b, c. Now, if you represent the adjacent c matrix of R like

this what will be a, b, c? What will be the adjacency matrix? a to b there is an arc,

b to c there is an arc so this is the adjacency matrix of R. Suppose I denote this by A then

what can I say about A squared?

What can you say about A squared? It is 0 1 0, 0 0 1, 0 0 0 cross 0 1 0, 0 0 1, 0 0

0. If you multiply what do you get? Here 0 1 0 cross 0 this multiplied by this is again

is 0 this multiplied by this will give you 1 and the rest of the element this multiplied

by this is 0 this multiplied by that is also 0 and so on. So R squared represent A squared.

Now if you consider the graph or the binary relation a, b, c this is R, R squared consists

of only one arc between a and c any path of length of two is replaced by an arc so R squared

has this which is represented by this matrix. Now what about R cubed? In R cubed there is

no path of length three so R cubed is the empty relation that is obtained by multiplying

R cubed is R squared cross R so that is obtained by multiplying this the matrix representing

A squared and A that is 0 1 0, 0 0 1, 0 0 0. So if you multiply you will see that that

is the 0 matrix.

So we see that R which is this is represented by 0 1 0, 0 0 1, 0 0 0. And R squared is a, b, c and this is represented

by 0 0 1, 0 0 0, 0 0 0. R cubed is just empty relation and represented by the 0 matrix.

So the transitive closure of R is R union R squared union R cubed union of i is is equal

to 1 to n R cubed that is you find the union of these three matrices you will get 0 1 1,

0 0 1, 0 0 0 and that is nothing but this a, b, c if you represent there is an arc from

a to b, there is an arc from a to c, there is an arc from b to c this is the transitive

closure. So you get the transitive closure by matrix multiplication like that.

How much time it will take to calculate the transitive closure? So R is a binary relation

represented by the adjacency matrix and this is of size n by n. Then to calculate the transitive

closure of R you have to find A, A squared, A cubed up to A power n. how much time it

will take? To multiply two matrices of size n by n you require ordered n cubed operations.

Like that you are multiplying once, twice, thrice like that n minus 1 times actually so you are performing

this matrix multiplication order n times, order n times this matrix multiplication is

performed. So totally it will take order n power 4 of course addition will take some

time but the total time is, this is the predominating factor so order n power 4 time it will take

to find the transitive closure of a relation.

There are very good algorithms to find the transitive closure like the Warshalls algorithm

and Warrens algorithm may be we shall consider them later they are very good algorithms very

efficient algorithms for calculating transitive closurethey are very simple also they take

only order n cubed time to find the transitive closure.

Now, let us consider some properties connecting the relation that is what the symmetric closure

is, what the transitive closure is and how they are related and so on. If R is reflexive

then s R and t(R) are reflexive.

If R is symmetric then r R and t(R) are symmetric and if R is transitive then r R is transitive.

Now let us see, these are very simple and straight forward. Let us consider the first

statement alone: R is reflexive then s R and t(R) are reflexive. R is reflexive would mean

R is represented by a graph like this some directed arcs, if it is reflexive you will

have self loops at every node. Now, to get the symmetric closure whenever there is an

arc in one direction you will add the arc in other direction. This is not going to affect

the self loops in anyway those self loops which are originally there are going to be

there still. So, if you considered the symmetric closure that will still be reflexive. And

similarly, consider the transitive closure of R, the transitive closure of R when you

have a path between two nodes you will be adding an edge between the two nodes. And

these self loops which are originally present are going to be still there and are not going

to be affected and so the transitive closure will also be reflexive. So similarly we can

prove the other two parts b and c; R is transitive then r R is transitive.

Now let us consider these relationships. Let R be a, binary relation on a set A then rs(R)

is equal to sr(R), rt(R) is equal to tr(R) and ts(R) contains st(R), how do you prove

that? Let us take one by one, rs(R) is equal to sr(R). What is this and what is this? Take

R first find the symmetric closure then find the reflexive closure. I will write like this

so that it is clear: first find the symmetric closure and then find the reflexive closure.

Here first find the reflexive closure then find the symmetric closure. They are all equal,

either way you can do, first find the reflexive closure then find the symmetric closure or

find the symmetric and the reflexive either way you can do it. So what is r? I write r

like this: rs(R) is equal to reflexive closure of what is s(R)? s(R) is R union R power c

and that is equal to reflexive closure of a relation is R union R power c union E. You

are adding the equality relation.

Now what can you show about the symmetric reflexive closure of R? sr(R) is equal to

it is a symmetric closure of what r is, R that is R union E. And what is this? This

is equal to R union E union R union E power c that is equal to R union E union R power

c union E power c. equality relation is just the set of pairs of the form x x, as a graph

if you look at it is just consisting of self loops at every node. So E power c is the same

as E so you need have to not write it twice so this becomes R union E is equal to R power

c and of course because of commutativity you can write it as R power c union E. So you

find that this and this are equal so you get reflexive closure of the symmetric closure

of a relation is the same as the symmetric closure of reflexive closure of that relation,

that is the first part.

Look at the second part; you want to show that the reflexive transitive closure of a

relation R is same as the transitive reflexive closure of R, that is, what we want to prove

is this rt(R) is equal to tr(R), now what is rt(R)? rt(R) is r of t(R) and we know that

t(R) of R, that is the transitive closure is R union R squared union R cubed union etc.

And the reflexive closure of that is E union R union R squared union R cubed etc where

E is the equality relation. Now we want to show that this is the same as this that is

the transitive reflexive closure of R is the same as this. But before going into that let

us make some observations, E power i is the same as E for any i where i is an integer,

what does that mean? If you take the equality relation that consists of just self loops

and if you take any power of that that will be the same as the original equality relation.

So E power i is the same as E for all i.

RE is the same as ER is the same as R, what does that mean? Suppose E is the relation

consisting of self loops equality relation, suppose it is on some set a b c d and another

relation is there on a b c d represented by R so this will have some arcs. Now, what is

the concatenation of this and this, what is the composition of this and this? ER, first

this and then this, that will mean c to c if you have c to c of course let me say it

is like this, c to c then here you have c to d so in the composition relation you have

an arc from c to d. Similarly, b to b you have and then here you have b to c and when

you combine the relation the concatenation of the relation you will have b to c so E

cross R is the same as R.

Similarly, if you look at RE an arc in RE will consist of a pair bc and then cc here.

That will essentially compose of only bc. So an arc from here to here then a self loop

followed by a self loop combine them together that it will just an arc b to c. Similarly,

an arc from c to d combining with the self loop here will give you only the arc from

c to d. So R cross E also will give you only R, E cross R also will give you only R. And

we also know that E power i is equal to E for all i. Making use of this you will realize

that t of r of R will be t of what is the reflexive closure? It is R union E, so t(R)

of R of that will be R union E union R union E squared union R union E cubed and so on.

And we know that E power i is E for all E and then RE is equal to ER and so on and E

power i is the same as the E, RE is the same as ER. So making use of these results this

will essentially reduce to E union R union R square union and so on. And this we have

seen earlier, it is nothing but rt(R). So we see that tr(R) is the same as rt(R).

Let us come to the third portion, the third portion is not an equal portion it is contained

ts(R) contains st(R) how do you prove that? We want to show that ts(R) contains st(R),

now this can be proved in this manner; take the symmetric closure of a relation R, s(R)

will always contain R by definition s(R) contains R. Now, take the transitive closure on both

sides so ts(R) will contain t(R). Now on both sides take the symmetric closure so sts(R)

contains st(R). But ts(R) is already symmetric it is a symmetric relation because first of

all we are taking the symmetric relation and then taking the transitive closure. That symmetric

property will not be affected by that, that we have seen earlier. So this is a symmetric

relation and taking the symmetric closure of that does not make any difference you get

the original relation itself and because this is symmetric these two are the same and because

these two are the same you can write it as this: ts(R) contains st(R).

So, we prove the third part and the first two parts was equality and the third part

is contained in. Let us show why it is contained in. Take the less than relation, what is ts

of less than relation and what is st of less than relation. Look at this first, less than

is a transitive relation so t of less than is the less than relation only and the symmetric

transitive closure of that is the symmetric closure of the less than relation which is

the not equal to relation. This is the less than relation on the set of non negative integers.

So st of less than is the not equal to relation whereas if you say ts less than what is the

symmetric closure of less than relation? That is a not equal to relation. And what is the

transitive closure of this? That is the transitive closure of the not equal to relation which

is the universal relation, universal relation on the set of non negative integers, they

are not the same, self loops are absent here self loops are present here. So, that shows

that they are not equal but ts less than this will contain this so ts less than contains

st less than. So it is the containment in this case not the equality. There are examples

to show that they cannot be equal.

Now, generally you say that if R is a binary relation on a set A, then R plus which denotes

the transitive closure. Transitive closure is usually denoted by R plus. Instead of t(R)

many times you use the notation R plus that is the transitive closure. An R to the power

star is read as R to the power star that denotes the reflexive transitive closure of the relation

R. And rt(R) is tr(R) that we have seen, so instead of saying that you use R to the power

star. These transitive closure relations are really very useful in many cases.

We will consider one or two applications. One is, consider a set of procedures, you

have a set of procedures P1 P2 P3 etc, then you represent like this; Pi R Pj if Pi calls

Pj. If Pi calls this Pj as a sub routine then you say Pi or Pj then what does Pi R plus

Pk represent, what does it represent? See Pi may call Pj and Pj may call P R, P R may

call Pk and if you say Pi R plus Pk the set of such Pks are the set of procedures which

will be called when Pi is executed. When the procedure Pi is executed you will get Pi R

plus Pk that means Pk will be invoked during the execution of Pi.

And what does Pi R to the power star Pk represent? Of course because this will represent the

reflexive transitive closure so it will also include Pi. Here this may not include Pi this

is the set of procedures which will be active at some point when Pi is invoked. When Pi

is called the set of procedures will be active at some point of time is denoted like this.

Now, when do you say that Pi R to the power star Pi because reflexive closure will always

contain Pi so this will always hold. But if you say Pi R plus Pi what does that mean?

It means that during the execution of Pi it invokes itself either directly or indirectly.

Pi may call itself or Pi may call Pj or Pj may call Pi whatever it is in that case Pi

is recursive, it is a recursive program directly or indirectly so this is one application.

Usually this sort of notations is also used in grammars. This star and plus we already

seen when we defined sigma plus and sigma power star. So in grammars again this notation

is used. suppose you have a string say some a1, a2 and an and some portion of it is I

will denoted by u is replaced by a roll u goes to v, so from this string you get this,

if I write as w1 it is a string over some alphabet and if a portion of it is replaced

by v, this u is replaced by v but the rest of the strings will be there then you get

w2 it is usually denoted by w1 derives w2 this represents a relation between strings

and this is called directly derives, this is if w1 derives wn by this step that is represented by this notation which

is know as the reflexive transitive closure.

So if w1 is derived in one step you call it as directly derives. But if you have w1 deriving

w2 then w2 deriving w3 in one step and so on until you get some wn. Each is obtained

from the previous one by the application of a single rule. And this you write as w1 to

the power star wn that is this star you call it as derives. Or in other words if you get

w2 from w1 in one step you write w1 derives w2.

If you get w2 w1 in several steps wn from w1 in several steps you write it as w1 double

arrow power star wn. This denotes derives. This denotes directive derives, this also

represents a relationship between the strings, this also denotes the relationship between

the strings and generally we have wi to the power star wi because each string is derived

from itself, that is what we have. So generally we can easily see that this is the reflexive

transitive closure of.

Therefore, to find out the communication paths in a communication network all the pair of nodes which can be

connected or from one node where you can send a message to any other node you have to calculate

the transitive closure. And here again like in grammar you have this derivation. Even

in automaton which is a corresponding acceptance device for a grammar you have these relationships

and you may be making use of this in several subjects in computers science and transitive

closure is a very important concept. That is why people have spent time in finding efficient

ways of finding the transitive closure as we have already seen if you represent the

relation by the adjacency matrix then if you calculate the transitive closure in naive

manner then you may require order n power 4 time because the adjacency matrix will be

represented by as n by n Boolean matrix and you have to calculate a, a squared, a cubed

up to a power n and find the sum.

But there are other efficient methods like Warshalls algorithm and Warrens algorithm

where you need not go through all those steps it takes only order n cube. So we have considered

some closure properties of relations like reflexive, transitive and symmetric closure.

There are other aspects of relations like partial order, linear order, well order, a

lexicographic order on string and so on, they are also very useful in certain things. Then

there is an equivalence relation which is also a very important concept. We shall consider

about partially ordered sets and partially orders and also equivalence relations in the

coming lectures.

The Description of Lecture 20 - Closure of Relations (Contd.)