Chapter - 4, Relations

Section - 4.5 - Closures


Summary

  • Reflexive Closure: Suppose is a relation on a set . Then the reflexive closure of is the smallest set such that and is reflexive, if there is such a smallest set. In other words, a relation is the reflexive closure of if it has the following three properties:
    1. .
    2. is reflexive.
    3. For every relation ,if and is reflexive, then .
  • Strict Partial Order and Strict Total Order: Suppose is a relation on . Then is said to be irreflexive if . is called a strict partial order if it is irreflexive and transitive. It is called a strict total order if it is a strict partial order, and in addition it satisfies the following requirement, called trichotomy:
    .
  • Symmetric Closure: Suppose is a relation on . The symmetric closure of is the smallest set such that and is symmetric, if there is such a smallest set. In other words, a relation is the symmetric closure of R if it has the following properties:
    1. .
    2. is symmetric.
    3. For every relation ,if and is symmetric, then .
  • Transitive Closure: The transitive closure of is the smallest set such that and is transitive, if there is such a smallest set. In other words, a relation is the transitive closure of if it has the following properties:
    1. .
    2. is transitive.
    3. For every relation ,if and is transitive, then .
  • Suppose is a relation on and suppose:
    • is Reflexive closure of . Then is the smallest element of the family of sets . Since we know the smallest element of a family of sets is , .
    • is Symmetric closure of . Then is the smallest element of the family of sets . Since we know the smallest element of a family of sets is , .
    • is Transitive closure of . Then is the smallest element of the family of sets . Since we know the smallest element of a family of sets is , .
  • Since all the family of sets mentioned above, contains the element (because is reflexive, symmetric and transitive), . Thus is defined. So we can conclude that reflexive, symmetric and transitive closures exist for every relation. Also since a set has a smallest element, it can have only one such element. Thus reflective, symmetric, and transitive closures are unique.
  • Reflexive closure of a relation on is .
  • Symmetric closure of a relation on is .

Soln1

(a)

Reflexive Closure:
.

Symmetric Closure:
.

Transitive Closure:
.

(b)

Reflexive Closure:
.
which is equivalent to,
.

Symmetric Closure:
.

Transitive Closure:
As we can see, is alreast a transitive closure:
.

(c)

Reflexive Closure:
Since is defined for positive number , thus , so , Thus including it,
.

Symmetric Closure:
As we can see is already symmetric,
.

Transitive Closure:
.


Soln2 Similar to Soln1(a).


Soln3

(a) Suppose is asymmetric relation. Suppose are arbitrary elements of such that . Thus is false. Or we can also say that is false, or . Thus we can also say . Since and are arbitrary, we can conclude that . Thus is antisymmetric.

(b) Suppose is strict partial order. Suppose and are arbitrary elements of such that . We will prove by contradiction that . Suppose . Since and is transitive, it follows . This contradicts with the given that is strict partial order, and . Thus if then . Thus we can conclude that is asymmetric.


Soln4

(a)

Suppose is strict partial order.

Reflexive: Since is reflexive closure of , it follows that . Thus is reflexive.

Transitive: Suppose such that . Since , and . Thus we have and . Thus we have following possible cases:

  • Case 1: and :
    Since , . Since and , it follows . Or we can also say .

  • Case 2: and : Since , . Since and , it follows . Or we can also say .

  • Case 3: and :
    Since is transitive, it follows that . Or we can also say .

  • Case 4: and :
    Thus . Since , it follows . Or we can also say .

Thus from all the cases, . Since are arbitrary, we can conlude that is arbitrary.

Antisymmetric: Suppose such that . Thus and . Thus we have following cases:

  • Case 1: and :
    Since . But since , . Thus this cases is not possible.

  • Case 2: and : Since . But since , . Thus this cases is not possible.

  • Case 3: and :
    Since is transitive, it follows . But since is irreflexive, . Thus this case is also not possible.

  • Case 4: and :
    Thus .

Thus from all the cases, if , then . Thus is antisymmetric.

