Chapter - 4, Relations

Section - 4.3 - More About Relations


Summary

  • In last section, relations were described as subsets of cartesian products. Another alternative notation for relations can be:
    • A point in a relation R, or , can be also be described by notation: .
    • This notation is similar to the way in mathematics where relationships between two objects are expressed by placing a symbol between these two objects. Eg: , or .
  • Another way to see relations, is drawing their pictures. To describe a relation from to . Two closed curves can be drawn adjacent to each other without touching. Draw points/vertices in one curve containing all the points from and similarly in other curve containing all points of . Now if and and , then draw an edge pointing from to .
  • For relations like , directed graphs can be used to described the relation. Such relations may also be called as: is a relation on set .
  • Suppose is a relation on , then:
    • is reflexive on (or just reflexive, if is clear from context) if or in other words .
    • is symmetric if .
    • is transitive if .
  • Suppose is a set. Let . Then is called identity relation on .
  • Suppose is a relation on a set , then:
    • is reflexive iff , where is the identity relation on A.
    • is symmetric iff .
    • is transitive iff .

Skipping problems 1 to 3 as they need diagrams.

Soln4

(a) .

(b) .

(c) . Set is reflexive, symmetric and transitive.

(d) . Set is transitive.


Soln5 .


Soln6

.
.

Since . Thus by triangular inequality, we have:

.
Since and , we have:
.

Thus we have,
.


Soln7

()Suppose is reflexive. Suppose . Since is a relation on , it follows that . Since is reflexive and is defined on , it follows that . Thus if , then . Since is arbitrary, we can conclude that .

()Suppose . Suppose . Since , . Since , it follows that . Thus if , then . Since is arbitrary, we can conclude that , which is equivalent to saying that is reflexive.

Thus from both directions we can conclude that: is reflexive, iff, .


Soln8

()Suppose is transitive. Suppose . Thus there exist an element such that and . Now since is transitive and , it follows that . Thus if , then . Since is arbitrary, we can conclude that .

()Suppose . Suppose are three elements in such that . Now since and , it follows . Since , it follows that . Since are arbitrary, we can conclude that , which is equivalent to saying that is transitive.


Soln9

(a)

()Suppose . Thus there exist an element such that . Since , it follows . Thus is equivalent to . It follows that if , then . Since is arbitrary, we can conclude that .

()Suppose . Thus . Since , it follows that . Now since and , it follows that . Thus if , then . Since is arbitrary, we can conclude that .

Thus we have as well as . It follows that .

(b)

()Suppose . Thus there exist an element such that . Since , it follows that . Thus is equivalent to saying that . Thus if , then . Since is arbitrary, we can conclude that .

()Suppose . Thus . Since , it follows that . Now since and , it follows that . Thus if , then . Since is arbitrary, we can conclude that .

Thus we have as well as . It follows that .


Soln10


  • Suppose . Thus , or . Since , there must exist an element such that . It follows that . Since and , it follows that . Thus if , then . Since is arbitrary, we can conclude that .


  • Suppose . Thus , or . Since , there must exist an element such that . It follows that . Since and , it follows that . Thus if , then . Since is arbitrary, we can conclude that .


Soln11

Suppose . Thus . Since is reflexive and , it follows . Now since and , it follows . Thus if , then . Since is arbitrary, it follows that .


Soln12

(a) Suppose is reflexive. Suppose . Thus , and we can also say that . Since is reflexive, . Thus . Since , it follows . Thus we have: if , then . Or we can conclude that , which is equivalent to saying that is reflexive.

(b) Suppose is symmetric. Suppose . It follows that . Since is symmetric, it follows that . Now since , it follows . Thus if , then . Since is arbitrary, we can conclude that is symmetric.

(c) Suppose is transitive. Suppose . It follows that . Since is transitive, it follows that . Thus we have and . Now if , then . Since is arbitrary, we can conclude that is transitive.


Soln13

(a) True. Suppose and are reflexive. Suppose . Since is reflexive, it follows . Thus we can also say . It follows that if , then . Since is arbitrary, we can conclude that . Thus is reflexive.

(b) True. Suppose and are symmetric. Suppose . Thus we have two cases:

  • Case 1:
    Since is symmetric, it follows . Thus we can also say .

  • Case 2:
    Since is symmetric, it follows . Thus we can also say .

