211L6Solutions

Exercises

1. For each of the pair of sets A and B below, determine whether A is a subset of B or B is a subset of A or A = B.

• (a) A = {1, 2}, B = {2, 3, 4}.

A != B

• (b) A = {a, c}, B = {c, d, a}.

a is a subset of b (proper subset)

• (c) A = {3, 2, a}, B = {2, 3, a}.

A = B

• (d) A = {4, 7,−1}, B = {7, 3, 4}.

A != B

2. For any two sets A and B prove the equalities A U A = A and A n B = B n A are true.

• If x is from a A U A then x is from A and is also x is from A. {x | x is a member of A or x is a member of A}. Thus A U A = A.

• For any set, if {x | x is a member of A and x is a member of B}, then it follows that x is a member of B and x is a member of A. Thus A n B = B n A.

3. Let A, B, C be sets. Prove that (A U B) U C = A U (B U C) and (A n B) n C = A n (B n C).

• Let A = {a,b} B = {b,c} C = {c,d}.
  • (A U B) U C = {a,b,c} U {c,d} = {a,b,c,d}
  • A U (B U C) = {a,b} U {b,c,d} = {a,b,c,d}
  • Thus (A U B) U C = A U (B U C)

• Let A = {a,b} B = {a,c} C = {a,d}.
  • (A n B) n C = {a} n {a,d} = {a}
  • A n (B n C) = {a,b} n {a} = {a}
  • Thus (A n B) n C = A n (B n C)

4. Give examples of sets A and B such that A \ B != B \ A.

let A = {a,b,c} and B = {c,d,e}. Then A\B = {a,b} and B\A = {d,e}

{a,b} does not equal {d,e} and thus A\B is not the same as B\A.

5. Let A and B be sets. Prove or disprove the following equalities:

• (a) P(A n B) = P(A) n P(B).

e.g.

• P({a b} n {b c}) = P{(b)} = b
• P(a b) n P{b c} = {(a,a), (a,b), (b,a), (b,b)} n {(b,b), (b,c), (c,b), (c,c)} = (b,b)

b does not equal (b,b).

• (b) P(A U B) = P(A) U P(B).
• P({a} U {a}) = a
• P({a}) U P({a}) = a

Therefore, in at least one instance this does hold true.

6. Find the cross products A × B, A × A, and A × B × A for the following sets:

• (a) A = {1, 2}, B = {2, 3, 4}.
  1. A × B = {{1,2},{1,3},{1,4},{2,2},{2,3},{2,4}}
  2. A × A = {{1,1},{1,2},{2,2}}
  3. A × B × A = {{1,2,1},{1,2,2},{1,3,1},{1,3,2},{1,4,1},{1,4,2},{2,2,2},{2,3,2},{2,4,2}}
• (b) A = N, B = {1, 2}.
  1. A × B = {{N,1},{N,2}}
  2. A × A = {{ N,N },}
  3. A × B × A = {{N,1,N},{N,2,N}}
• (c) A = {c, d}, B = 0.
  1. A × B = {{c,0},{d,0}}
  2. A × A = {{c,c},{c,d},{d,d}}
  3. A × B × A = {{c,0,c},{c,0,d},{d,0,d}}

7. For sets A, B and C prove A × (B U C) = A × B U A × C.

• Let A = {a,b} B = {b,c} C = {c,d}.
  • A × (B U C) = A × {b,c,d} = {{a,b},{a,c},{a,d},{b,b},{b,c},{b,d}}
  • A × B U A × C = {{a,b},{a,c},{b,b},{b,c}} U {{a,c},{a,d},{b,c},{b,d}} = {{a,b},{a,c},{a,d},{b,b},{b,c},{b,d}}
  • Thus A × (B U C) = A × B U A × C

8. Consider the set A = {x, y}. List down all unary and binary relations on this set. How many ternary relations are there on this set? How many 4-place relations are there on this set? {x,y,(x,x),(x,y),(y,x),(y,y)} //and empty There are no ternary or 4-place relations.

9. Consider the set A = {a, b, c}. Do the following:

• (a) Find a relation on A that is symmetric and reflexive but not transitive.

{(a,a),(a,b),(b,b),(b,a),(c,c)}

• (b) Find a relation on A that is symmetric and transitive but not reflexive.

{(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)}

• (c) Find a relation on A that is reflexive and transitive but not symmetric.

{(a,a),(a,b),(b,b),(b,c),(c,c),(c,a)}

10. Let R be a binary relation on A. Call a relation R0 the minimal symmetric cover of R if the following are true:

• (a) R0 is a symmetric relation.
• (b) R � R0.
• (c) If S is a symmetric relation containing R then R0 � S.

Design a method that builds the minimal symmetric cover for any given binary relation R.

For all (x,y) which exist in R, if (y,x) does not exist, create it.

11. Let R be a binary relation on A. Call a relation R0 the transitive closure of R if the following are true:

• (a) R0 is a transitive relation.
• (b) R � R0.
• (c) If T is a transitive relation containing R then R0 � T.

Design a method that builds the transitive closure for any given binary relation R.

Wherever (x,y) exist in R and (y,z) exist in R, if there isn't already a path from x,z then create one.

12. Give an example of a symmetric relation which is antisymmetric. R={(1,1),(2,2),(3,3)}

13. Give an example of antisymmetric relation which is symmetric. R={(1,1),(2,2),(3,3)}

Programming exercises

1. Write a program that for input finite sets A and B outputs A [ B.

• Done

2. Write a program that for input finite sets A and B outputs A \ B.

• Done

3. Write a program that for input finite sets A and B outputs A \ B.

• Done

4. Write a program that as input takes a binary relation on a finite set and determines

• a) if the relation is reflexive;

Done

• b) if the relation is symmetric;

Done

• c) if the relation is transitive;
• d)if the relation is antisymmetric.

Done

5. Write a program that given a finite set A and a binary relation R on A outputs the minimal symmetric cover of R (see Exercise 10).

6. Write a program that given a finite set A and a binary relation R on A outputs the transitive closure of R (See Exercise 11)