Produced by Charles Wells.  Home    Website TOC     Website Index   Back to Relations Head 

Last edited 5/26/2008 2:49:00 PM

PROPERTIES OF RELATIONS

This section concerns certain properties relations may have.  In each case it applies only to a binary relation on a single set.  The ones given here are fundamental to most parts of abstract math.  Wikipedia describes some other properties.

Reflexive relations

Definition: reflexive

A binary relation  on a set A is reflexive on A if  for every element of A.

Examples

¨  The relation “  ” is reflexive on .  That’s because the statement “  ” is true for every real number r. 

¨  The equals relation is reflexive on any set: the statement “x = x” is true for every mathematical object x. 

¨  The relation “  ” on the powerset of any set is reflexive.

¨  The relation  on the set of integers defined by  if and only if  is reflexive.

¨  A nearness relation on  is reflexive. 

Non-examples

¨  The relation " <" is not reflexive on .   

¨  The relation "is the sister of" on the set W of all women is not reflexive, since no one is the sister of herself.   

¨  The relation  on  is reflexive.  The relation  (same set of ordered pairs) on  is not reflexive.  This example shows that for reflexivity, the stricter definition of relation must be used.

Something to think about

A relation  on a set A is reflexive if and only if the equals relation on A is a subset of .

Irreflexive relations

Definition: irreflexive

A relation  on a set A is irreflexive on A if  is false for every element a of A.   Note that this is not the negation of “reflexive”.  The relations “<” on  and “is the sister of” on W  just mentioned are in fact irreflexive.  But a relation can be neither reflexive nor irreflexive:  The relation  {(1, 1), (2, 2)} is not reflexive on the set of all integers, because 3 (among others!) is not related to itself.  But it is not irreflexive either, since 1 is related to itself.

Warning  It is wrong to say that the relation

 just given is “reflexive at  1 but not at  3”.  Reflexivity and irreflexivity are properties of the relation and the set it is defined on, not of particular elements of the set. This comment also applies to the other properties of relations discussed in this section.

Symmetric relations

Definition: symmetric

A binary relation  on a set A is symmetric if  implies  for all elements a and b of A.

Examples

¨  The  empty relation is symmetric, because the statement “if  then  ” is vacuously true.

¨  The equals relation is symmetric.   (Rewrite:  Must show that if a = b, then b = a.  But you have known that for years.)

¨  Any nearness relation is symmetric.

Non-examples

¨   The relation {(1, 2), (2, 1), (1,3)} is not symmetric.  It is wrong to say it is “sometimes symmetric” or “is symmetric as far as 1 and 2 are concerned.”  Being symmetric is a property of the whole relation.

¨  The sister relation is symmetric on the set of all women.

¨  The sister relation on the set of all people is not symmetric.

Warning   It is important to understand the precise meaning of the definition of symmetric. It is given in the form of an conditional assertion:   is symmetric if for all pairs (a, b), if  then .  This does not assert that   for any particular elements a and b.

Remark

We have defined relation as an abstraction (set of ordered pairs) of a relationship in the usual sense, and then defined a symmetric relation in terms of the abstract definition of relation (when (a, b) is in the relation then so is (b, a).)  We could have given a direct abstract definition of symmetric relation on a set A by saying it is a set of one- and two-element subsets of A.  For example, the symmetric relation {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)} could be modeled as {{1},{1, 2}, {2, 3}}. This is an example of a concept having two different-looking definitions. 

Worked Exercise

Show that if a relation  on a set A is not symmetric, then A has at least two distinct elements.

Proof:  If A is empty, then   is the empty relation, which is vacuously symmetric.

If A has exactly one element, then either  is empty in which case it is vacuously symmetric, or , where a is the only element in A, but then  is symmetric.

So A must have at least two elements.

Antisymmetric relations

Definition:antisymmetric

A binary relation  on a set A is antisymmetric if for all elements a, bA, if  and  , then a = b

Examples

¨  The empty relation is vacuously antisymmetric.

¨  The “<” relation is vacuously antisymmetric.  (Rewrite:  “If a < b and b < a, then a = b” is vacuously true because the statement “a < b and b < a” is always false.)

¨  The “  ” relation on the set  of real numbers is antisymmetric.  (Rewrite:  “If , then a = b”, a familiar fact about numbers.  Antisymmetry is typical of order relations in general.