relations multipication and functional properties

81 Views Asked by At

I've been trying to solve this question without any success. Would you help me please?

Let $A={1,2,3}$ and let $M$ be the set of all relations over $A$. Let $s:M\to M$ be the function that assign for every $R \in M$ it's symmetric complement $$R\cup R^{-1} = R \cup \{\langle a,b\rangle \mid \langle b,a\rangle \in R\}.$$
Prove or disprove:

  1. $s$ is injective

  2. $s$ is surjective

  3. (what i'm really having a trouble with) for every $R_1,R_2 \in M$ $s(R_1R_2)=s(R_1)s(R_2)$.

  4. for every $R \in M$ $s(s(R))=s(R)$

What I've done

  1. since s assigns for every $R \in M$ its $R^{-1}$, then if we take a raondom $R \in M$ it means that $\langle R,R'\rangle \in s$ because $s \subseteq M \times M$, and then be can say that $R'=s(R)$. so if we take $R,S \in M$ so that $S \neq R$ then we have $t(R) \neq t(S)$, i.e because every element in the domain has more than one link in the range(not transitive).

  2. $s$ is surjective because if we take for instance $w \in x$ there most be at least one $y \in z$ so that s(z)=x, and because $s:M\to M$ and the given information it assigns for every $R$ its $R^{-1}$, then we can say that $R=s(t)$, thus $s(R)= s(s(t)=s(t)=R$.

  3. i don't know how to solve it, i'm having hard time with it, would appreciate your help.

  4. since we proved that s is surjective, we can use that property to assert that $s(s(R))=s(R)$ for every $R \in M$ because of its transivity.

please help me if you can, i've elaborated and explained what i've done and why and tried to write it in a mathmatical way.

**regarding the term symmetric complement, here's an example that will clarify it, and again, sorry for not knowing its english name: sorry, i don't know how it's called in english, but i'll give an example of it: say that A={1,2,3,4} and the relation R over A is: $R={<1,2>,<3,3>,<3,4><4,1>}$ then the property i'm looking for is ${<1,2>,<3,3><3,4><4,1><2,1><4,3><1,4>}$

2

There are 2 best solutions below

0
On

s is not injective because s maps {(1,2)} and {(2,1)} to the same element.
s is not surjective because {(1,2)} is not in its range.

1
On

ss(R) = s(R) because (exercise) $(R \cup R^{-1})^{-1} = R \cup R^{-1}$.

To disprove 3, let R1 = {(1,2)}, R2 = {(2,1)}.