Mathematical Relations 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
IntroductionUbiquitous in mathematics is the concept of comparing things, and examining the relationships between them. Since we do that all the time and everywhere, it's worth having a look at the concept of a "Relation" in an abstract sense to try to tease out the common themes.
Relations
A common case is where we are looking at the relationships between items from the same set. We can consider this as a special case of the description above, simply taking $A$ and $B$ to be the same set. In this case, then, we have one set, take a pair of elements $(a,b)$ (which need not be different) in a specific order, and ask "Yes" or "No". From now on we will only work with this more restrictive case, we will always have a relation between/on elements from the same set. Examples:
We can now ask questions about the relation.
Reflexivity
Now choose an element $s$ from $S$ and ask: is $(s,s)$ in $R$? If the answer is always "Yes" then we say that $R$ is "Reflexive". In other words, $R$ is "Reflexive" if every element is related to itself.
TransitivityAnother potentially interesting property of relations is that of transitivity. We ask: Given that $(a,b)$ is in $R$, and $(b,c)$ is in $R$, does it necessarily follow that $(a,c)$ is in $R$? In words, if $a$ is related to $b$, and $b$ is related to $c$, is $a$ then related to $c$? If Thor picks up his hammer, and I pick up Thor, have I then, in any real sense, picked up Thor's hammer?
Symmetry and AntiSymmetryAgain, suppose we have a set $S$ and a relation $R$ on pairs from $S$. We can ask: if $a$ and $b$ are different elements of $S$, and $(a,b)$ is in $R$, does that imply that $(b,a)$ is also in $R$?
Cool stuff (optional)The "transitive closure" of a relation is when you take a relation (which we think of as a subset of $S^2$) and throw in exactly those additional pairs necessary to make a (possibly new) relation that is transitive. The transitive closure of "is a prime multiple of" is the relation "is a nontrivial multiple of". We can also throw in all pairs of the form $(s,s)$ to make a relation reflexive.
Warning: here be dragons, so I'm going to point at all the cool ideas, shout "What in the World is That!", and run away ...
Equivalence relationsSometimes we have a collection of things and, for our purposes, some things might be just as good as each other. So we declare that these things are, in this context, "equivalent", and we just proceed with any specific representative of that collection. So let's suppose we have some particular purpose in mind, and we have a set of things we're dealing with, and some are equivalent to each other. This is a relation. We have two things, $a$ and $b$, and we ask "Are these equivalent for our purpose?" So we end up with pairs for which the answer is "Yes". We have a relation. Call it $R$.
So for every $s$, the pair $(s,s)$ is in $R$, so $R$ is reflexive. What about transitivity? If $a$ and $b$ and equally good for our purpose, and $b$ and $c$ are equally good for our purpose, are $a$ and $c$ equally good for our purpose? In symbols, if $(a,b)$ is in $R$, and $(b,c)$ is in $R$, will $(a,c)$ necessarily be in $R$? The key here is the word "equally". If they are genuinely equally good for the purpose, then the answer surely would be "Yes". And finally, what about symmetry? Suppose $a$ and $b$ are equally good for our purpose, does that then imply that $b$ and $a$ are also equally good for our purpose? Again, clearly(!) yes. So our intuitive concept of things being "equivalent for our purpose" leads us to conclude that the resulting relation will be reflexive, transitive, and symmetric. So we make the definition:
Equivalence classesLet's suppose we have a set, $S$, and we have a relation $R$ between elements of $S$, so $R$ is a subset of $S^2$. Remember, $R$ is the collection of pairs $(a,b)$ that we have chosen. Let's further suppose that $R$ is an equivalence relation, so it's reflexive, transitive, and symmetric. Pick an element $s_0$ of $S$, and extract all those elements related to it. This is what we call the "equivalence class of $s_0$". These are the elements which, for the purposes of $R$, are thought of as being "equally good as $s_0$ for our purpose". With a little thought we can see that because of the properties, we will end up with the same collection no matter which initial element we chose.
So our set $S$ can, in a sense, be "Tiled" by collections of things. Within a single "tile" all the elements are equivalent for our purpose, but between tiles they are not. This concept underpins many things in mathematics, including, but not limited to, constructions of the reals (and other things), and modulo arithmetic. The ideas here are deep and powerful.
Partially and Totally Ordered SetsOne final diversion.
If, additionally, every pair of different elements of $S$ have exactly one of $(a,b)$ and $(b,a)$ in $R$, then the relation $R$ is said to be a "Total Order", and $S$ is said to be "Totally Ordered". In this instance ">" on the reals (or integers, or rationals) is a Total Order, but "Is a superset of" is not a Total Order  you may be interested in constructing a specific example of this.
ConclusionThe whole language of Relations, with its concepts of Reflexivity, Transitivity, (Anti)Symmetric, Equivalence Relations, Equivalence Classes, and Orders (both Partial and Total) prove to be immensely powerful. These are ideas that turn up again and again, and in the next post we'll see them in action.
Send us a comment ...

Quotation from Tim BernersLee 