Relations

What Is a Relation?

A relation R from set A to set B is a subset of the Cartesian product A × B. If (a, b) ∈ R, we write aRb and say "a is related to b".

Cartesian Product: A × B = {(a, b) | a ∈ A and b ∈ B}
If |A| = m and |B| = n, then |A × B| = m × n

Example: A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}

Representing Relations

1. Set of ordered pairs: R = {(1,2), (2,3), (3,4)}
2. Matrix:  M[i][j] = 1 if iRj, 0 otherwise
3. Directed Graph (Digraph): vertices = elements, edges = pairs

Properties of Relations on a Set

Reflexive:    ∀a ∈ A: aRa
              Every element relates to itself.

Symmetric:    ∀a, b ∈ A: aRb → bRa
              If a relates to b, then b relates to a.

Antisymmetric: ∀a, b ∈ A: (aRb ∧ bRa) → a = b
              If a relates to b and b relates to a, they are equal.

Transitive:   ∀a, b, c ∈ A: (aRb ∧ bRc) → aRc
              If a relates to b and b relates to c, then a relates to c.