Relations

Overview

Relating Elements

A relation captures the idea that two elements can be connected or associated. For example, "less than" relates pairs of numbers, and "is a friend of" relates pairs of people. Formally, a relation is defined using ordered pairs.

Definition

Binary Relation

A binary 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."

A relation on a set A is a relation from A to A (i.e., a subset of A × A).

Example: Let A = {1, 2, 3}. The relation "less than" on A is R = {(1,2), (1,3), (2,3)}.

Definition

Properties of Relations

A relation R on set A is:

Reflexive: aRa for all a ∈ A. (Every element is related to itself.) Symmetric: If aRb, then bRa. (The relation goes both ways.) Antisymmetric: If aRb and bRa, then a = b. Transitive: If aRb and bRc, then aRc. (The relation chains.)

Example

Identifying Properties

"≤" on integers: • Reflexive: a ≤ a ✓ • Antisymmetric: if a ≤ b and b ≤ a, then a = b ✓ • Transitive: if a ≤ b and b ≤ c, then a ≤ c ✓ • Symmetric: 1 ≤ 2 but 2 ≤ 1 is false ✗

"=" on integers: • Reflexive ✓ Symmetric ✓ Antisymmetric ✓ Transitive ✓

Definition

Equivalence Relation

A relation that is reflexive, symmetric, AND transitive is called an equivalence relation. It partitions the set into equivalence classes - groups of mutually related elements.

Example: "has the same remainder when divided by 3" is an equivalence relation on ℤ. The equivalence classes are {…, -3, 0, 3, 6, …}, {…, -2, 1, 4, 7, …}, and {…, -1, 2, 5, 8, …}.

Definition

Partial Order

A relation that is reflexive, antisymmetric, AND transitive is called a partial order. A set with a partial order is called a partially ordered set (poset).

Example: "⊆" on subsets of a set is a partial order. {1} ⊆ {1,2} and {1,2} ⊆ {1,2,3}, so {1} ⊆ {1,2,3}.