1. Suppose that the relations R ⊆ Z × Z and S ⊆ Z × Z contain, respectively, n pairs and m pairs of elements. In terms of n and m, what’s the largest possible size of R ◦ S? The smallest?   2....

1. Suppose that the relations R ⊆ Z × Z and S ⊆ Z × Z contain, respectively, n pairs and m pairs of elements. In terms of n and m, what’s the largest possible size of R ◦ S? The smallest?

2. Consider the following claims about the composition of relations.

1.For arbitrary relations R, S, and T, prove that R ◦ (S ◦ T) = (R ◦ S) ◦ T.

2.For arbitrary relations R and S, prove that (R ◦ S) −1 = (S −1 ◦ R −1 ).

3.Let R be any relation on A × B. Prove or disprove: hx, xi ∈ R ◦ R −1 for every x ∈ A.