1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How can I prove that these relations are bijective maps?

  1. Sep 15, 2018 at 5:50 PM #1
    <Moderator's note: Moved from a technical forum and thus no template. Also re-edited: Please use ## instead of $$.>

    If ##R_{1}## and ##R_{2}## are relations on a set S with ##R_{1};R_{2}=I=R_{2};R_{1}##. Then ##R_{1}## and ##R_{2}## are bijective maps

    ##R_{1};R_{2}## is a composition of two relations

    For the surjectivity part, I showed that if ##(a,b)\in I## then ##(a,c)\in R_{1}## and ##(c,b)\in R_{1}## and ##(a,c)\in R_{2}## and ##(c,b)\in R_{2}## for some ##c\in S##. Now for arbituary ##(x,y)\in R_{1}## we have ##(x,z)\in I## which implies that ##(y,z)\in R_{2}##. But also ##(y,z)\in R_{1}##, so ##R_{1}## is surjective. Similar argument for ##R_{2}##


    And for Injectivity, I've tried to show that if ##aR_{1};R_{2}c## and ##bR_{2};R_{1}c##, then ##a=b## but I am not entirely sure what ##a=b## means in this context.
     
    Last edited by a moderator: Sep 15, 2018 at 6:14 PM
  2. jcsd
  3. Sep 16, 2018 at 6:54 AM #2

    verty

    User Avatar
    Homework Helper

    a = b means the same thing in every context as far as I know, which is that a can take the place of b or b can take the place of a.
     
  4. Sep 16, 2018 at 12:58 PM #3

    Stephen Tashi

    User Avatar
    Science Advisor

    It's good that you question that!

    Equality is only defined relative to an equivalence relation. This problem has several different types of equality (which may turn out to be all the same, but we cannot begin by assuming they are).

    Using notation to distinguish various equalities, we have
    ##x =_{(R_1)}y \ \ ## denoting ##(x,y) \in R_1##.
    ##x =_{(R_2)}y \ \ ## denoting ##(x,y) \in R_2##.
    ##x =_{(R_1;R_2)}y \ \ ## denoting ##(x,y) \in R_1; R_2##.

    We also have the equality relation used by the person who is doing the proof!

    The person doing the proof is talking about various sets. He must assume there is a way to tell whether two elements in these sets are "equal" from his point of view. So we can add the relation
    ##a = b## to denote equality with respect to that relation.

    For example, if a person writing a proof used the notation "##(b,b)##", it may happen that ##(b,b) \notin R_1##. However a person using the notation takes the viewpoint that both elements in the ordered pair ##(b,b)## are "equal" from his point of view.
     
  5. Sep 16, 2018 at 2:59 PM #4

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    I'm a bit confused by your proof. I think there should be the unique notation ##(a,b)\in R## and not something like ##aR##. This is generally something I find wrong: you don't quantify your variables.

    E.g. "... if ##(a,b)\in I## then ##(a,c)\in R_{1}## and ##(c,b)\in R_{1}##" makes no sense to me.
    It should be: "... if ##(a,a)\in I=R_1;R_2## then there is a ##c\in S## such that ##(a,c)\in R_{1}## and ##(c,a)\in R_{2}##"
    depending whether you read ##R_i;R_j## from left to right or from right to left which you haven't said. But I do not understand where your choices come from or what exactly you claim and what you are assuming. Also "I showed" is very confusing. Where? Did you mean "I will show"? And surjectivity of which ##R_i##? Both at the same time? The closer a statement is to the basics of set theory, the more precise the language has to be. Yours is not - or at least I cannot follow you without making additional assumptions on what you might have meant.
    I'm a bit confused, as at prior we cannot assume the relations to be equivalence relations, so the notation on the LHS seems inappropriate to me.
     
  6. Sep 16, 2018 at 4:07 PM #5

    Stephen Tashi

    User Avatar
    Science Advisor

    You are correct. My notation only makes sense if we are given that the relations involved are equivalence relations. My point is that the question concerning the context of "a=b" must be interpreted from the viewpoint of the person writing the proof , not from membership in some different relation involved in the proof.
     
  7. Sep 17, 2018 at 3:03 AM #6
    Hey, thanks for your comments, everyone. I've figured out how to do it so I'll post the solution here
     
  8. Sep 17, 2018 at 3:09 AM #7
    If ##(x,z) \in R_{1}## then ##(x,w) \in R_{1};R_{2}## and ##(z,w) \in R_{2}## for some ##w \in S##. But ##R_{1};R_{2}=I## so ##x=w\,.##

    Now, suppose ##(y,z) \in R_{1}## then ##(y,w)\in R_{1};R_{2}## since ##(z,w) \in R_{2}\,.## Hence ##y=w=x\,.## Same argument for ##R_{2}\,.##

    Now to prove surjectivity, suppose ##(x,y) \in R_{1};R_{2}=I\,,## then for any ##y , y=x\,.## So obviously ##R_{1};R_{2}## is surjective.
    Since the composite of ##R_{1}## and ##R_{2}## is surjective, so are ##R_{1}## and ##R_{2}\,.##
     
    Last edited by a moderator: Sep 17, 2018 at 9:20 AM
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted