Consider a generic equivalence relation $R$ on a set $S$. By definition, if we partition $S$ using the relation $R$ into $\pi_S$, whose members are the congruence classes $c_1, c_2...$ then

$aRb \text{ iff a and b are members of the same congruence class in } \pi_S$.

But what is the domain and codomain of $R$? Is it $S \rightarrow S $ or $S^2 \rightarrow \text{{true,false}}$?

The reason I ask is to have an idea of the members of $graph(R)$. Does it only contain ordered pairs which are equivalent, i.e. $(a,b)$; or all elements of $S \times S$ followed by whether they are equivalent, i.e. $((a,b), true)$?

Moreover, what would the image of $s \in S$ under $R$ look like? If one suggests that $R(s)$ would return a set of all the equivalent members, then the former definition is fitting.

I suppose the source of confusion is that we rarely think of equivalence relations as 'mapping' from an input to an output, instead it tells us if two objects are similar in some way.

  • $\begingroup$ $Domain=Codomain=S$ and the image of $s\in S$ is the congruence class containing $s$. $\endgroup$ – Shahab Apr 12 '13 at 2:54
  • $\begingroup$ If you found any of the answers here helpful, please upvote them. Also, click the checkmark next to the answer which you found the most helpful to accept it. Thanks. $\endgroup$ – Code-Guru Apr 23 '13 at 2:06

One way to define a relation $R$ on a set $S$ is as a subset of $S \times S$. Using this definition, we can create a graph $G = (S, R)$ where $S$ is the vertex set and $R$ is the edge set. In other words, if $a, b \in S$ are vertices of the graph $G$, then $(a, b)$ is an edge of $G$ if and only if $(a, b) \in R$ (i.e. $aRb$).

Now for an equivalence relation, two vertices are equivalent if and only if they are in the same component. Equivalently, two vertices $a, b$ are equivalent if and only if there is a path from $a$ to $b$.

  • $\begingroup$ I don't think he meant "graph" in a graph-theoretic sense $\endgroup$ – Shahab Apr 12 '13 at 2:23
  • $\begingroup$ @Shahab What other kind of graph would you use for a general relation on a general set S (which may or may not consist of numbers)? $\endgroup$ – Code-Guru Apr 12 '13 at 3:18
  • $\begingroup$ Abstracting the equivalence relation to a simple graph is a fine way to help my understanding. Indeed; I had meant the graph as a subset of the Cartesian of domain and codomain, but thinking in terms of a planar graph is perhaps the best way to visualize the relation. $\endgroup$ – jII Apr 12 '13 at 3:44
  • $\begingroup$ @jesterII Note that the graph of a general relation is not guaranteed to be planar. I'm pretty sure that you are not using the word "planar" by its technical meaning. $\endgroup$ – Code-Guru Apr 12 '13 at 3:48
  • $\begingroup$ Indeed, what I mean by planar is the visual representation $G=(V,E)$, not graph meaning a subset of domain and codomain $graph(R) \subset X \times X$ $\endgroup$ – jII Apr 12 '13 at 19:59

The domain is $S\times S$ and codomain is {true, false}. Said another way, you can just think of any relation as a subset of $S\times S$.

  • $\begingroup$ Consider the identity function $f:S\to S$. It is an equivalence relation. $\endgroup$ – Shahab Apr 12 '13 at 2:56
  • $\begingroup$ Why do you think that? $\endgroup$ – Paul Gustafson Apr 12 '13 at 2:58
  • $\begingroup$ Because it satisfies the definition. $\endgroup$ – Shahab Apr 12 '13 at 3:01
  • $\begingroup$ What is the definition of an equivalence relation? $\endgroup$ – Paul Gustafson Apr 12 '13 at 3:04
  • $\begingroup$ A subset $f$ of $S\times S$ such that $(x,x)\in f, (x,y)\in f\Rightarrow (y,x)\in f, (x,y),(y,z)\in f\Rightarrow (x,z)\in f$, $\forall x,y,z\in S$. $\endgroup$ – Shahab Apr 12 '13 at 3:08

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.