This is probably a rather stupid question, but I have looked at several different sources and still do not seem to understand this... I am teaching myself Group theory from a set of lecture notes, which have a section on equivalence relations on sets. In the notes, no mention whatsoever is made of the cartesian product of a set; it simply defines the equivalence relation, ~, on a set X as being a relation which is reflexive, symmetric, and transitive, and given examples of

"a)$X = Z$ the relation $\equiv _n$ defined as $a \equiv _n b \iff n | b-a$"

"b) $X$ any set of groups, $\cong$ “isomorphic to” is an equivalence relation."

Now when I looked online (e.g. Wolfram Alpha) and in a book, they both define an equivalence relation in terms of a "subset, $R$, of $X \times X$".

Wikipedia has this quite concealed. It defines

a binary relation that is at the same time a reflexive relation, a symmetric relation and a transitive relation.

and I just learned from this that a binary relation is a collection of ordered pairs of elements of a set.

Now I have looked at some stack exchange posts (e.g. this one) in the hope that it may clarify something, but unfortuantely I am still confused. I don't get what some ordered pairs of a set have to do with a statement regarding the elements of the set itself (they are just ordered pairs, right?) unless the specific subset $R$ of the Cartesian product of the two sets is such that some relation between the two elements is satisfied, for example all of the ordered pairs have elements which are congruent modulo n. Or in the second example, the elements-here groups- in each pair in the subset $R$ are isomorphic.

Is this the right kind of idea? If it is, I am still struggling to see why the equivalence relation would be the 'some set of ordered pairs of elements' as opposed to the relation between them as it says in the lecture notes. I.e. in the lecture notes the 'irsomrphic to' and 'congruent modulo n' are said to be the equivalence relations, not the set of ordered pairs of elements satisying this!

  • $\begingroup$ In set theory language, a (binary) relation on $X$ is a subset of the cartesian product $X \times X$. $\endgroup$ – Mauro ALLEGRANZA Jul 10 '17 at 12:00
  • $\begingroup$ A relation on a set $X$ is simply a subset $R\subset X\times X$. What this means is for any two elements in $X$, one can compare them by means of a relation if they are found in as an ordered pair within $R$. For example a relation is reflexive if $\forall x:(x,x)\in R$, symmetric if $(x,y)\in R\implies (y,x)\in R$, transitive if $(a,b), (b,c)\in R\implies (a,c)\in R$ $\endgroup$ – George Jul 10 '17 at 12:00
  • $\begingroup$ Th relation father-to-son is a subset of the cartesian product $\text {Humanity} \times \text {Humanity}$. $\endgroup$ – Mauro ALLEGRANZA Jul 10 '17 at 12:01
  • $\begingroup$ In this case, every memeber of the set $H \times H$ is a pair like $(John, Bill)$ where $John$ is the father of $Bill$. $\endgroup$ – Mauro ALLEGRANZA Jul 10 '17 at 12:02
  • 1
    $\begingroup$ In your example with $\mathbb Z$ we have that $(a,b) \in \ \equiv_n$ iff ... where $\equiv_n$ is a binary relation, i.e. a subset of $\mathbb Z \times \mathbb Z$. Every element of the set $\equiv_n$ is a pair $(a,b)$ such that $a$ and $b$ satisfy the condition following the dots. $\endgroup$ – Mauro ALLEGRANZA Jul 10 '17 at 12:03

By definition, any binary relation on a set $A$ is a subset of $A\times A$. That actually goes the other way around, so every subset of $A\times A$ is a relation.

In your example, if $A=\mathbb Z$, for example:

"a)$X = Z$ the relation $\equiv _n$ defined as $a \equiv _n b \iff n | b-a$"

this relation, $\equiv_n$, is actually the set $$\equiv_n = \{(a,b)\in\mathbb Z^2| n|b-a\}$$

However, because we very often talk about relations, we decided on an alternative way of writing them. If $R\subseteq A\times A$ is a relation, then instead of writing $(a,b)\in R$, we write $aRb$ to mean the same thing. So, instead of writing $$(a,b)\in \equiv_n$$ we write $$a\equiv_nb$$ which is easier to read.

So, to answer your confusion

I am still struggling to see why the equivalence relation would be the 'some set of ordered pairs of elements' as opposed to the relation between them

the relation between them is exactly the same thing as some set of ordered pairs of elements.


From an abstract point of view, a binary relation on a set X is indeed a pair $(R,X)$ such that $R\subset X\times X$. The link with the more intuitive notion is best explained with an example:

Consider the binary relation $\bmod_n$ on $\mathbf Z$ defined as $$\bmod_n(x,y)\iff n\mid x-y$$ The corresponding subset $M\subset\mathbf Z\times\mathbf Z$ comprises the elements \begin{align} &(0,0),\, (0,n),\, (0,-n),\,(0,2n),\,(0,-2n),\,\dots\dots\\ &(1,0),\, (0,1+n),\, (0,1-n),\,(0,1+2n),\,\dots\dots\\ &\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots.. \end{align} Observe it is equivalent to define $\bmod_n(x,y)$ by a defining property (set comprehension) or by being a member of the list (set extension). Anyway $(x,y)\in M$ is a defining relation too.


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.