# The Unapologetic Mathematician

## Relations

Sooner or later I’ll have to use relations, so I may as well get the basics nailed down now.

A relation between two sets $X$ and $Y$ is just a subset $R$ of their Cartesian product $X\times Y$. That is, it’s a collection of pairs $(x,y)$. Often we’ll write $xRy$ when $(x,y)$ is in the relation.

A function $f$ is a special kind of relation where each element of $X$ shows up on the left of exactly one pair in $f$. In this case if $(x,y)$ is in the relation we write $f(x)=y$. Remember from our discussion of functions that I was saying every element of $X$ has to show up both at least once and at most once (that is, exactly once). A surjection is when every element of $Y$ shows up on the right side of a pair in $f$ at least once, and an injection is when each element in $Y$ shows up at most once.

Also interesting are the following properties a relation $R$ between a set $X$ and itself might have:

• A relation is “reflexive” if $xRx$ for every $x$ in $X$.
• A relation is “irreflexive” if $xRx$ is never true.
• A relation is “symmetric” if whenever $xRy$ then also $yRx$.
• A relation is “antisymmetric” if whenever $xRy$ and $yRx$ then $x$ and $y$ are the same.
• A relation is “asymmetric” if whenever $xRy$ then $yRx$ is not true.
• A relation is “transitive” if whenever $xRy$ and $yRz$ then also $xRz$.

A very important kind of relation is an “equivalence relation”, which is reflexive, symmetric, and transitive. We’ve already used these a bunch of times, actually. When a group $G$ acts on a set $X$, we can define a relation $\sim$ by saying $x\sim y$ whenever there is a group element $g$ so that $gx=y$. Since the identity of $G$ sends every element of $X$ to itself, this is reflexive. If there is a $g$ so that $gx=y$, then $g^{-1}y=x$, so this is symmetric. Finally, if we have $g$ and $h$ so that $gx=y$ and $hy=z$, then $(hg)x=z$, so the relation is transitive.

When we have an equivalence relation $\sim$ on a set $X$, we can break $X$ up into its “equivalence classes”. Any two elements $x$ and $y$ of $X$ are in the same equivalence class if and only if $x\sim y$. We write the set of equivalence classes as $X/\sim$. For group actions, these are the orbits of $G$.

Show for yourself that in our discussion of cosets that there’s an equivalence relation going on, and that the cosets of $H$ in $G$ are the equivalence classes of elements of $G$ under this relation.

### Like this:

Posted by John Armstrong | Fundamentals

## 2 Comments	»

1. [...] Orders As a bonus today, I want to define a few more kinds of relations. [...]

Pingback by | March 11, 2007 | Reply

2. [...] given a topological space and an equivalence relation on the underlying set of we can define the quotient space to be the set of equivalence classes [...]

Pingback by | April 28, 2010 | Reply

« Previous | Next »

## About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.
{"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": 61, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "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.9333192706108093, "perplexity_flag": "head"}