Relations

Suppose that A = {a, b, c}. Then R = {(a,a), (a, b), (a,c)} is a relation on A

• Suppose A = {1, 2, 3, 4}

• R = {(a,b) | a is less than b}: ordered pairs: (1, 2), (1,3), (1,4), (2,3), (2,4), and (3,4)

• Do AxA then find what fits in R

Q: How many relations are in set A?

• For each element in AxA, we have to make one of two choices.

  • Number of relations 2 to the power of cardinality of AxA

Binary Relations on a Set

Ex 1:

A = {1, 2, 3, 4}

R is (a,b) where a=b+1

R= {2,1}, {3,2}, {4,3}

Combining Relations

We can combine two relations R1 and R2 using operations like U, ^, and -

Composition

Definition

• Suppose:

  • R1 is a relation from a set A to a set B

  • R2 is a relation from B to a set C

Ex: Consider the following relation on the set A={1,2,3,4}

• R1 a<b

• R2 a= b-1

With composition for R1oR2:

• Apply R2 first

  • Look at the things that match the number at the end for the first ordered pair

    • ex: (1,2) and (2,3)

      • the answer would be (1,3)

• Its just like composition of functions

if R1 is less than or equal to and R2 is greater than or equal to, then the composition R3=a=b

Powers of relation

• Composing a relation within itself:

  • R squared

Reflexive Relations

• Definition: R is reflexive iff (a,a) exist in R for every element A

  • Every element is related to itself

Example

• A = {1,2,3,4}

• R={(a,b)|a<=b)}

• Is this relation reflexive? Apparently yes

Symmetric Relations

• If you have an ordered pair: then you need to have its mirror image

  • (a,b) then (b,a)

Ex:

• A = 1,2,3,4

• R = {(a,b)|a+b is even}

• Is this relation symmetric

• yes! All the ordered pairs have a mirrored image within R

Antisymmetric Relations

If the pair (a,b) is in there, then the mirror image should NOT be in there.

blah blah blah

It just takes one to mess it up

Transitive Relations

if a is related to b and b is related to c, then a is related to c