abstractmath.org

help with abstract math

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.

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

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

¨
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.

¨ 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.**

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

A relation on a set A is **irreflexive**** on
A** if

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

¨ 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.

**¨ ** 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. **

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. **

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.

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

¨ 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” .

¨ 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.

**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.

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

¨ 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.**

¨
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

¨ 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.

Give an example of a nonempty, symmetric, transitive
relation on the set {

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

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.