Unknown
An important idea in mathematics is that of a set of objects. From the theory of sets, we can establish the
notions of a binary relation and a function.
1. Binary Relations
Intuitively, a binary relation is some rule on two objects. For example, “10 < 20”, “Collingwo od is better than Carlton”, and “Pacino and de Niro have been in the same movie”. On the integers, things like “less than”,
“is a factor of”, or “not equal to” are examples of binary relations. We abstract this notion as follows:
Definition 1.1. A binary relation from a set X to a set Y is a subset of the set of ordered pairs
{(x, y ) : x X, y Y }.
By ordered pair we mean that (x, y) is not necessarily equal to (y, x), that is, it matters that x is in the first
coordinate and y is in the second coordinate. The set of all ordered pairs is known as the Cartesian
product
1
of X and Y . We denote this set by X × Y := {(x, y ) : x X, y Y }.
Example 1.2.
• If X = Y , we call a binary relation from X to Y also a binary relation on X.
• Equality is a binary relation on any set. If X is a set, then R
on X is precisely the subset of X × X
=
given by {(x, x) : x X}. So two elements x, y X are equal if (x, y ) R
. This lo oks a bit strange
=
doesn’t it? You might be asking, don’t you mean x = y? See below for the answer.
• “Less than” is a binary relation on the real numbers. So (1, 2) R
and (p, 4) R
. Again, this
looks very strange if you are familiar with infix notation.
• The “blo od type” binary relation BT is defined on the sets of human beings and blo od types. So if
Fred has A+ blood, then (F red, A+) BT .
• The “grand-father” binary relation GF is defined on the set of human beings. So if Bill is Fred’s
grandfather, then (Fred, B ill) GF .
Instead of writing (x, y) R all the time, we will often write x R y to mean (x, y) R. So in the
first example above, (x, y ) R
is the same as x = y .
=
Exercises 1.3. Which of the following are binary relations?
(1) Football team x is better than fo otball team y.
(2) Politicians are stupid.
(3) Town x is a suburb of Perth.
(4) The integer x is a divisor of the integer y.
(5) Person x is wearing the same hat as person y.
The Cartesian Product was named after Ren`
e Descartes (1596-1650), the famous French
philosopher and mathematician.
8 2 . R EL AT I ON S, FU N CT I ON S, A N D P ER MU TAT I ON S
2. Functions
In high school, the first functions we saw were something like f (x) = x
or f (x) = 3x + 1, but yet a function
was never defined. What is a function? One can think of a function as a machine which takes an input and
spits out an output. Another way to think of a function, is that it is a binary relation on the input and output
of this machine. So for example, if we take the above example f (x) = x
on the real numbers, we say that 2 and
4 are related since f (2) = 4. So a function is a relation, but is it special in anyway? Note that f (2) is always
equal to 4, but the same can’t be said of <, where 2 < 4 but 2 < 5 as well! We have the following abstract
definition of a function:
Definition 2.1. A function f from X to Y is a binary relation from X to Y where for each (a, b) and
(a, c) in f , if (a, b) = (a, c) then b = c. In other words, for anything in the first coordinate of an ordered pair of
f , there is a unique entry in the second coordinate.
Example 2.2.
(1) The squaring function f (x) = x
on the real numbers, can be thought of as the set of pairs (x,
(like (2, 4), (5, 25), (-1, 1), (
6, 6), etc).
(2) Equality is a function. In fact, we usually call it the identity function. So if X is a set, the function
defined by f (x) = x (for all x X) is actually the equality relation!
(3) Notice that R
is not a function since (2, 4) R
and (2, 5) R
(4) The “grandfather” relation is also not a function since it is possible to have two di erent grandfathers!
(5) The “bloo d-type” relation is a function, since everyone has a unique blood type.
You Might Also Like
Posted in: Abstract Algebra