(b)

Suppose . Since is strict partial order we have following cases:

  • Case 1: . Thus . Since , . Thus .

  • Case 2: . Thus . Or we can also say .

  • Case 3: . Thus . Or we can also say .

Thus from all the cases, we have . Since are arbitrary, it follows that is total order.


Soln5

(a)

To prove that is the largest element of . We need to prove that and .

Suppose such that . Thus . Thus if then . Thus . Also since , it follows that . Thus if , then . It follows that is irreflexive. Also , it follows that . Since and and is irreflexive, it follows that .

Suppose . Suppose such that . Since , it follows that . Also since is irreflexive, it follows that . Thus . Since , it follows that . Thus . Since are arbitrary, it follows that . Since is arbitrary, it follows that .

Thus and , it follows that is the largest element of .

(b)

Suppose is partial order on .

Suppose . Since is partial order, . Also . Thus , or . Thus is irreflexive.

Suppose such that . Since , it follows . Since is transitive, it follows that . We will prove by contradiction that . Suppose , then since , it follows . Also we have and since is antisymmetric, it follows that . But since , . Thus leads to contradiction. Thus , or . Since , it follows that . Since are arbitrary, it follows that is transitive.

Thus is irreflexive and transitive, it follows that is strict partial order.


Soln6

(a) .

(b) We know that .

Thus There exists a such that and .
It is equivalent to:
There exists a such that is the ancestor of and is the ancestor of .
It is equivalent to:
There exists a such that and have a ancestor .
It is equivalent to:
and have a common ancestor .


Soln7

(a)

()Suppose and is reflexive. Thus:

  1. .
  2. is reflexive.
  3. Suppose is a set such that and is reflexive. Since , thus .

Thus is reflexive closure of . Since , is reflexive closure of .

()Suppose and is reflexive closure of . Since is reflexive closure of , it follows that , or . It follows that is reflexive.

(b)

()Suppose and is symmetric. Thus:

  1. .
  2. is symmetric.
  3. Suppose is a set such that and is symmetric. Since , thus .

Thus is reflexive closure of . Since , is symmetric closure of .

()Suppose such that is symmetric closure of . Since is symmetric closure of , it follows that is symmetric. Thus is symmetric.

Similarly it can be proved for transitive that is transitive iff is transitive closure of .


Soln8

Suppose is symmetric closure of . Thus is symmetric. Suppose . Thus there exist an element such that . Since is symmetric, it follows that . Thus . Since is arbitrary, it follows that .

Now to prove :

()Suppose . Thus there exist an element such that . We will prove by contradiction that . Suppose . Thus . Now consider a set thus making . Since was symmetric, and we removed from , it follows that is also symmetric. Since contains all the elements of except and and since , it follows that . Since is symmetric, and and , it follows that is not the smallest element such that and is symmetric. But it contradicts with the given that is symmetric closure. Thus our assumption is wrong. It follows that . It follows that . Since is arbitrary, it follows that .

()Suppose . Thus there exist an element such that either or . Thus we have following possible cases:

  • Case 1: . Since , and , it follows . Thus .

  • Case 2: . Since , and , it follows . Since is symmetric, it follows that . Thus .

Thus from both cases, if , then . Since is arbitrary, .

Thus we have and , it follows that .

Finally putting all together we have .


Soln9

Let .

Suppose . Since , it follows . Also since , it follows and . Thus . Since is arbitrary, it follows that .

Suppose that . It follows that . Since is transitive, it follows . Since , it follows . Similarly since , it follows . Thus we have and and , it follows that . Thus is transitive.

Also note that by the definition of , . Also since is transitive closure of and and is transitive, it follows that(by the definition of transitive closure), .
Since and , it follows thar .

Suppose . It follows that . Thus . Suppose . Since , it follows that . Thus . Since and , it follows that .

Suppose . It follows that . Thus . Suppose . Since , it follows that . Thus . Since and , it follows that .


Soln10

