Todd and Vishal’s blog

Topological Musings

A relation is an equivalence iff it is reflexive and euclidean

July 9, 2009 in Elementary Math Problem Solving | Tags: equivalence relation, euclidean, reflexive

High-school students and undergraduates are (almost) always taught the following definition of an equivalence relation.

A binary relation $R$ on a set $A$ is an equivalence iff it satisfies

• the reflexive property: for all $a$  in $A$, $a R a$,
• the symmetric property: for all $a, b$ in $A$, if $a R b$, then $b R a$, and
• the transitive property: for all $a, b, c$ in $A$, if $a R b$ and $b R c$, then $a R c$.

However, there is another formulation of an equivalence relation that one usually doesn’t hear about, as far as I know. And, it is the following one.

A binary relation $R$ on a set $A$ is an equivalence iff it satisfies

• the reflexive property: for all $a$  in $A$, $a R a$, and
• the euclidean property: for all $a, b, c$ in $A$, if $a R b$ and $a R c$, then $b R c$.

Exercise:  Show that a binary relation $R$ on a set $A$ is reflexive, symmetric and transitive iff it is reflexive and euclidean.

About these ads

Like Loading...

• 221,457 hits

11 comments

Comments feed for this article

On why it’s called “euclidean”, see this page at the recently created nLab. The commentary and history given there (probably due to Toby Bartels; I didn’t check) is interesting.

The nLab is a wiki on general mathematics, so far written mostly by regular customers at the n-Category Café. Anyone is welcome to contribute however. Many of the articles are written by people with strong category-theoretic inclinations, which could be taken either as invitation or warning I guess but there is both a rich treasure trove already in place and infinite scope for expansion.

July 9, 2009 at 2:44 pm

watchmath

This is the first time I see this equivalence formulation. Do you know the case where it is easier to verify equivalence relation by using this eqivalent definition?

I hope you don’t mind that I do the exercise
$(\Rightarrow)$ Suppose $aRb$ and $aRc$. By the symmetric property $bRa$. By transitive property applies to $bRa$ and $aRc$ we have $bRc$. So it is Euclidean.

$(\Leftarrow)$ Supppose $aRb$. Since it is reflexive, then $aRc$ for $c=a$. By the Euclidean property we have $bRc$, i.e, $bRa$. Now suppose $aRb$ and $bRc$. Since it is symmetric then $bRa$. By applying the Euclidean property to $bRa$ and $bRc$ we have $aRc$.

Todd,

Thanks for that piece of info! I think there is something not quite right about the use of tags on nLab. I mean, a search for “equivalence left euclidean” on Google returns the nLab page you mentioned as the first search result, but the same page is only seen on the fourth page of search results for “equivalence euclidean”, which actually returns the blog post I just wrote as the first search result! Would you look into this (anomaly)? Perhaps introduce appropriate tags in the abovementioned nLab page.

watchmath,

If you click on the nLab page that Todd provided a link to, you may find an answer there. For example, using the alternative formulation, proving congruence (on the set of triangles in the Euclidean plane) is an equivalence relation is easy and also intuitive. However, I came across the second formulation via a study of accessibility relation in introductory modal logic.

This is kind of like the alternative conditions used to define a subgroup; a subset S of a group G is a subgroup if e is in S, and for any $x,y \in S$, we have $xy^{-1} \in S$, and the proof is analogous.

In Maclane and Birkhoff’s Algebra the following exercise for relations appears:

“A relation $R$ on a set $X$ to itself is called ‘circular’ if $x R y$ and $y R z$ imply $z R x$. Show that a relation is reflexive and circular if and only if it is reflexive, symmetric, and transitive.” [Edited LaTeX code.]

October 31, 2011 at 4:29 am

Luqing Ye

Answer:
$\Leftarrow$:$x\mathcal{R} y$ and $y\mathcal{R} z$ means that $x\mathcal{R} z$ .And this means that $z\mathcal{R} x$.
$\Rightarrow$:First prove symmetry.$x\mathcal{R} x$ and $x\mathcal{R} y$ means that $y\mathcal{R} x$.
And transition:$x\mathcal{R} y$and $y\mathcal z$means $z\mathcal{R} x$.From the symmetry we know that $x\mathcal{R} z$.$\Box$.

July 12, 2009 at 4:47 am

Aaron F.

Oooh, cool! Most of the math on this blog is way over my head, but I have a special place in my heart for binary relations, and another special place in my heart for alternative formulations of familiar things. So this may be my favorite Topological Musings post ever.

Aaron, I am glad you liked this post. My favorite posts are the ones written by Todd, by the way!

I’ve only begun following math blogs and studying category theory; this post on Euclidean relations was a pleasant find. I hope I can use it someday on an algebra exam! Hopefully following your blog will help me develop enough to follow some journals…

October 31, 2011 at 10:45 am

Luqing Ye

I think the Euclidean property is very intuitive as long as you regard equivalence property as a double-head arrow connecting two points.

October 31, 2011 at 10:48 am

Luqing Ye

errata:equivalence property $\rightarrow$ equivalence relation .

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 67, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9229453802108765, "perplexity_flag": "middle"}