0
$\begingroup$

I am studying Naive Set Theory and stuck to understand algebraic part of equivalence relation. Can you please explain what these inclusions mean?

The algebra of relations provides some amusing formulas. Suppose that, temporarily, we consider relations in one set $X$ only, and, in particular, let $I$ be the relation of equality in $X$ (which is the same as the identity mapping on X). The relation I acts as a multiplicative unit; this means that $IR = RI = R$ for every relation $R$ in $X$. Query: is there a connection among $I$, $RR^{–1}$, and $R^{–1}R$? The three defining properties of an equivalence relation can be formulated in algebraic terms as follows: reflexivity means $I ⊂ R$, symmetry means $R ⊂ R^{–1}$, and transitivity means $RR ⊂ R$.

Halmos, Paul R.. Naive Set Theory (Dover Books on Mathematics) (p. 41). Dover Publications. Kindle Edition.

$\endgroup$
4
  • 2
    $\begingroup$ In set theory, relations between elements of a set are encoded as sets of pairs, therefore the inclusions mean inclusions as sets. $\endgroup$ – user239203 Jun 4 at 8:12
  • 2
    $\begingroup$ Example: reflexivity. You have to check that if $I = \{ (a,a) \mid a \in X \} \subseteq R$ then relation $R$ is reflexive. And similarly for the other two properties of an Equivalence relation. $\endgroup$ – Mauro ALLEGRANZA Jun 4 at 8:13
  • 2
    $\begingroup$ A relation $R$ on a set $X$ is a set of pairs: $R \subseteq X \times X$. $\endgroup$ – Mauro ALLEGRANZA Jun 4 at 8:17
  • 1
    $\begingroup$ You can find several related posts here. For example: If $R$ is a transitive relation, then $R\circ R\subseteq R$ and the questions linked there. $\endgroup$ – Martin Sleziak Jun 4 at 9:56
1
$\begingroup$

In set theory a binary relation on a set $X$ is some (any) subset of $X\times X.$ We can write $I_X=\{(x,x):x\in X\}$, which is a subset of $X\times X.$ For subsets $R, S$ of $X\times X$ we can write $$R^{-1}=\{(y,x): (x,y)\in R\}$$ and $$RS=\{(x,z):\exists y\,(\,(x,y)\in R\land (y,z)\in S\,)\}.$$ In particular $RR=\{(x,z):\exists y\,(\,(x,y)\in R\land (y,z)\in R\}$.

We can also show that a binary relation $R$ on $X$ is an equivalence relation iff $I_X\subseteq R=R^{-1}=RR.$

BTW. In topology $I_X$ is called the diagonal of $X\times X.$

$\endgroup$
1
  • $\begingroup$ If you're interested in paring down the def'n, observe that if $\emptyset\ne R=R^{-1}=RR $ then $I_X\subset R.$ $\endgroup$ – DanielWainfleet Jun 5 at 16:57

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.