How can I prove that these relations are bijective maps?

[seismichills]

<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.

 

[verty]

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.

 

[Stephen Tashi]

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.

 

[fresh_42]

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.

 

[Stephen Tashi]

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.

 

[seismichills]

Hey, thanks for your comments, everyone. I've figured out how to do it so I'll post the solution here

 

[seismichills]

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}\,.$