abstractmath.org
help with abstract math
Produced by Charles Wells. Home Website TOC Website Index Blog
Back to Relations Head
Posted 30 August 2009
OPERATIONS
ON RELATIONS
Table of contents
Union
and intersection
Since relations
from A to B are subsets of ,
you can form the union or intersection of any
two relations.
Examples
On the set of real numbers:
¨
The union of “ = “ and " <" is (of
course!) “ ” .
¨
The intersection of “ ” and “
” is “=”.
¨ The
union of “<” and “>”
is “not equal to”.
¨ The
intersection of “<” and
“>” is the empty relation.
Rules of inference
¨
For all and
,
if and only if
or
(or both).
¨
For all and
,
if and only if both
and
.
Opposite of a relation
Definition: opposite
The opposite of a relation
from A to
B is a relation called
from B to
A, defined by
. In other words, you get
from
by turning around all the pairs in
.
Examples
¨
On the opposite of " >" is
" <" and the opposite of "
" is "
".
¨ For any set A, the opposite of the equals relation on A is the same equals relation
¨ More generally, the opposite of any symmetric relation is the same relation.
Composition of relations
Definition: Composition of relations
Let be a relation from A to B and
a relation from B to C. The composite
is a relation from A to C defined this
way:
if and only if there is an element
satisfying
and
.
Remark
Computer scientists may write for
Example
Let A = {1 ,2, 3, 4 ,5},
B = {3 ,5, 7, 9},
C = {1 ,2 ,3, 4, 5, 6},
α = {(1, 3), (1, 5), (2, 7), (3, 5), (3, 9), (5, 7)} and
= {(3,1), (3,2), (3,3), (7,4), (9,4), (9,5), (9,6)}.
Then
= {(1,1), (1,2), (1,3), (2,4), (3,4), (3,5), (3,6), (5,4)}.
So
m n if
and only if in the picture there is a sequence of two arrows, the first marked α
and the second marked
,
from m to n.
Associativity
Theorem: If is a relation from A to B,
is a relation from B to C and
is a relation from C to D, then
.
It is worthwhile to draw a picture of an example like the one to the right to understand this claim.