Produced by Charles Wells.  Home    Website TOC     Website Index   Blog

Back to Relations Head

Posted 30 August 2009

RELATIONS: BASIC IDEAS

You are familiar with relations such as “ = “ and “ < “ that may hold between numbers.  The mathematical concept of relation includes these but is much more general and abstract than you might expect.

The moderately devious definition I give below captures this generality, but it is hard to get your head around the definition when you first see it.  I suggest reading it and then looking at the examples to see how it works.

Note:  This site discusses only relations between two objects (binary relations). 

Terminology

Definition: A relation from a set A to a set B is a subset of .   (This is the strict definition.  See fine points.)

¨  Any subset of  is a relation from A to B.  

¨  A and B can be different sets.

Examples

The relation “<”

The relation “<” on the real numbers is the subset of  consisting of all pairs (r, s) of real numbers for which r < s.  This means that the relation “<” is a mathematical object. 

In setbuilder notation, the relation “<” is the subset .   If this were a definition of “<” it would be circular.  In fact it is an illustration of the definition of relation and assumes you already know what “<” means.  One possible non-circular definition of “<” is that it is  

An arbitrary relation

The arbitrary relation  is a subset of , and so it is a relation from the set  to the set .  I made it up to illustrate that relations can be arbitrary.

Relations on a single set

If  is a relation from a set A to A, in other words , then we say  is  a relation on A.   Most of the relations studied here in abstractmath.org are relations on a single set. 

How we write relations

If  (so  is a relation from A to B), and , then we write “  ”, using infix notation.  

“  ” is a statement that means that a is in the relationship  to b. 

Examples

If we use  for the abritrary relation above, then  and , but it is not true that .  In fact no element of A is related by  to 8.   (  is the Greek letter gamma.  Don’t call it “r” or you will be sneered at by rude math majors.)

Remarks

¨  The definition of relation may seem weird at first.  It says in effect “a relation  is the set of pairs (a, b) for which the statement “  ” is true”.   It has the advantage that you don’t have to describe in words what makes the relationship hold, you simply have to say what pairs it is true of.  This allows relations to be arbitrary.   This is by far the most common way to define relations in math, but there are other ways.

¨  “r < s” is a symbolic assertion  but  “r + s” is only an expression (symbolic term)  that denotes another number.   It makes sense to ask whether “r < s” is true or false but it does not make sense to ask whether “r + s”  is true or false.  Note that the symbol “<” by itself is a symbolic term.

¨   “  ” is the Greek letter alpha.  In abstractmath.org I often use Greek letters for relations if there is not already a symbol such as “<” or “  ” for the relation.

Two fine points

Strict and less strict

Here are three definitions of a relation.  Note that they all have the same set of ordered pairs.

¨   from the set {1, 2} to the set {5,6,7,8}. 

¨   from {1,2,3} to {5,6,7}.

¨   on the set of natural numbers .

Are these the same relation or different relations?  Mathematical usage differs on this point. 

The less strict definition of relation:  A relation is a set of ordered pairs.

The stricter definition of relation from A to B:  A relation from A to B is a subset of .

¨  According to the less strict definition,  are all the same relation. 

¨  According to the stricter definition they are all different.

This distinction is closely analogous to the distinction between the two definitions of function. 

Remarkably often, it makes no difference which definition is used in a particular context and the author of a text might not tell you what stance she is taking on this point. 

In some cases you must assume they are different.  This is true of the definition of reflexive, for example.

Relations given by rule

Now look at the equals relations on  two different sets:  

¨  On the set  A = {1, 2}   the equals relation is  {(1, 1), (2, 2)}.

¨  On B = {2, 3, 4} it is {(2, 2), (3, 3), (4, 4)}.

The definition of the equals relation is the same in both cases, in fact on any set:  a = b if and only if a and b are the same mathematical object.   But the two relations given above are nevertheless different relations, by either the strict or the less strict definition, because they are different sets of ordered pairs. 

Thus “equals” is the name of many different relations, depending on the set it is defined on.  Another example of this phenomenon occurs with the “is the sister of” relation.  More about this under overloaded notation.

Rules of inference for relations

Method:  Let A and B be sets and let .  

¨  If you know , then you know .

¨  If you know , then you know .

Worked Exercises

Write all ordered pairs in the relation   on the set A.

1) A = {1,2,3},  is "  ".

2) A = {1,2,3,4,5},  is "divides".

3) A = {1,2,3},  if and only if n = 3.

4)  A = {1,2,3},  if and only if m < n + 1.

5)  A = {1,2,3},  if and only if m > n + 1.

Answers:

1) (1,2), (1,3), (2,3), (2,1), (3,1), (3,2)

2) (1,1), (1,2), (1,3), (1,4), (1,5), (2,4)

3) (1,3), (2,3), (3,3)

4) (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)

5) (3,1)

Representing relations

Relations between small finite sets can be represented graphically, with arrows from a to b if a is related to b, and also by a table.  Here are a graph and a table representing the arbitrary relation given above.

In some cases, a relation on the real numbers can be displayed by shading the area containing the pairs for which the relation holds.  The graph below shows part of the relation “<” on the reals.  

This can’t be done for all relations on the reals.  Try picturing the rational difference relation, for example.

Metaphors and Images for relations

If you are new to abstract math you perhaps think of a relation as some sort of natural connection between certain pairs of objects.   The kinds of examples you think of are like “<” on numbers or “is the sister of” on the set of all women. 

The definition of relation as a set of ordered pairs says nothing about this, for the good reason that it is really really hard to say what “natural connection” means.   This definition is an abstraction of the intuitive idea of relationship.  A relationship is something that holds between two objects, so you define relation to be any set of ordered pairs of objects. 

This definition also suits mathematicians, who generally want all their concepts to allow complete arbitrariness within the bounds of the definition.   

So you get this weird thing that “  is a subset of  ”, but you don’t normally write “  ”, you write “  ”.  Indeed most of the time your mental image of a relation does not include thinking about it as a set (of ordered pairs or leprechauns or anything) at all.  “Is the sister of” is a SET??

(Functions can cause this difficulty too, but the ordered pairs part is not so hard to deal with because you are used to thinking of the graphs of functions.)

So all I can say is