Binary relations

Binary relations

1. Binary Relations
Denition:Abinary relationbetween two setsXandYis a subset ofXY|i.e., is a set
of ordered pairs (x; y)2XY.
For a relationRXYwe often writexRyinstead of (x; y)2R. We writeR
c
for the complement
ofR|i.e.,xR
c
yif and only if (x; y)=2R. IfXandYare the same set, so that the relationRis
a subset ofXX, we say thatRis a relation onX.
Example 1:
Xis a set of students, sayX=fAnn; Bev; Carl; Dougg.
Yis a set of courses, sayY=f501A;501B;520g:
ThenXYhas 12 elements. An example of a relationRXYis the set of pairs (x; y) for
which \x is enrolled in y." Another example is the relationAdened by \xAyifxreceived anA
grade iny".
Example 2:
XandYare arbitrary sets andf:X!Yis a function fromXtoY.
(a) DeneGas follows:G:=f(x; y)2XYjy=f(x)g. Clearly,Gis simply the graph of the
functionf. But we can just as well regardGas a relation between members ofXandY, where
xGymeans thaty=f(x).
(b) Denexx
0
to meanf(x) =f(x
0
). Note thatxxfor everyx2X; that ifxx
0
then
x
0
x; and that ifxx
0
andx
0
x
00
, thenxx
00
. Any relation with these three properties is
called anequivalence relation. Equivalence relations are important; we'll see a lot more of them
shortly.
Example 3:
LetXbe an arbitrary set and letu:X!Rbe a real-valued function onX. IfXis interpreted as
a set ofalternativesanduis interpreted as autility functionthat represents someone's preference
over the alternatives, then we interpretu(x
0
)> u(x) to mean the person strictly prefersx
0
tox
and we dene the corresponding relationPonXbyxPy,u(x
0
)> u(x). Similarly, we interpret
u(x
0
) =u(x) to mean the person is indierent betweenx
0
andx, and we dene the relationIby
xIy,u(x
0
) =u(x); and we interpretu(x
0
)=u(x) to mean the person weakly prefersx
0
tox
(she either prefersx
0
or is indierent), and we dene the relationRbyxRy,u(x
0
)=u(x). It's
common to usex
0
xinstead ofx
0
Px;x
0
xinstead ofx
0
Ix; andx
0
%xinstead ofx
0
Rx.

2. The setXin Example 3 could be a set of consumption bundles inR
n
, as in demand theory, but
that's not necessary;Xcould be any set of alternatives over which someone has preferences.
Note that the indierence relationI, or, in Example 3 is the same relation dened in Example
2(b). It therefore has the three properties described there and is an equivalence relation. The
strict preference relationP, or, has the third property but not the other two; and the weak
preference relationR, or%, has the rst and third property but not the second. These properties,
and several others, are important enough that we give them names and dene them formally:
Denitions:A binary relation on a setXis
(a)reexiveif8x2X:xRx;
(b)symmetricif8x; x
0
2X:x
0
Rx)xRx
0
;
(c)transitiveif8x; x
0
; x
00
2X: [x
00
Rx
0
&x
0
Rx])x
00
Rx;
(d)completeif8x; x
0
2X:xRx
0
orx
0
Rx;
(e)antisymmetricif8x; x
0
2X: [x
0
Rx&xRx
0
])x=x
0
(f)asymmetricif8x; x
0
2X: [x
0
Rx)xR
c
x
0
]
(g)irreexiveif8x2X:xR
c
x.
Example 4:
Xis a set of people. Each of the following is a binary relation onX:
(a)xNy:xlives next door toy.Nwould typically be symmetric, irreexive, and not transitive.
(b)xBy:xlives on the same block asy.Bwould typically be reexive, symmetric, and transitive.
(c)xSy:xis a sister ofy.Swould typically be irreexive, not symmetric (unless all elements of
Xare female), and not transitive.
(d)xAy:xis an ancestor ofy.Awould typically be irreexive, asymmetric, and transitive | a
strict preorder, as we'll dene shortly.
(e)xDy:xis a daughter ofy.Dwould be irreexive, asymmetric, and not transitive.
Example 3 continued:
Note that the relation%is complete and the relationsandare typically not complete. The
relations%andare typically not antisymmetric;is vacuously antisymmetric. (\Vacuous"
because the antecedent in the denition,x
0
x&xx
0
, can never be satised.) Can you
construct special cases of Example 3 in whichorare complete? How about special cases in
which%orare antisymmetric? (Example 5 may be helpful here.)
2

