How can I prove that these relations are bijective maps?

In summary: S, ##(a,b)## is also in S.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
  • #1
seismichills
3
0
<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:
Physics news on Phys.org
  • #2
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
seismichills said:
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
seismichills said:
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.
Stephen Tashi said:
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.
 
  • Like
Likes Delta2
  • #5
fresh_42 said:
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:

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

1. What is a bijective map?

A bijective map is a function between two sets that is both injective (one-to-one) and surjective (onto). This means that each element in the first set has a unique corresponding element in the second set, and every element in the second set has at least one corresponding element in the first set.

2. How can I prove that a function is injective?

To prove that a function is injective, you must show that different elements in the first set map to different elements in the second set. This can be done by assuming that two elements in the first set map to the same element in the second set, and then using logical arguments to show that this assumption leads to a contradiction.

3. How can I prove that a function is surjective?

A function is surjective if every element in the second set has at least one corresponding element in the first set. To prove this, you can take an arbitrary element in the second set and show that there is at least one element in the first set that maps to it.

4. What is the importance of proving that a function is bijective?

Proving that a function is bijective is important because it ensures that the mapping between two sets is well-defined and reversible. This means that the elements in the first set can be uniquely identified by their corresponding elements in the second set, and vice versa.

5. Can a function be both injective and surjective, but not bijective?

No, a function cannot be both injective and surjective without also being bijective. If a function is injective and surjective, it satisfies all the criteria for being bijective, and therefore must be bijective.

Back
Top