Mathematical Relations

Recent changes

Table of contents

Links to this page

FRONT PAGE / INDEX

Subscribe!

My latest posts can be found here:

Colins Blog

Previous blog posts:

Additionally, some earlier writings:

Introduction

Ubiquitous 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

Throughout this post I'll talk about "sets" and "collections". There is a technical difference, but in the main I'll use "set" in the more technical sense and "collection" in a less formal sense.
For the purposes of this post they are pretty much the same thing.
Let's start with the formal and technical concept of a "relation" between two sets. The informal concept is to have two sets, $A$ and $B,$ to choose element $a$ from $A$ and $b$ from $B$, and ask "Are these two elements related?" The answer is either Yes or No, so we have two buckets with those labels. If the answer for a pair $(a,b)$ is "Yes" then we put it in the "Yes" bucket, and similarly for "No". By this way of thinking, a "Relation" is a collection of "The Chosen Ones", the pairs for whom the answer is "Yes".

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 think of ">" as a relation;
We can think of "=" as a relation;
We can think of "is a multiple of" as a relation;
We can think of "is a prime multiple of" as a relation;
We can think of "Leaves the same remainder on division by 37" as a relation.

In general, there need not be a clean, clear, simple rule to say which pair goes in the "Yes" bucket - we could simply choose some pairs at random, chuck them in the bucket, and say "That collection of pairs is my relation. But in general we have some purpose to our collection.

We can now ask questions about the relation.

Reflexivity

Notation: given a set $S$, the set $S^2$ is the set of all pairs $(a,b)$ where $a$ and $b$ are chosen from $S$, and need not be different. Thus a relation, the collection of pairs we have chosen to put in the "Yes" bucket, is a subset of $S^2$.
Suppose we have a set $S$, and some relation between $S$ and itself. We'll call the relation $R$, and so we can think of $R$ as a subset of $S^2$.

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.

The relation ">" is not reflexive;
- It is not the case that 3>3.
The relation "=" is reflexive;
The relation "is a multiple of" is reflexive;
The relation "is a prime multiple of" is not reflexive;
- ... using the usual modern convention that 1 is not prime.
The relation "leaves the same remainder on division by 37" is reflexive.

Transitivity

Another 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?

The relation ">" is transitive;
The relation "=" is transitive;
The relation "is a multiple of" is transitive;
The relation "is a prime multiple of" is not transitive;
The relation "leaves the same remainder on division by 37" is transitive.

Symmetry and Anti-Symmetry

Again, 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$?

If the answer is always "Yes" then $R$ is "Symmetric";
If the answer is always "No" then $R$ is Anti-Symmetric;
If the answer is sometimes "Yes" and sometimes "No", then the relation is neither symmetric nor anti-symmetric.

Examples:

The relation ">" is anti-symmetric;
The relation "=" is symmetric;
The relation "is a multiple of" is anti-symmetric;
The relation "is a prime multiple of" is anti-symmetric;
The relation "leaves the same remainder on division by 37" is symmetric.

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 non-trivial multiple of".

We can also throw in all pairs of the form $(s,s)$ to make a relation reflexive.

The "Reflexified" (not a real word) version of ">" is the relation "is greater than or equal to".
The reflexification of the transitive closure of "is a prime multiple of" is the relation "is a multiple of".

Going meta: The relation "is a super-set of" can be applied to relations so we can have relations of relations.

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 relations

Sometimes 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$.

Always look out for the word "clearly". Some people us it in the sense of "I can see that this is obvious and you can't, so I'm cleverer than you." That annoys me. I use it in the sense of "When you find the right way to think about this, you'll see it's obvious, and then you're standing in the right place to understand the next part more easily.
At least, that's what I try to do - I don't always succeed.
We wonder if a relation like this is necessarily reflexive. Well, take a thing $s$ and we ask "Is $s$ just as good as $s$ for our purpose?" Given that they're the same thing, the answer would clearly(!) have to be yes.

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:

A relation that is Reflexive, Transitive, and Symmetric is called an "Equivalence Relation".

Equivalence classes

Let'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.

There are dragons here too, related to sizes of infinity. Again, I'll point, shout, and run away.
There may be elements of $S$ not yet chosen, so we can pick another one, $s_1$, and do the same again. And again, and again, and so on.

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 Sets

One final diversion.

Some people require Reflexivity, some people specifically require Anti-Reflexivity, that is, that $(a,a)$ is never in $R$. The choice is a matter of convenience, the two definitions are effectively equivalent.
If a set $S$ has a relation $R$ that is both Transitive and Anti-Symmetric, then the relation $R$ is said to be a "Partial Order on $S$". Examples include ">" on numbers, and "Is a superset of" for sets.

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.

Conclusion

The 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.

<<<< Prev <<<<

Introducing Big Oh

>>>> Next >>>>

Big Oh And Relations ...