I am having the following relation with the set A and B:

$$ (x_1, y_1) \sim_{A\times B} (x_2, y_2) \iff\; x_1 \sim_A x_2\ \;\land\; \; y_1 \sim_B \; y_2 $$

I haved already proved, that it is a equivalence relation. Now I search the equivalence class for $$\sim_{A\times B}$$

I know the definition of an equivalence class $$ [x]:=(y\in A\mid x\sim y) $$

$$ ⟨x′,y′⟩∈[⟨x,y⟩]_{A×B}\\ if\ and\ only\ if\ x′∈[x]_A\ and\ y′∈[y]_B$$ $${ Now\ I\ need\ a\ way\ to\ describe\ this:\ } {⟨x,y⟩:x∈X\ and\ y∈Y}$$

What is the amount of the equivalence classes of this relation? How can I write it down?


You just need to use the Cartesian product. Then you can write: \begin{align*} [x,y]_{A\times B} &= \{(x',y') \in A\times B\ |\ (x',y')\sim_{A\times B} (x,y)\}\\ &= \{(x',y') \in A\times B\ |\ x' \in [x]_A \quad \text{and}\quad y'\in [y]_B\}\\ &= \{(x',y') \in [x]_A\times [y]_B\}\\ &= [x]_A\times [y]_B \end{align*}

Now, say we have $n_A$ different equivalence classes in $A$ and $n_B$ different equivalence classes in $B$. Then the number of different equivalence classes in $A\times B$ is $n_A\cdot n_B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.