Results 1 to 3 of 3

Math Help - show a binary relation is well-defined

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    6

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    6
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Well defined binary operation
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 27th 2011, 12:19 PM
  2. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  3. Recurrence Relation for a binary string
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 25th 2010, 02:55 PM
  4. Binary relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 3rd 2008, 11:58 AM
  5. binary relation
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 24th 2008, 10:34 AM

Search Tags


/mathhelpforum @mathhelpforum