Define the relation M(A, B) : AnB # 0, where the domains for A and B are all subsets of

Z. For each of the five properties of a relation defined in this chapter (reflexive, irreflexive,

symmetric, antisymmetric, and transitive) either show M satisfies the property, or explain

why it does not.

Hint: This problem causes a lot of grief. The relation M is a relation between subsets of

Z. For example, {1, 2}M{9} is false, since {1, 2} n {9} = 0. But {1, 2} M {2, 4,6, 7} is true

since {1, 2} n {2, 4, 6, 7} = {2}, and not 0.

(bonus) Let A = 0 and consider the empty relation, E = 0, on A. For each of the five prop-

erties of a relation defined in this chapter (reflexive, irreflexive, symmetric, antisymmetric,

and transitive) either show M satisfies the property, or explain why it does not.

Warning: Reasoning about the empty set can cause grave mental anguish. Suggestion:

write out each of the five definitions you need to check (reflexive, symmetric, etc.) and

decide if the statement is true or false.

For example: For the reflexive condition, the statement to check is

Vr(c E0 = (1,I) ( E)

Since the left side of the implication (x 6 0) is definitely false (after all there isn’t any-

thing in the empty set!) the entire implication is true (recall the truth table for implication).

That means the proposition above is true, and so E is reflexive. Reasoning for the remain-

ing four conditions all follow a similar pattern.

Math