# show a binary relation is well-defined

• Sep 23rd 2010, 12:47 PM
jimbob11
show a binary relation is well-defined
here's a problem from the current logic book I'm reading: Let (W,R) be a quazi-order and define ~ on W by putting s~t iff Rst and Rts. First (which i don't have a problem with) show ~ is an equivalence relation.

Part (b): Let [s] denote the equivalence class (mod ~ on W) containing s and define the following relation on the collection of equivalence classes: [s] =< [t] iff Rst. Show that this is well-defined.

Is the idea just to choose an arbitrary representative s' of [s] and t' of [t] and show that [s'] =< [t'] ? I guess I don't see how this isn't completely trivial since we automatically get [s'] = [s] and [t'] = [t] so using substitution [s'] =< [t']. Can someone show me what fallacious assumption i'm making in this argument? Maybe I'm confused because I've only seen problems asking to show an operation to be well-defined as opposed to some binary relation. Thanks for the help
• Sep 23rd 2010, 01:27 PM
emakarov
Good question. Whey you say, "so using substitution [s'] =< [t']", do you mean, that, since [s] is [s'], [t] is [t'] and [s] is known to be <= [t], we get [s'] <= [t']? The problem with this is that, well, <= on classes is not well defined. Indeed, given two equivalence classes A and B, how do you choose the representatives? Suppose you have some way; for example, if we are talking about numbers, choose the least prime numbers in A and B and compare them. Then it does not matter what the relationship is between R, which is used to compare representatives, and the ~, which is used to form equivalence classes. However, it may be the case that A <= B, s in A, t in B and ~Rst.

You are asked to show precisely that this situation is impossible. Namely, that for any s ~ s' in A and t ~ t' in B, Rst iff Rs't'. This requires using the relationship between ~ and R, as well as properties of R.
• Sep 23rd 2010, 02:08 PM
jimbob11
Ok, in short, i suppose you could say that since I'm even using [s'] <= [t'] and its definition in my deduction shows that I'm assuming that <= is meaningful - which is, of course, what needs to be shown. Thanks, i knew i couldn't be that trivial.