** Relations and Graphs**

The * cartesian product* of two sets
* A * and * B * , denoted
* A X B * , is the set of all ordered pairs * (a, b) * where
* a ∈ A * and * b ∈ B * .

A * relation* between two sets is a subset of their
cartesian product.

A * graph* is a pair * (S, Γ) * where * S * is
a set of nodes and * Γ ⊆ S X S * .

Properties of relations:

Property: | Definition: |

Reflexive | ∀ a (a, a) ∈ R |

Symmetric | ∀ a, b (a, b) ∈ R →
(b, a) ∈ R |

Transitive | ∀ a, b, c (a, b) ∈ R ∧ (b, c) ∈ R |

→ (a, c) ∈ R | |

Antisymmetric |
∀ a, b (a, b) ∈ R ∧ (b, a) ∈ R
→ a = b |

A relation that is reflexive, symmetric,
and transitive is an
* equivalence relation*, which corresponds to a
* partition*
of the set (a set of disjoint subsets whose union is the set).

A relation that is reflexive, antisymmetric, and transitive is a
* partial order*. Example: * ≤ * .