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
Since relations
from A to B are subsets of ,
you can form the union or intersection of any
two relations.
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.
¨
For all and
,
if and only if
or
(or both).
¨
For all and
,
if and only if both
and
.
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
.
¨
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.
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
.
Computer scientists may write for
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.
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.