3. Example 5:
The usual ordering of the real numbers inR, in which=is the weak ordering and>is the strict
ordering, is analogous to the relations dened in Example 3, but generally not quite the same. For
example,=isantisymmetric, and so is the equality relation, =, unlike%and.
Examples 3 and 5 display the dierence between anorderingof a set and what we call apre-
orderingof a set: if%is merely a preorder but not an order, then two or moredistinctelements
xandx
0
can satisfy bothx
0
%xandx%x
0
(for example, two consumption bundlesxandx
0
between which someone is indierent). But if%is an order (often called atotal order), that can't
happen |x
0
%xandx%x
0
require thatxandx
0
be the same element.
Denition:A relationRon a setXis
(a) apreorderif it is transitive and either reexive (aweak preorder) or irreexive (astrict
preorder);
(b) anorderif it is complete, transitive, and antisymmetric.
Denition:If%is a preorder onX, then
(a) the associated strict preorder, denoted, is dened byx
0
x,[x
0
%x&x6%x
0
] ;
(b) the associated equivalence relationis dened byx
0
x,[x
0
%x&x%x
0
] .
Remark:The terminology in the above denition is appropriate:is indeed a strict preorder
andis an equivalence relation.
Exercise:Provide a proof of this remark.
In economics and decision theory we're often interested in elements that arebest, or amaximum,
inXaccording to a preorder%|i.e., an element that's at least as good (or at least as large) as
every other element inX. If a preorder is not complete, there may not be a maximum element,
so we also dene the weaker notion of amaximalelement. (Donotuse Denition 3.7 in de la
Fuente.)
Denition:If%is a preorder onX, then
(a) xis amaximumelement for%if8x2X: x%x;
(b) xis amaximalelement for%if6 9x2X:xx.
Similarly, xis aminimumorminimalelement if8x2X:x%xor6 9x2X: xx.
3

4. Denition:IfRis a binary relation onXand if x2X,
(a) theR-upper-contour setof xis the setRx=fx2XjxRxg, and
(b) theR-lower-contour setof xis the set xR=fx2XjxRxg.
According to this denition, if%is a preorder onXwe would use%xandxfor the weak
and strict upper-contour sets of x. But I nd it's generally better to use the notationRxand
Pxfor the weak and strict%-upper-contour sets, and to use xRand xPfor the weak and strict
lower-contour sets.
A preorder is a natural, intuitively appealing way to represent someone's decision behavior: when
faced with a setXof available alternatives, we assume that his choice will be an elementbxto
which no other elementxis strictly preferred |i.e., it will be a maximal element ofXwith
respect to the decision-maker's preference%. But relations are cumbersome and awkward to work
with; functions are much more tractable analytically. So if we have a given preorder%on a set
X, we would like to be able to transform it into a utility functionuonXin such a way thatu
and%are related as in Example 3.
Denition:LetRbe a binary relation on a setX. A real-valued functionu:X!Ris autility
functionforR, or arepresentationofR, if
8x; x
0
2X:u(x
0
)=u(x),x
0
Rx:
Ris said to berepresentableif there is a utility function forR.
In Example 3 we went in the opposite direction to the one indicated in the above denition: we
started with the functionuas the representation of someone's preference and dened the associated
%. But it's preferences we think are fundamental, not utility functions, so we would like to know
when we can nd a utility function to represent a given preorder. We'll return to this idea later
and provide conditions on a relationRthat are sucient to ensure that it can be represented by
a utility function. You'll see this idea in Economics 501A as well.
4

