Relations

Definition 1.12

Given sets A and B, any subset R of A×B is a relation between A and B. If (a,b)R this is often denoted by aRb

If A=B, R is said to be a relation on A

Definition 1.13

The domain of a relation R between A and B is the set {a:aA and there exists  bB so that  aRb}

The range of a relation R between A and B is the set {b:bB and there exists  aA so that  aRb}

Definition 1.14

Let R be a relation between A and B. The inverse of the relation R dentoed by R -1 is a relation between B and A, defined by
R -1 = { ( b , a ) : ( a , b ) R }

Definition 1.15

Let R be a relation between A and B, and let S be a relation between B and C.

The composition of R and S, denoted by SR, is a relation between A and C defined by ( a , b ) SR  if there exists  b B such that  ( a , b ) R  and  ( b , c ) S

Definition 1.16

A relation R on A is reflexive if aRa for all aA.

A relation R on A is symmetric if aRbbRa for all a,bA.

A relation R on A is antisymmetric if aRb and bRaimpliesa=b.

A relation is transitive if whenever aRb and bRc, then aRc