Relations on sets
A relation can be looked on in two ways, either as a subset of the cartesian product between two sets, or as some property shared by a member of one set with a member of the other.
We are accustomed to thinking of x=y as a statement about the relative size of two numbers x and y, but we can also think of it as a subset of R x R (the reals x the reals).
If R is a relation, (not the set of reals), we can write either (x,y)∈R or xRy, the latter is often more convenient.
The three important qualities of a relation are (remember RST) for a relation R on a set with elements a, b, c.
| property | to prove | example |
| reflexive | aRa | = |
| symmetric | aRb ⇒ bRa | = |
| transitive | aRb and bRc ⇒ aRc | = > |
To prove something about a relation, translate it in two steps:
- firstly into the "to prove" column above
- Secondly into English using the definition of the relation
For example, if R is the relation between people meaning "has the same nationality", is it transitive?
- First step: for transitivity we have to prove that aRb and bRc ⇒ aRc
- Second step: translating into English, we have to prove that if a has the same nationality as b, and b has the same nationality as c, then a has the same nationality as c, which is pretty obvious if you state it in English.