5. Equivalence Relations and Partitions
In Examples 2 and 3 we encountered the idea of an equivalence relation, although we didn't single
it out with its own formal denition. Equivalence relations are one of the most ubiquitous and
fundamental ideas in mathematics, and we'll encounter them over and over again in this course.
The notationthat we used in Examples 2 and 3 is the standard notation for an equivalence
relation.
Denition:Anequivalence relationon a setXis a binary relation that is reexive, symmetric,
and transitive. Equivalence relations are typically denoted by the symbol. The setfx2Xj
xxgof all members ofXthat are equivalent to a given member xis called theequivalence
classof xand is typically written [x]. Ifxx
0
, we say that \xis equivalent tox
0
."
Example 5 continued:
Xis a set of people. The relation \is the same age as" is an equivalence relation. The relation
\is a brother of" is not. The relation \lives in the same house as" is an equivalence relation. The
relation \lives next door to" is not.
Example 3 continued:
The equivalence class [x] of an alternative x2Xis the set of all the alternatives that are \indierent
to x" |i.e., all the alternativesxfor which the decision-maker is indierent betweenxand x. If
the setXisR
2
+and the utility functionuis ice" (we'll leave that term undened for now), then
[x] is the indierence curve containing x.
Remark:If%is a weak preorder, then the relationdened byx
0
x,[x
0
%x&x%x
0
] is
an equivalence relation, called the equivalence relation associated with%.
Exercise:Provide a proof that the relationassociated with a preorder%is an equivalence
relation.
Notice that in each of the above examples the equivalence relation \partitions" the setXinto the
relation's equivalence classes. Here's a formal denition of the idea of a partition:
Denition:Apartitionof a setXis a collectionPof subsets ofXthat satises the two
conditions
(1)A; B2 P )(A=BorA\B=;) ;
(2)[
A2P
A=X.
5

6. An informal statement of the above denition is that a partition ofXis a collection of subsets
that aremutually exclusiveandexhaustive. Every member ofXis in one and only one member of
P:
Theorem:Ifis an equivalence relation on a setX, then the collection of its equivalence classes
is a partition ofX. Conversely, ifPis a partition ofX, then the relationdened by
xx
0
, 9S2 P:x; x
0
2S
is an equivalence relation, and its equivalence classes are the elements of the partition.
Exercise:Provide a proof.
Let's apply the notions of equivalence, equivalence classes, and partitions to preferences and their
utility function representations. First note that if a given preference has a utility function repre-
sentation, then it hasmanyutility function representations, as the following example indicates.
Example 6:
Letu:R
2
+!Rbe dened byu(x) =x1x2, a Cobb-Douglas utility function, and let%be the
preference (i.e., preorder) onR
2
+dened as in Example 3. Obviouslyuis a representation of%.
Now dene a new utility functioneuonR
2
+byeu(x) = log[u(x) + 1] |i.e.,eu(x) = log[x1x2+ 1].
It's easy to see thateuis also a utility representation of%.
Denition:Letu:X!Rbe a real-valued function dened on the setX. The function
eu:X!Ris anorder-preserving transformationofuif there is a strictly increasing real
functionf:u(X)!Rsuch thateu=fu|i.e., such that8x2X:eu(x) =f(u(x)):
Remark:Two real-valued functionsuandeuon a setXare order-preserving transformations of
one another if and only if they are both representations of the same relationRonX.
Example 7:
LetXbe a set and letUbe the set of all real-valued functions onX. Dene the relationonU
as follows:ueuifeuis an order-preserving transformation ofu. Thenis an equivalence relation
onU. An equivalence class [u] consists of all the utility functions onXthat represent the same
preference asu. Thus, the equivalence relationpartitions the setUof all real-valued functions
onXin such a way that each equivalence class in the partition corresponds to adistinctpreference
%onR
2
+| obviously, to a distinctrepresentablepreference | and each distinct representable
preference corresponds to a distinct equivalence class in the partition.
Exercise:Prove thatis an equivalence relation.
6

7. In Example 7 the set of equivalence classes plays an important role: it is the same, in every
essential respect, as the set of representable preferences | every distinct preference corresponds
to a distinct equivalence class. This is a common occurrence, so we assign a name and a notation
to the set of equivalence classes generated by an equivalence relation:
Denition:Letbe an equivalence relation on a setX. ThequotientofXby, or the
quotient setgenerated by, denotedX=, is the set of all-equivalence classes |i.e.,X=
is the setf[x]jx2Xg.
Example 6 continued:
In Example 6,is the indierence relation derived from the utility functionu, and the quotient
setR
2
+=is the set of indierence curves for the functionuand also for any order-preserving
transformation ofu.
Suppose someone's preference overR
2
+is described by a complete preorder%. Can we represent
%by a utility function? In other words, can we be sure that%is representable? Example 7
suggests that perhaps the answer is yes, that every complete preorder is representable. It turns
out that this is not so. The following theorem provides conditions that guarantee that a preorder
isrepresentable. The theorem is followed by an example of a preference that is not representable.
Representation Theorem:If a relationRon the setR
l
+is complete, transitive, and continuous,
then it is representable. Moreover, it is representable by acontinuousutility function. (We'll
dene continuity for relations and functions shortly.)
Proof:Debreu, on page 56, Proposition (1), gives a proof. Jehle & Reny, on page 120, Theorem
3.1, give a proof for relations that are complete, transitive, continuous, and strictly increasing.
Do we really need all three assumptions, or \axioms," about a preference in order to know that it is
representable by a utility function? For example, it seems plausible that if we don't insist that the
utility function be continuous, we may be able to at least ensure that a (possibly discontinuous)
representation ofRexists if we at least know thatRis complete and transitive. Or perhaps ifR
satises one or more additional assumptions as well, but assumptions that are not as strong as
continuity, thenthatwill be enough to ensure thatRis representable. What we want in this kind
of situation is a collection ofcounterexamples: for each assumption in our theorem, we want an
example that demonstrates that if all the remaining assumptions are satised, but that one isn't,
thenRneed not be representable. One such counterexample is given below: a relation%that is
complete and transitive, but is not continuous, and for which no utility function exists.
7

8. Exercise:Provide counterexamples to show that neither completeness nor transitivity can be
dispensed with in the theorem above.
Example 8 (Lexicographic Preference):
This is an example of a preference relation | a complete preorder | which is not representable.
Of course, it's not acontinuousrelation; otherwise we would have a counterexample to the truth
of the theorem. Let%onR
2
+be dened by
(x
0
1; x
0
2)%(x1; x2),[x
0
1> x1or (x
0
1=x1&x
0
2=x2)]:
See Figure 1. How would we show that%is not representable? We have to show thatnoutility
function could represent%| which is not so easy, as it turns out. The proof relies on a fairly
deep mathematical result: that the set of all real numbers (or any non-degenerate real interval)
is an \uncountable" set. If we accept that mathematical fact, then the proof is not so bad: we
assume that%has a representationu(), and then we use that to establish thatR+is countable,
which we know to be false. Therefore, our assumption that%has a representationu() cannot be
correct. This is called anindirect proof, or aproof by contradiction.
Thus, we assume thatu() is a utility function for%. For eachx2R+, dene the two real numbers
a(x) =u(x;1) andb(x) =u(x;2) (see Figure 2). Clearly,a(x)< b(x) for eachx, and therefore, for
eachx, there is a rational numberr(x) that lies betweena(x) andb(x). Moreover, ifx <ex, then
r(x)< b(x) andb(x)< a(ex) anda(ex)< r(ex); we therefore haver(x)< r(ex) wheneverx <ex| in
particular,x6=ex)r(x)6=r(ex), so thatr() is aone-to-onemapping fromR+to a subset of the
setQof rational numbers. Since any subset ofQis countable, this implies thatR+is countable,
which we know is false.
Note that an equivalent denition of%is the following:
(x
0
1; x
0
2)(x1; x2),[x
0
1> x1or (x
0
1=x1&x
0
2> x2)];
together with
(x
0
1; x
0
2)%(x1; x2),(x1; x2)6(x
0
1; x
0
2):
8

9. Figure 1:
Figure 2:
9