Relations

Internal

• Mathematics

Overview

A binary relation R on two sets A and B is a subset of the Cartesian product A x B. If (a, b) belongs to the subset of the Cartesian product that defines the relation, we write a R b.

A binary relation R on a set A is a subset of the Cartesian product A x A.

A n-ary relation on sets A₁, A₂, .... A_n is a subset of the Cartesian product A₁ x A₂ x ... x A_n.

An example of a binary relation on a finite set is the edge set of a graph.

Binary Relation Properties

A binary relation R ⊆ A x A is reflexive if a R a for all a ∈ A.

A binary relation R ⊆ A x A is symmetric if a R b implies b R a for all a, b ∈ A.

A binary relation R ⊆ A x A is transitive if a R b and b R c implies a R c for all a, b, c ∈ A.

A binary relation R ⊆ A x A is antisymmetric if a R b and b R a imply a = b.

Equivalence

A relation that is reflexive, symmetric and transitive is an equivalence relation. For example, "=" is an equivalence relation on the natural numbers.

Equivalence class. If R is an equivalence relation on the set A, then for a ∈ A, the equivalence class of a is the set [a] = {b ∈ A, where a R b}. In other words, the equivalence set of a is the set of all elements equivalent to a, relative to relation R.

Theorem: An equivalence relation is the same as a partition. The equivalence classes of any equivalence relation R on a set A for a partition of A, and any partition of A determines an equivalence relation on A for which the sets in the partition are the equivalence classes.

TODO

CLRS page 1163