Thus from both cases . Since is arbitrary, we can conclude that is symmetric.

(c) False. Counter Example: . Clearly and are transitive but is not transitive. Because and but .


Soln14

(a) True. Suppose and are reflexive. Suppose . Since is reflexive, it follows that . Similarly, since is reflexive, it follows that . Thus . Thus if then . Since is arbitrary, we can conclude that is reflexive.

(b) True. Suppose and are symmetric. Suppose . Thus . Since is symmetric, it follows that . Similarly, since and is symmetric, it follows that . Thus we have . Since is arbitrary, we can conclude that is symmetric.

(c) True. Suppose and are transitive. Suppose are elements in such that and . Thus and . Since is transitive, it follows that . Similarly since is transitive, it follows that . Thus . Since are arbitrary, we can conclude that is transitive.


Soln15

(a) False. . Thus . Clearly, R_2 is not reflexive, since but .

(b) True. Suppose and are symmetric. Suppose . Thus . Since is symmetric, it follows that . Similarly, since and is symmetric, it follows that . Thus we have . Since is arbitrary, we can conclude that is symmetric.

(c) False. Counter Example: . Thus .
Clearly and are transitive but is not transitive. Because and but .


Soln16

Suppose and are reflexive. Suppose . Since is reflexive, . Similarly, since is reflexive, . Since and , it follows that . Thus if , then . Since is arbitrary, we can conclude that is reflexive.


Soln17

Suppose and are symmetric.

()Suppose is symmetric. Suppose .

Since is symmetric, iff
iff
. iff
Since and are symmetric,
. iff
. iff

Thus if , iff . Since is arbitrary, we can conclude that .

()Suppose . Suppose . Since , there must exist an element such that . Since and are symmetric, it follows that and . It follows that . Since , it follows . Thus if , then . Since is arbitrary, we can conclude that is symmetric.


Soln18

Suppose and are transitive. Suppose . Suppose are elements in such that and . Since , it follows .
Similarly since , it follows . Since and , it follows that . Since , it follows .
Since , it follows that .

Since and and since is transitive, it follows .
Similarly, since is transitive, and , it follows .

Thus since , it follows that . Thus if , then . Since are arbitrary, it follows that is transitive.


Soln19

(a)

Proof and Theorem both are not correct. Problem with proof is, it is not using the existential instantiation properly. In the proof, if , then there exists and such that and . Also if , then there exists and such that and . Now here former may not be equal to latter . But in the proof, it was wrongly assumed.

(b)

(Update: 3rd June ‘18, Earlier solution contained mistakes. Thanks William for pointing out.)

Counter example:

.
.

, since and .
, since and .

But .

Earlier incorrect solution

Counter example:

.
.

, since and .
, since and .

But .


Soln20

Suppose is transitive. Suppose and . Since are not empty, suppose , , are arbitrary elements. Then by the definition of , and . Since , , and is transitive, . But then since and , it follows from the definition of that . Thus, is transitive.

Consider the case that may contain empty sets. Suppose , then . It follows . This can be true if . Thus we can have the following counter example:

Suppose and and , also suppose there is an element and an element such that .

Since , . Similarly . But since , it follows . Thus is not transitive if contains empty sets.


Soln21

(a) True. Suppose is reflexive. Suppose . Suppose . Thus there exist an element such that . Thus and since is reflexive, . Since is arbitrary, we can say that . It follows that . Thus if , then . Thus is reflexive.

(b) False. Counter example:

.

Now we can easily see that but .

(c) True. Suppose is transitive. Suppose . Since , there exist an element such that . Also since , there exist an element such that . Thus . Since is transitive, it follows that . Thus . Since are arbitrary, it follows that is transitive.


Soln22 Proof and theorem both are false. The flaw in the proof is there may not exist any element such that . Counter example:

. Thus is symmetric and transitive. But since , it is not reflexive.


Soln23

Suppose and . Suppose . To prove is transitive,we need to prove . To prove , we have to prove that if , then . Suppose . Now consider two exhaustive cases:

Case 1: . Thus . Since and , it follows that . Also, since , and , it follows that .

Case 2: . Suppose . Now since and , it follows that . Since , it follows . Since and , it follows that . Since , it follows , or .
Now consider . Thus . But , it follows that . Since , it follows . Thus we have and and , it follows that . Since and , it follows that . Since and , it follows that .

Thus from both cases .