bigideas

I wanted to post on this topic for three reasons. First, it’s connected with relative identity, which I posted about here a while ago. Second, it’s relevant to something I’m chewing over from Davidson over here. Third, it’s maths, and maths is cool.

There are three ideas I want to explain in this post are relation, transitivity and equivalence. Each idea builds on the previous one. The context is set theory, but we won’t need to develop much set theory to get our work done.

In fact, we only need three prerequisites. Number one: A set, which we can treat as just a “bunch of things”, a collection or class. Speaking informally as we are, we can imagine those things are anything we like: people, fuit and vegetables, animals, abstract ideas. I’ll use everyday examples here but the idea is very widely applicable. We’ll always denote a set by a capital letter, say X.

Number two: say we have two sets. The first, X, is the set of people who live on your street. The second, Y, is the set of children who live on your street. Clearly everything that’s an element of Y is also an element of X. We call Y a subset of X.

Number three: We define the product of two sets A and B in the following odd-sounding way. We take each element of A in turn and pair it up with each element of B in turn, putting each pair into a new set called A×B. Say A is a set containing fruits and B contains animals. Then the elements of A×B would be things like (apple, cat), (pear, cat), (banana, camel) and so on.

This last construction is important and a bit weird, so here’s a more common example. Say we want to construct the product of a set with itself: A×A. Let’s make it concrete and say A is the set of the primary colours, so it contains red, green and blue. Then A×A will be the set containing all these pairs:

When you take a product of a set A with itself, it’s usual to write A² instead of A×A.

Right, that’s the preliminaries over with. The idea of a product of a set with itself enables us to define our first term very easily: a binary relation on a set A is any subset of A². This makes “binary relation” a very general idea. All the relations we consider below are binary , so we’ll just call them “relations”. You may like to think about how to construct tertiary or higher-order relations.

A simple example of a relation would be the family relationship of being-an-ancestor-of. Let A once again be the set of people who live on your street. Now take the following subset B of A²: (x, y) is an element of B if and only if x is an ancestor of y. If Jane is John’s mother, then (Jane, John) is an element of B.

We’ll adpot some different notation for this and write x»y if (x, y) is an element of B. So Jane $raquo; John, for example. You can read “»” as “is an ancestor of”. We call » a relation on the set A. We can use any symbol that seems reasonable instead of “»”.

Let’s look at some properties of this relation. From the definition, we can immediately say that if x»y is true (that is, if (x, y) is in B), then y»x must be false. This immediately tells is that x»x can’t be true for any element of A, which is extremely reassuring.

Here’s another thing. Say you know that x»y and y»z. Clearly we must also have x»z. A relation with this property is called transitive. Not all relations are transitive. If we defined “»” to mean “is a parent of” then it wouldn’t be a transitive relation any more. That’s okay — for some kinds of relation we want transitivity and for others we don’t.

One example where we do want it is in something called an equivalence relation. In fact, an equivalence relation is defined as any relation that’s transitive, reflexive (which means x»x for all elements x) and symmetric (which means whenever x»y we must also have y»x).

You probably keep the files on your computer in various different folders. If A is the set of all files, we write x»y if x is in the same folder as y. Let’s check whether this is an equivalence relation, by checking the three criteria are met:

• Reflexivity: x is always in the same folder as itself
• Symmetry: if x is in the same foler as y, then y is surely in the same folder as x
• Transitivity: if x»y and y»z then x»z.

In this case, the symbol “»” might look a bit inappropriate. It’s more usual to use “~” for equivalence relations, so we’d write x~y to mean “x is equivalent to y under the relation ~” or, in this case “x is in the same folder as y.

It turns out (you can try to prove this if you like) that equivalence relations always “partition” sets into distinct subsets whose elements are all equivalent to one another. You can think of those subsets as the folders in your file system. These are known as equivalence classes and they’re found in virtually all fields of mathematics.

I hope this hasn’t been too dry. If you think these ideas are trivial, note that an order is also a kind of relation; it’s transitive but not symmetric, and so it isn’t an equivalence relation. Order theory is certainly not trivial, and has important applications in many fields including formal logic. But I think these simple ideas are good things to have in your intellectual toolbox whether you’re interested in maths or not; they encode basic logical ideas that we meet every day.