Are the following equivalence relations? Linear orderings? Partial orderings? (
ID: 2941908 • Letter: A
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