(a)

Since is the relation on . Clearly . Suppose . Then . Thus . It follows .

(b)

Suppose .

Suppose . Suppose is an arbitrary element in . It follows . Thus . Since is arbitrary, it follows . Thus . Since is arbitrary, it follows .

Suppose . Suppose is an arbitrary element in . Since belongs to all the elements of , it follows that . Since is symmetric, it follows that . Since is arbitrary, it follows . Thus . Thus is symmetric.

Suppose such that and is symmetric. It follows that . Suppose , thus . Since , it follows that . Thus .

Thus from all the above points, we can conclude that is symmetric closure of .


Soln11

(a)

We know that reflexive closure of , where .

Suppose and .

Suppose is an arbitrary element. Thus and is reflexive. Since , it follows and T_2 is reflexive. Since is reflexive closure of , it follows by the definition of reflexive closure that . Since is arbitrary, it follows , or . Thus .

(b)

  • Symmetric

We know that symmetric closure of , where .



Suppose and .



Suppose is an arbitrary element. Thus and is symmetric. Since , it follows
 and T_2 is symmetric. Since is symmetric closure of , it follows by the definition of symmetric closure that . 
Since is arbitrary, it follows , or . Thus .

  • Transitive:

We know that transitive closure of , where .



Suppose and .



Suppose is an arbitrary element. Thus and is transitive. Since , it follows
 and T_2 is transitive. Since is transitive closure of , it follows by the definition of transitive closure that . 
Since is arbitrary, it follows , or . Thus .



Soln12

(a)

  • (), Proof of :

Since , it follows and . Thus using Soln11(a), and . It follows that .

  • (), Proof of :

We will first prove:

  1. .
  2. is reflexive.

Suppose , or . We have following cases:

-Case 1: : Since , it follows that , or we may also say .

-Case 2: : Since , it follows that , or we may also say .

Since is arbitrary, and from all possible cases we can conclude that .

Suppose . Since is reflexive, it follows that . Thus we can also say that . Thus is reflexive.

Since and is reflexive, and is the reflexive closure of , then by using the definition of reflexive closure, .

Since and , we can conclude that .

(b)

  • (), Proof of :
 


Since , it follows and . Thus using Soln11(b), and . 
It follows that .



  • (), Proof of :



We will first prove: 


  1. . 

  2. is symmetric.



Suppose , or . We have following cases:



-Case 1: : Since , it follows that , or we may also say .
 


-Case 2: : Since , it follows that , or we may also say .



Since is arbitrary, and from all possible cases we can conclude that .



Suppose such that . Thus . Since and are symmetric, it follows that , or . Thus is symmetric.

Since and is symmetric, and is the symmetric closure of , then by using the definition of symmetric closure,
 .



Since and , we can conclude that .


(c)

Proof of :
 


Since , it follows and . Thus using Soln11(b), and . 
It follows that .



Counter example for :

Suppose:
.
.

.

Transitive closure for is:
.

Transitive closure for is:
.

And .

Transitive closure for is : .

Clearly .


Soln13

For all the parts there is one common part that I shall prove here.

We have is reflexive/symmetric/transitive closure of , where .

Suppose . It follows . Since and , it follows that . Thus .

(a)

We know that and .
And ,

Suppose that . Thus and . iff
iff
iff
iff
iff
.

Thus .

(b)

Suppose . It follows that and . Since and are symmetric, it follows that . Thus . Thus is symmetric.

Since is symmetric closure of , and , and is symmetric, then by the definition of symmetric closure, it follows that .

Counter example to show: :

Suppose .
Thus .

Symmetric closure of is:
.

Symmetric closure of is:
.

Symmetric closure of is:
.

And .

Thus .

(c)

Suppose and . It follows that and . Since and are transitive, it follows that and . Thus . Thus is symmetric.

Since is transitive closure of , and , and is transitive, then by the definition of transitive closure, it follows that .

Counter example to show: :

Suppose:
.
.

.

Transitive closure for is:
.

