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: ≤ .