Prove/Disprove that the following relation is a (right-) congruence relation: $w R_3 v \iff$ All characters that occur in the word $w$ and only these occur in the word $v$.
Note: A character $x\in\Sigma$ occurs in $w\in \Sigma^*$, if and only if $\exists w',w'':w=w'\cdot x \cdot w''$
Right congruence is defined as the following:
Let $\Sigma =\{a,b,c\}$. A relation $R\subseteq \Sigma^* \times \Sigma ^*$ is called (right-) congruence relation on $(\Sigma^*,\cdot)$ if and only if $R$ is a equivalence relation on $\Sigma^*$ and $$\forall x,y\in \Sigma^*: xRy\implies (\forall z\in \Sigma^*:x\cdot zRy\cdot z)$$
$\Sigma$ is a character.
$\Sigma^n$ is the set of all words with length $n$.
$\Sigma^*$ is defined as $\bigcup\limits_{n\in\mathbb{N}}(\Sigma^n)$
The "$\cdot$" is the dot operator for the concatenation of two words $w=w_1w_2\dots w_n$, $v=v_1v_2\dots v_m$, (which are $n$-touples) where $v\cdot w:= w_1w_2\dots w_nv_1v_2\dots v_m$.
I know, that the relation is indeed a congruence, but I'm not really sure how to prove it in a formal way. These are my thoughts:
Reflexive: Every character that occurs in $w=w_1\dots w_n$ $(n\in\mathbb{N})$ occurs in $w$, in other words $w=w$.
Symmetric: Let $w=w_1\dots w_n$ with $w_1\neq w_2 \neq \dots \neq w_n$ and $v=v_1\dots v_m$. Suppose $wRv$: That means, that every $w_i$ with $0<i\leq n$ is "mapped" on to one or more $v_j$ with $0<j\leq m$. The bad thing is, that the mapping is not bijective (that would make the prove a lot easier), because there are elements in $v$ which can be duplicates. (How to go on now?)
Transitive:?
Making it into an answer then, let $ S(w) \doteq \{x \in \Sigma \,:\, x \text{ is a character of } w\} $, define $w R v \iff S(w) = S(v)$ an equivalence relation since $=$ is an equivalence on sets.
In fact, $S(w \cdot v) = S(w) \cup S(v)$ so if $x R y$ we have
$$ S(x\cdot z) = S(x) \cup S(z) = S(y)\cup S(z) = S(y \cdot z) $$
then $x \cdot z R y \cdot z$ for any $z$. We have then that $R$ is a right-congruence. I would say that we have also $z \cdot x R z \cdot y$, making it a left-congruence too.