Produced by Charles Wells.  Home    Website TOC    Website Index   Blog

Back to Relations Head

Posted 31 August 2009

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.

¨  The equals relation on any set is antisymmetric.  (Rewrite:  If a = b and b = a, then a = b, which is true by definition of “and” .

Non-examples

¨  The total relation on a set is not antisymmetric if the set has more than one element. 

¨  A nearness relation is not antisymmetric.  For example, if , then  and 3.14 are near each other, but they are not the same.

Warning  

Antisymmetry is not the negation of symmetry. 

¨  The  equals relation is both symmetric and antisymmetric.

¨  So is the relation {(1, 1), (2, 2)} on the set  of real numbers.  Note that this is not the equals relation.  See this exercise.

¨  The relation divides on the set  of integers is neither symmetric nor antisymmetric.   3 divides 6 but 6 does not divide 3, so it is not symmetric.  On the other hand,  3 divides 3 and 3 divides 3, but 3 and 3 are not equal, so it is not antisymmetric.

Transitive relations

Definition: transitive

A binary relation  on a set A is transitive  if for all elements a, b, and c of A, if  and , then .

Examples

¨  The empty relation is vacuously transitive on any set.

¨  The equals relation is transitive on any set.  (If a = b and b = c then a = c.  This is equivalent to the property given by “two things equal to the same thing are equal to each other.”)

¨  All these relations are transitive on :  “ < “, “  ”, “>”, “  ”.   In general, anything you could call an ordering is transitive.

Non-examples

¨  The sister relation S on the set of all women is not transitive.  Agatha may be Bertha's sister, whence Bertha is Agatha's sister, but Agatha is not her own sister. This illustrates the general principle that when a definition uses different letters to denote things, they don't have to denote different things (see two). In the definition of transitivity, a, b and c may be but don't have to be different.

¨  Nearness relations are not transitive.  For example, if , then 3.10 and 3.16 are near each other and  3.16 and 3.22 are near each other, but 3.10 and 3.22 are not near each other.  It is well known, for example, that color discrimination is not transitive.  (You can have three color samples A, B and C, with A and B appearing identical and B and C appearing identical, but with A and C detectably different.)  

¨  The  element of relation need not be transitive.  For example,  and , but .

¨  Define a relation  on the set  of real numbers by:  .  Then  is not transitive.

Worked Exercise

Give an example of a nonempty, symmetric, transitive relation on the set {1,2} that is not reflexive.

Answer:  {{1,1}} on the set {1,2} for example.  See  partial equivalence relation.

Properties of relations in math

The two most important classes of relations in math are order relations (antisymmetric and transitive) and equivalence relations (reflexive, symmetric and transitive).   A section of abstractmath.org is devoted to each type.  Other kinds of relations do occur in math but they are not as pervasive as order relations and equivalence relations.   Some examples of other kinds of relations are nearness, preorders, and partial equivalence relations.