Results 1 to 14 of 14

Math Help - Advanced Mathematics

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    21

    Advanced Mathematics

    Here is a wkst that I have been working on and would like some more insight on. I am a bit lost and what to see what other ppl think! I have somewhat an idea but an confused at parts. Thanks


    If we have a relation R on a set A that is both reflexive and transitive, we can make it into a partial order relation by identifying pairs of elements that are related under R in both directions. We define partial order relation on equivalence classes of elements of A, as shown below. Throughout, let A be a set and suppose that R is a relation on A that is reflexive and transitive. Do no auume anything about the symmetric or antisymmetric properties for R.

    1. Define a second relation ~ on A by saying that a ~ b if and only if aRb and bRa are both true. Show that ~ us an equivalence relation on A.

    2. For each a in A, let [a] = { x exist in A | x ~ a}, that is, the equivalence class of a under the  relation defined in Question 1. Let C be the set of all distinct equivalence classes [a], as a varies over all elements A. Define a relation < on C by saying that [a] < [b] if and only if aRb in A. Show that < is well-definded, that is, if [a] =[c] and [b] = [d], then [a] < [b] implies that [c] < [d]. (hint: remember that [x] =[y] if and only if x ~ y in A. Use this to rephrase what you are asked to show)

    3. With C and < defined in Question 2, show that < is a partial order relation on C. (Hint” for the antisymmetric property, you will again need to use the fact that [x] = [y] if and only if x ~ y in A.)

    4. An example to illustrate the procedure outlined in Question 1-3, let B = {1,2,3,4,5} and let A = P(B), the set of all subsets of B. Define R on A by saying that SRT if and only if (S intersect {1,3,4}) subset (T intersect {1,3,4}). Show that R is both reflexive and transitive in this case, but is neither symmetric nor antisymmetric. List the distinct equivalence classes of A under ~, where ~ us defined on A as in Question 1. (that is, find the set C.) Find a lattice diagram for the partial order relation < on C that is defined in Question 2 and 3. Explain.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Let's start with the first one.

    I'll ask you a question: What do you have to show in order to show that ~ is an equivalence relation on A?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    21
    You have to show that it is reflexive, symmetric and transitive. I kinda get how to show reflexive, but my problem is being general. I like to just use examples.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by mathgirl1188 View Post
    You have to show that it is reflexive, symmetric and transitive. I kinda get how to show reflexive, but my problem is being general. I like to just use examples.
    Well, you need to learn how to apply the general principle to the specific example.

    You do know the general principle of an equivalence relation, so that's good. So start by making this explicit in this example.

    (1) Show for any a in A, we have a~a. So let a be in A. We need to show aRa and aRa, but that's just to say we need to show aRa. But we have aRa since R is reflexive.

    (2) Show for any a and b in A, if a~b then b~a. [I'll let you fill in this part.]

    (3) Show for any a, b, and c in A, if a~b and b~c, then a~c. [I'll let you fill in this part.]

    So try to fill in the parts I left for you. I'll help you if you get stuck.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    21
    Okay...here i go!

    (2) Show for any a and b in A, if a~b then b~a. Let a, b be in A. We want to show that aRb and bRa. If there is a bijection f: A --> B, then ARB and BRA, so A ≈ B. Hence a exit in A then a exist in B, so a~b because ARB. Therefore, with BRA we can say b~a. And so it is symmetric.

    (3) Show for any a, b, and c in A, if a~b and b~c, then a~c. We want to show that aRb and bRa implies aRc. But we have aRb and bRa, since R is transitive. Hence we can imply that aRc.

    I am kind of ify on (2) but feel I am in the right direction! Thoughts?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by mathgirl1188 View Post
    (2) Show for any a and b in A, if a~b then b~a. Let a, b be in A. We want to show that aRb and bRa. If there is a bijection f: A --> B, then ARB and BRA, so A ≈ B. Hence a exit in A then a exist in B, so a~b because ARB. Therefore, with BRA we can say b~a. And so it is symmetric.
    I don't see where you got anything about bijections; and there is no B involved in this. Your argument makes no sense to me at all.

    We need to show that for any a and b in A, if a~b then b~a.

    So assume a and b in A and a~b. So, by definition of '~', we have aRb and bRa. So, by definition of '~', we have b~a.

    Quote Originally Posted by mathgirl1188 View Post
    (3) Show for any a, b, and c in A, if a~b and b~c, then a~c. We want to show that aRb and bRa implies aRc. But we have aRb and bRa, since R is transitive. Hence we can imply that aRc.
    No, that's not right at all.

    We need to show that for any a, b and c in A, if a~b and b~c, then a~c.

    So suppose a, b and c in A and a~b and b~c. So, by definition of '~' we have aRb and bRa and bRc and cRb. So, since we have aRb and bRc, by transitivity of R, we have aRc. And, since we have cRb and bRa, by transitivity of R, we have cRa. So we have both aRc and cRa, so, by definition of '~', we have a~c.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2010
    Posts
    21
    what about this approach for (2)
    a, b exist in A and a~b implies a = b, but that can also be written as b = a which than implies that b ~ a and is symmetric.

    or

    a~b can be written as a ≡ b(mod n), which than is a - b = nq for some q in A, then a - b = -(a - b) = -nq = n(-q) so that b ~ a
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2010
    Posts
    21
    for (2) are you allowed to assume aRb and bRa since it said above that we cannot assume anything about symmetric or antisymmetric properties for R.

    That is where I am lost than!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by mathgirl1188 View Post
    what about this approach for (2)
    a, b exist in A and a~b implies a = b
    No, that is incorrect. There is no basis for to infer a = b.

    Quote Originally Posted by mathgirl1188 View Post
    a~b can be written as a ≡ b(mod n)
    That makes no sense to me at all; where did 'n' come from? a and b are just variables ranging over ANY kind of thing, not necessarily numbers of any kind.

    Please take whatever time it takes to understand the proofs I gave. Those are the most straightforward kind of proofs for this kind of problem. You shouldn't complicate the problem with notions about bijections and mod and things that aren't pertinent to the problem.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by mathgirl1188 View Post
    for (2) are you allowed to assume aRb and bRa since it said above that we cannot assume anything about symmetric or antisymmetric properties for R.

    That is where I am lost than!
    I infered aRb and bRa, because I have a~b, which, by definition of '~', MEANS aRb and bRa.

    That's the key step in proofs like this. You have to "unpack" the meaning of '~'. Where '~' occurs, you need to replace it in terms of 'R', as '~' is defined in terms of 'R'.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Apr 2010
    Posts
    21
    Okay, I am following your thought process on those proofs. So would #2, 3, and 4 follow the same idea? I think 4 is a bit more specific instead of general. But for #2 and 3 do we follow the process of:

    a ~ b if an only if aRb and bRa. So ~ is an equivalence relation on S. This is b/c we define a partial order relation < on equivalence classes of sets under ~ by saying that [a] < [b] if and only if aRb.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by mathgirl1188 View Post
    a ~ b if an only if aRb and bRa. So ~ is an equivalence relation on S.
    (I don't know what S is.) In (1) we showed that ~ is an equivalence relation on A.

    Are you asking about question (2) now? There we are asked to show:

    If [a] = [c] and [b] = [d] and [a] < [b], then [c] < [d].

    So assume [a] = [c] and [b] = [d] and [a] < [b].

    Now, unpack those statements, and unpack what you want to prove, which is [c] < [d]. Then see how you can use all that unpacked information to prove [c] < [d].

    By the way, this exercise is an example of an important and common technique in mathematics. The set of equivalence classes induced by an equivalence relation on a non-empty set A is a partition of A. To show that a relation on a partition is properly defined by definining it in terms of arbitrary members of the equivalence classes, we have to show that it doesn't matter which members of the equivalence classes we choose, as for example, to know that addition of rational numbers is well defined we have to know, e.g., that 1/2 + 2/3 = 4/8 + 10/15, and similarly for any other fractional representations of the two rational numbers we want to add.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Apr 2010
    Posts
    21
    So for #2 we know based on a theorem that if we let ~ be an equivalence relation on A and let a, b be elements of A then:
    if a ~ b, then [a] = [b]
    if a not ~ b, then [a] is a subset of [b].

    Hence, since we proved that aRb in #1 we can assume that a < b is true. Therefore, by than above we know that if a~b than [a] = [b] so [a] is a subset of [b] and [b] is a subset of [a]. so since [b] = [d] and b is a subset of [a] than we can assume that [d] exist in [a] and since [a] = [c] and we know that [a] is a subset of [b] than [c] exist in [b] so we can conclude that [c] < [d] because [a] is a subset of [b] and [b] is a subset of [a], so everything relates to each other, since [a] < [b].

    thought??
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by mathgirl1188 View Post
    if a not ~ b, then [a] is a subset of [b].
    I don't see why you say that. Though, we can get [a] subset of [b] anyway, since we have aRb from [a] < [b] and by transitivity of R.

    But, as I said, the problem we want to solve here is simple just by unpacking the premises.

    Quote Originally Posted by mathgirl1188 View Post
    Hence, since we proved that aRb in #1
    No we didn't. But we do derive aRb from the premise in this theorem that [a] < [b].

    Quote Originally Posted by mathgirl1188 View Post
    a < b is true
    I don't see how that even makes sense. < is a relation on C (the equivalence classes of members of A), not a relation on A itself. And your argument goes on with even more stuff that doesn't seem (at least to me) to make sense. (Some of it is so daffy that I have to ask whether you're joking with me about this.)

    I think you're trying to think PAST the very simple and basic outline of what you need to do. As I mentioned, to start this proof, what you need to do is unpack the following statements:

    [a] = [c]

    [b] = [d]

    [a] < [b]

    In other words, translate each one to a statement not using '[ ]' or '<' but using only '~', then translate that to a statement not using '~' but using only 'R'.

    You've got a start by unpacking [a] < [b] to aRb. Now just unpack the other two, and see how you can put together all the unpacked info to prove [c] < [d].
    Last edited by MoeBlee; April 8th 2010 at 07:37 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 16th 2011, 02:22 PM
  2. Advanced communications mathematics
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 21st 2009, 09:18 PM
  3. Mathematics: Discrete-Mathematics (Algorithems)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2008, 07:27 AM
  4. Mathematics Of Degree (the New Mathematics !!!! )
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: August 26th 2006, 08:35 PM

Search Tags


/mathhelpforum @mathhelpforum