High-school students and undergraduates are (almost) always taught the following definition of an equivalence relation.
A binary relation on a set
is an equivalence iff it satisfies
- the reflexive property: for all
in
,
,
- the symmetric property: for all
in
, if
, then
, and
- the transitive property: for all
in
, if
and
, then
.
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 on a set
is an equivalence iff it satisfies
- the reflexive property: for all
in
,
, and
- the euclidean property: for all
in
, if
and
, then
.
Exercise: Show that a binary relation on a set
is reflexive, symmetric and transitive iff it is reflexive and euclidean.
13 comments
Comments feed for this article
July 9, 2009 at 2:29 pm
Todd Trimble
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
Suppose
and
. By the symmetric property
. By transitive property applies to
and
we have
. So it is Euclidean.
July 9, 2009 at 5:44 pm
Vishal Lama
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.
July 9, 2009 at 6:50 pm
Akhil Mathew
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
, we have
, and the proof is analogous.
July 10, 2009 at 8:48 pm
Gilbert Bernstein
In Maclane and Birkhoff’s Algebra the following exercise for relations appears:
“A relation
on a set
to itself is called ‘circular’ if
and
imply
. 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:
:
and
means that
.And this means that
.
:First prove symmetry.
and
means that
.
and
means
.From the symmetry we know that
.
.
And transition:
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. 😉
July 12, 2009 at 9:59 pm
Vishal Lama
Aaron, I am glad you liked this post. 🙂 My favorite posts are the ones written by Todd, by the way!
October 28, 2009 at 8:54 pm
Rashad
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
equivalence relation .
February 5, 2018 at 12:51 pm
Sueann Almen
A liberal schooling is a cohesive collection of experiences which generally includes the examine
of natural sciences (including mathematics), social sciences and
the humanities https://math-problem-solver.com/ . Answer: Combining
a mathematics major with one other main can be an ideal
thought.
April 15, 2019 at 11:23 am
prof dr mircea orasanu
as is very important and interesting observed prof dr mircea orasanu and prof drd horia orasanu