Relations

Definition and Basic Concepts

Binary Relation

Definition: A binary relation R from set A to set B is a subset of Cartesian product A × B. Notation: R ⊆ A × B. Element (a,b) ∈ R means a is related to b.

Domain and Range

Domain: set of all a ∈ A such that ∃b ∈ B with (a,b) ∈ R. Range: set of all b ∈ B such that ∃a ∈ A with (a,b) ∈ R.

Relation on a Set

Relation R on set A: R ⊆ A × A. Also called homogeneous relation. Focuses on relationships within a single set.

Types of Relations

Reflexive Relation

Definition: ∀a ∈ A, (a,a) ∈ R. Self-related elements guaranteed.

Symmetric Relation

Definition: ∀a,b ∈ A, if (a,b) ∈ R then (b,a) ∈ R.

Antisymmetric Relation

Definition: ∀a,b ∈ A, if (a,b) ∈ R and (b,a) ∈ R then a = b.

Transitive Relation

Definition: ∀a,b,c ∈ A, if (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R.

Properties of Relations

Reflexivity

Property: Relation includes all pairs (a,a). Indicates self-connection.

Symmetry

Property: Relation pairs are bidirectional.

Antisymmetry

Property: No distinct pairs (a,b) and (b,a) coexist unless a=b.

Transitivity

Property: Relation chains produce implied pairs.

Irreflexivity

Property: No element relates to itself: ∀a, (a,a) ∉ R.

Totality (Connexity)

Property: ∀a,b ∈ A, a ≠ b implies (a,b) ∈ R or (b,a) ∈ R.

Equivalence Relations

Definition

Relation that is reflexive, symmetric, and transitive.

Equivalence Classes

Partition of set A into disjoint subsets where elements are related.

Quotient Set

Set of equivalence classes, denoted A/R.

Properties

Each element belongs to exactly one class. Classes are mutually exclusive.

Partial Orders

Definition

Relation that is reflexive, antisymmetric, and transitive.

Poset

Partially ordered set (A, ≤) where ≤ is a partial order.

Comparability

Not all pairs need to be comparable.

Hasse Diagram

Graphical representation of finite posets omitting transitive edges.

Representation of Relations

Set of Ordered Pairs

Explicit listing of pairs (a,b) ∈ R.

Directed Graphs

Vertices represent elements; edges represent relation pairs.

Boolean Matrix

Matrix M with M[i,j] = 1 if (a_i,a_j) ∈ R, else 0.

Adjacency List

List of reachable elements per vertex.

Operations on Relations

Union

R ∪ S = {(a,b) | (a,b) ∈ R or (a,b) ∈ S}.

Intersection

R ∩ S = {(a,b) | (a,b) ∈ R and (a,b) ∈ S}.

Difference

R \ S = {(a,b) | (a,b) ∈ R and (a,b) ∉ S}.

Complement

R^c = {(a,b) | (a,b) ∉ R} w.r.t. A × A.

Composition of Relations

Definition

For R ⊆ A × B, S ⊆ B × C, composition S ○ R = {(a,c) | ∃b ∈ B, (a,b) ∈ R and (b,c) ∈ S}.

Associativity

(T ○ S) ○ R = T ○ (S ○ R) for relations R, S, T.

Identity Relation

I_A = {(a,a) | a ∈ A}, identity for composition.

Examples

Used in database joins, graph pathfinding, and function composition.

Given:R = {(1,2),(2,3)}S = {(2,4),(3,5)}S ○ R = {(1,4),(2,5)}

Inverse Relation

Definition

Inverse R⁻¹ = {(b,a) | (a,b) ∈ R}.

Properties

(R⁻¹)⁻¹ = R, (S ○ R)⁻¹ = R⁻¹ ○ S⁻¹.

Relation to Symmetry

R symmetric ⇔ R = R⁻¹.

Applications

Reverse graph edges, invert functions (if bijective).

Relation Matrix

Definition

Relation on finite set A = {a₁,...,a_n} represented as n×n matrix M.

Matrix Entries

M[i,j] = 1 if (a_i,a_j) ∈ R; else 0.

Matrix Operations

Union: elementwise OR, Intersection: elementwise AND.

Composition via Boolean Matrix Multiplication

(S ○ R) represented by M_S × M_R using Boolean arithmetic.

Applications of Relations

Database Theory

Relations model tables; operations correspond to queries.

Graph Theory

Relations represent edges, paths, connectivity.

Computer Science

State transition systems, data structures, type theory.

Mathematical Logic

Model theory, equivalence classes, orderings.

Formal Languages

Relations encode grammar productions, parsing.

Worked Examples

Example 1: Checking Properties

Let A = {1,2,3}, R = {(1,1),(2,2),(3,3),(1,2),(2,1)}.

Reflexive: Yes, all (a,a) present.

Symmetric: (1,2) ∈ R and (2,1) ∈ R → Yes.

Transitive: (1,2) and (2,1) ∈ R but (1,1) ∈ R → Yes.

Conclusion: R is equivalence relation.

Example 2: Composition

Given R = {(a,b),(b,c)}, S = {(b,d),(c,e)}.

S ○ R = {(a,d),(b,e)}.

Step 1: Find pairs (a,b) ∈ R and (b,c) ∈ S
Step 2: For each b in R and S, pair (a,c) in composition
Result: {(a,d),(b,e)}

Example 3: Matrix Representation

A = {x,y}, R = {(x,y)}.

References

• Rosen, K. H., Discrete Mathematics and Its Applications, McGraw-Hill, 7th Ed., 2012, pp. 210-260.
• Lipschutz, S., Discrete Mathematics, Schaum’s Outline Series, McGraw-Hill, 1997, pp. 150-200.
• Grimaldi, R. P., Discrete and Combinatorial Mathematics, Pearson, 5th Ed., 2003, pp. 120-170.
• Epp, S. S., Discrete Mathematics with Applications, Cengage Learning, 4th Ed., 2011, pp. 300-350.
• Stanley, R. P., Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997, pp. 50-90.