Are the following equivalence relations? Linear orderings? Partial orderings? (

Question

Are the following equivalence relations? Linear orderings? Partial orderings? ( Please prove your statements)
(a) R = {(a, b) Z^2 : a|b} (relation on Z)
(b) Q is a relation on the set of people (who have ever lived), and (a, b) R means that a is a
descendent of b (a child is a descendent, and any descendent of a child is also a descendent of its
parents, please ignore highly criminal possibilities)
(c) Let X = {(a, b) Z^2 , b not equal to 0}. T is a relation on X , and ((a, b), (c, d)) T means that ad = bc.

Explanation / Answer

So let's first say what conditions need to be satisfied for each of these relations.
Equivalence relations: 1) reflexive 2) symmetric 3) transitive
Linear Orderings: 1) transitive 2) antisymmetric 3) total
Partial Orderings: 1) reflexive 2) transitive 3) antisymmetric.

Let's start with (a) R = {(a,b)Z^2 : a|b} and we'll see if it's an equivalence relation first, so

1) does a|a? yes 2) if a|b does b|a? no. So we can stop there and say this is not an equivalence relation.

How about a linear ordering though? 1) if a|b and b|c, does a|c? yes, 2) if a|b and b|a does a = b? yes. 3)for all a, b in R, does a|b or b|a? no. So this is not a linear ordering either. Let's check the last one though. Of course we've already done all the work at this point, in examining the other relations. Is R reflexive? yes 2) transitive? yes. 3) antisymetric? yes. So R does define a partial ordering. Okay, onto (b)

is it reflexive? can anyone be their own child? not yet at least, so no. is it symmetric? if a is a descendent of b, can b be a descendent of a? again, not on this planet. Is it transitive? if a is a descendent of b and b is a descendent of c, then a is a descendent of c as well, so that's a big thumbs up. antisymetric? if a is a descendent of b and b is a descendent of a, does a = b? honestly i think that one might be too weird to answer, but I'd have to go with a no. Is it total? For all people a, b is a a descendent of b or b a descendent of a? I really hope not. So, no go on total ordering. There's nothing really going on with part (b) apparently.

Okay, now (c). 1) is it reflexive? well, ((a,b),(a,b))=>ab=ba, and since we are talking about integers here, this is true. Check. 2) Symmetric? ((a,b),(c,d))=>ad=bc and ((c,d),(a,b))=>cb=da, and we're two for two here. 3)Transitive? ((a,b),(c,d)) and ((c,d),(e,f))=>ad=bc and cf=de. We'd like to know, given that information does af=be? We'll let's do some substitution to find out. a=(bc)/d and f=(de)/c so af=(bc)(de)/dc=be, which is what we wanted, so (C) is an equivalence relation. You should check the two properties to see if it is total or partially ordered.

Hope this helps

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.