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

Union and intersection

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