Chapter - 4, Relations

Section - 4.2 - Relations


Summary

  • Relation: Suppose and are sets. Then a set is called a relation from to .
  • Suppose is a relation from to , then:
    • Domain of relation is a set:
      .
    • Range of relation is a set:
      .
    • The inverse of is the relation from to :
      .
  • Composition: Suppose is a relation from to and is a relation from to . Then the composition of and is the relation from to defined as follows:
    .
  • If is a relation from to , is a relation from to , and is a relation from to . Then:
    • .
    • .
    • .
    • .
    • .

Soln1

(a) Domain is the set of living persons who are parents of some living people and Range is the set of all living persons who have a living parent.

(b) Domain is the set of all real numbers, . Range is the set of all positive numbers, .


Soln2

(a) Domain is the set of all living persons who are brother of some living person. Range is the set of all living persons who have a living brother.

(b) Domain : . Note that if domain lies in then will be negative. Thus there will be no such that is negative.
Range: .


Soln3

(a) is a relation from to . is a relation from to . Thus:
.
.
.

(b) is a relation from to . is a relation from to . Thus:
.
.
.


Soln4

(a) .

(b)

.
.


Soln5

(a)

.
.

(b)

.
.


Soln6

(a)

and are both subsets of . Let is an arbitrary element of . Then,

iff .
iff .

Since is arbitrary, .

(b)

Suppose , then . Since , it follows that , or .


(c)

Clearly and are both relations from to . Let be an arbitrary element of .

Suppose . Thus there must exist an element such that and . Since , there must exist a n element such that and . Now since and , it follows that . Thus we have and , thus it follows that . Since is arbitrary, it follows that .

(d)

Clearly is a relation from to . Thus is a relation from to . Also, it can be noted that is also a relation from to . Suppose is an arbitrary element of to .

()Suppose . It follows that . Thus there exist an element such that and . Since , it follows that . Similarly, since , it follows that . Now, we have and , it follows . Now since is arbitrary, it follows that .

()Similarly, suppose . Thus there exists an element such that and . Thus it follows that and . Now since and , it follows that . And since , it follows that . Since is arbitrary, we can conclude that .

Thus from both directions, we can conclude that .


Soln7

Suppose is the enemy of and is the enemy of , then it is given that is the friend of . Thus we have if and , then . Now since and , it follows . Thus the given statement says: if , then , or Enemy of an enemy is a friend. Since is arbitrary, it follows that .


Soln8

(a)

Suppose . Thus there exist a pair such that . Since , it follows that . Thus if , then . Since is arbitrary, we can conclude that .

(b)

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

Thus from part (a) and this proof we can conclude that .

(c)

  • .
    Suppose . Thus there must exist a pair . Since , there must exist an element such that and . Now since , it follows that . Since is arbitrary, we can conclude that .

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

Since and , we can conclude that .


Soln9

(a). True.

Suppose . Then and . Thus . Thus we can say that, if , then . Since is arbitrary, we can conclude that .

(b) True.

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

(c) True.

Suppose .
iff .
iff .
iff .
iff .

Since is arbitrary, we can conclude that .


Soln10

We will prove it by contra-positive.

()Suppose . Thus there must exist some element and . Since , there must exist an element such that . Similarly, since , there must exist an element such that . Thus we have and , it follows that . Thus . Hence by contrapositive we can conclude that if , then .

()Suppose . Thus there exist atleast one pair . Thus there exist an element such that and . Thus it follows , or . Hence by contrapositive, we can conclude that if , then .


Soln11

(a)

Clearly , , and are relations from \to . Suppose is an arbitrary element in . Thus and . It follows that and and . Thus , which is equivalent to saying that . Now since and , there exist an element such that and . Thus it follows that . Sicne is arbitrary, we can conclude that .

(b)

The theorem and proof both not correct. In the proof, incorrect statement is:

Since and .

The problem is, there might exist some other element such that and . Thus even if , it might be a case that may still is in .

(c)

As noted in the above part b, we can easily find such element:

.
.
.

.

.
.
.


Soln12

(a) True.

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

(b) True.

Suppose . Thus there exists an element such that and . It follows that and . Since and , . Similarly, since and , . Thus .

(c) False.

.
.
.

.
.
.


Thus, .

(d)

Suppose . Thus,

iff, such that, .
iff, .
iff, .
iff, .

Since, is arbitrary, we can conclude that .