* Definition.* A * binary
relation* on a set S is a subset of the Cartesian product .

This definition is so abstract that you may find it difficult to see how this is connected to the ordinary idea of things being "related". Here's the idea.

A *relationship* between two objects is something like

"x is the father of y", or

"x is greater than y", or

"x and y have the same color", or

" .

Look at "x is the father of y". Your experience in the real
world tells you what this means --- how you would *verify*
that a given person is the father of another person. But another way
to *define* the "father" relationship would be to
make a list of *all* father-child pairs. For example, if Bonzo
has a son named Wickersham and a daughter named Gordinier, then the
pairs

would be on the "father" list.

You can see that these are *ordered pairs* --- elements of the
Cartesian product

And a little thought shows that *any* binary (two-element)
relationship can be defined in this way. That's why the formal
definition I gave above makes sense.

* Example.* Suppose . The
relation on S is the set

For example, is in the set, because .

Sometimes it's convenient to draw the * graph* of
a relation. Here's the graph of on S:

As usual, I'm using the horizontal axis for the first component and the vertical axis for the second component.

* Example.* The relation on consists of all points which satisfy the equation. For example, the point
is in the relation.

The graph of the relation looks something like this

* Example.* Consider the relation on the set
whose graph is shown below.

The relation is the set of pairs

It's common in math to use * infix notation* for
relations. This means that instead of writing an ordered pair , you put a * relation symbol*
between x and y --- for example,

You can use any symbol you want, though it's best to avoid symbols like " " or " " which have special meanings --- unless that special meaning is what you want. The "R" isn't very fancy, but it's often used; with this notation, the relation above would be

* Definition.* A relation
on a set S is an * equivalence relation* if:

- (Reflexivity) for all .
- (Symmetry) For all , if , then .
- (Transitivity) For all , if and , then .

An equivalence relation is meant to capture the idea of things
"being the same" for the purposes of a given discussion.
Here's a real-world example. Suppose you plan to drive to the movies.
With that intention alone in mind, there are many things about the
car you drive that aren't important --- what color it is, how many
miles it's been driven, whether the windshield is tinted, and so on.
You care only about the car being suitable for transporting you to
the movies. So any two cars --- whatever their color, mileage, or
windshield tint, for instance --- {\it are the same for your
purposes} if either will get you to the movies. The equivalence
relation on the set of cars is that two cars are equivalent if both
will get you to the movies or both will *not* get you to the
movies.

* Example.* Equality of integers, rational
numbers, real numbers, or complex numbers is an equivalence
relation.

* Example.* The less-than relation on
the set of real numbers is not an equivalence relation.

For no real number x is it true that , so reflexivity never holds.

If x and y are real numbers and , it is false that . For example, is true, but is false.

It *is* true that if and , then . Thus, is transitive.

Suppose instead I consider less-than-or-equal-to, the relation on .

Reflexivity now holds, since for any it *is*
true that . Transitivity holds just as before.

However, symmetry still doesn't hold: , but . Thus, is not an equivalence relation.

* Example.* (a) Is the relation whose graph is
drawn below an equivalence relation?

The relation is not an equivalence relation. is not in the relation, so the relation is not reflexive.

(b) Is the relation whose graph is drawn below an equivalence relation?

is in the relation, but is not. Therefore, the relation is not symmetric, so it's not an equivalence relation.

(c) Is the relation whose graph is drawn below an equivalence relation?

This relation is reflexive and symmetric. However, and are in the relation, but is not. The relation is not transitive, and therefore it's not an equivalence relation.

* Example.* (* Modular
arithmetic*) Let n be a positive integer. Integers x and y are
* congruent mod n* if is divisible by n.
Notation: .

Congruence mod n is an equivalence relation on . Another way to express congruence mod n is: x and y
are * congruent mod n* if x and y leave the same
remainder on division by n. But the first definition is easier to
use.

To make things concrete, I'll do this with , but any positive n will do.

Let . , which is divisible by 3. Therefore, , and congruence mod 3 is reflexive.

Let . Suppose . This means 3 divides , so for some integer k. Then , which means 3 divides . Hence, , and congruence mod 3 is symmetric.

Let . Suppose and . This means that 3 divides and , so

Add the two equations:

This means 3 divides , so . Thus, congruence mod 3 is transitive, and hence, it's an equivalence relation.

Copyright 2008 by Bruce Ikenaga