• Support PF! Buy your school textbooks, materials and every day products Here!

How can I prove that these relations are bijective maps?

  • #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:

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
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.
 
  • #3
Stephen Tashi
Science Advisor
7,016
1,237
I am not entirely sure what ##a=b## means in this context.
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.
 
  • #4
12,652
9,172
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.
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.
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##.
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.
 
  • #5
Stephen Tashi
Science Advisor
7,016
1,237
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.
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.
 
  • #6
Hey, thanks for your comments, everyone. I've figured out how to do it so I'll post the solution here
 
  • #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:

Related Threads on How can I prove that these relations are bijective maps?

  • Last Post
Replies
15
Views
837
  • Last Post
Replies
2
Views
6K
  • Last Post
Replies
3
Views
5K
Replies
28
Views
25K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
0
Views
815
Replies
5
Views
1K
Replies
1
Views
722
Replies
4
Views
3K
Top