Transitive closure for is:
.

Transitive closure for is : .

And .

Clearly .


Soln14

Suppose:
.
.
.

Thus, .

Transitive closure of is:
.

Transitive closure of is:
.

Transitive closure of is:
.

And .

Thus and .


Soln15

We will prove that is the symmetric reflexive closure of .

  1. : Since , it is clear that .

  2. is reflexive: Suppose . Thus . It follows that . Thus is reflexive.

  3. is symmetric: Suppose . Thus . Thus . Thus we can also say that . Thus is symmetric.

  4. Suppose such that and is symmetric and reflexive. Suppose . Thus . Thus we have following cases:

    • Case 1: :
      Since , it follows that .

    • Case 2: : Thus . Since , it follows that . Since is symmetric, it follows .

    • Case 3: : Thus . Since is reflexive, it follows that , or .

Thus if , then , it follows that . Thus is the smallest set of all such sets like .

Thus we proved that such set exists.


Soln16

Since is reflexive closure of , it follows that .

(a) Suppose . Then . Thus we have following cases:

  • Case 1: :
    Since is symmetric, \in R. Since , it follows .

  • Case 2: : Thus . Since is reflexive, it follows .

Thus from both cases, is symmetric.

(b) Suppose . Thus we have following possible cases:

  • Case 1: .
    Thus . It follows . Since , it follows .

  • Case 2: . Since is transitive, it follows that . Since , it follows that .

  • Case 3: . Thus . It follows . Since , it follows .

  • Case 4: . Thus . Since is reflexive, it follows that .

Thus from both cases, is transitive.


Soln17

Suppose is symmetric. Suppose . Since is symmetric, it follows . Since , it follows . Thus . Thus .

Suppose . It follows that . Since is transitive, it follows that . Thus . Thus is transitive.

Since and is transitive and is transitive closure of , it follows from the definition of transitive closure that . Thus if , then . Since , it follows that . Thus is symmetric.


Soln18

Let be the symmetric closure of , and let be the transitive closure of . Also, let be the transitive closure of , and let be the symmetric closure of .

(a)

Since is transitive closure of . It follows that . Since is symmetric closure of . It follows that is symmetric and . Using Soln17, since is symmetric, is symmetric. Also since and , it follows that . Thus is transitive and symmetric and .

Now suppose such that is transitive and symmetric, and . Since is symmetric and , and is the symmetric closure of , it follows(using definition of symmetric closure) that . Since is transitive and , and is the transitive closure of , it follows(using definition of transitive closure) that . Thus is the smallest of the sets like . It follows that is symmetric transitive closure of .

(b)

Suppose is symmetric closure of , .

We know from Soln11, that if , and and are transitive closure of and respectively, then .

Now since is transitive closure of and is transitive closure of , and , it follows that . Since is symmetric, and , and is symmetric closure of , it follows by the definition of symmetric closure that .

(c) False. The problem will be because the symmetric closure of a transitive set is may not be transitive. For eg: . Clearly is transitive but symmetric closure of is . Clearly this is not transitive.

Counter Example:

Suppose:
.

Thus,
Symmetric closure of is:
.
Transitive closure of is:
.

But, if we do first transitive then symmetric,
Transitive closure of is:
.
Thus symmetric closure of :
.

Clearly, .


Soln19

Proof and theorem both are not correct. The proof does not take into account that affter adding elements to to make it transitive, it may no longer be antisymmetric.

Counter example: , R = { (1,1), (2,2), (3,3), (1,2), (2,3), (3,1) } $$

Clearly is antisymmetric and reflexive.

Transitive closure of :
.

Clearly is not antisymmetric. Thus is not partial order on .


Soln20

(a) We shall give two examples of minimal elements:

.

.

These both are minimal elements since for both of them following statement holds:

There does not exist any other set, say in such that apart from itself such that our set, say .

(b) Since smallest set in should be the subset of all other sets. Since and are sets in and , it follows that there is no smallest set in .