Question

discrete maths

2. (Lewis, Zar 14.7) Determine whether each of the following relations is transitive, symmetric, and reflexive and why: (a) The subset relation (b) The proper subset relation (c) The relation R on Z, where R(a, b) if and only if b is a multiple of a (d) The relation R on ordered pairs of integers, where R(<a,b>,<c,d >) if and only if ad-bc.

Answer 1

(a) The reflexivity must hold FOR ALL subsets of a set, including ∅

• ∅⊂R
• But ∅∩∅=∅

Hence, since there exists a subset that doesn't satisfy reflexivity, the relation as a whole cannot be reflexive.

The relation is symmetric: but it's symmetric because IF x∩y≠∅, then y∩x=x∩y≠∅.

The transitivity, too, to find a counterexample to the property: We want to show that if for any subsets x,y,w⊆Rx,y,w⊆R xRy and yRw,yRw, it follows that xRw. xRy means x∩y≠∅. (The intersection of subset x and subset y is non-empty.) And yRw means y∩w≠∅. It does not necessarily follow that xRw, that is, there are counterexamples to x∩w≠∅.

• E.g.: let x,y,w be subsets of R defined by open intervals of reals: x=(0,2),y=(1,3),w=(2,4). Then x∩y=(1,2)≠∅,y∩w=(2,3)≠∅, but x∩w=(0,2)∩(2,4)=∅

(b) Proper subset relation is not reflexive (same point discussed in (a) for reflexivity)

It is symmetric (Refer symmetric point of (a))

It is not transitive