Relations on Sets

Relations in set theory describe connections between elements of two sets. A relation is nothing more than a set from the Cartesian product: if A and B are sets, then R ⊆ A × B. This means that the relation is the collection of connections between elements of A and B.

If (a,b) ∈ R, we say that 'element a is in relation with b'.

Types of Relations

• Reflexive: every element is in relation with itself. Example: '≤' relation on integers.
• Symmetric: if (a,b) ∈ R, then (b,a) ∈ R. Example: 'acquaintance' relation among people.
• Transitive: if (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R. Example: '≤' relation on integers.
• Antisymmetric: if (a,b) ∈ R and (b,a) ∈ R, then a = b. Example: '≤' relation on integers.

If a relation is reflexive, symmetric, and transitive, it is called an equivalence relation. Equivalence relations partition a set into equivalence classes.

Solved Example

Let A = {1,2,3}, and define a relation R as: R = {(1,1), (2,2), (3,3), (1,2), (2,1)}. Examine its properties!

• Reflexive? Yes, because every element is in relation with itself: (1,1), (2,2), (3,3) ∈ R.
• Symmetric? Yes, because if (1,2) ∈ R, then (2,1) ∈ R.
• Transitive? Yes, because for every case where (a,b) ∈ R and (b,c) ∈ R, (a,c) ∈ R holds. Let's check: (1,2) ∈ R and (2,1) ∈ R, so (1,1) ∈ R must hold, which it does. Further pairs like (2,3) or (3,1) do not exist, so no other cases to check.
• Antisymmetric? No, because (1,2) and (2,1) are both in it, yet 1 ≠ 2.

This relation is therefore reflexive, symmetric, and transitive, so an equivalence relation. The equivalence classes: {1,2} and {3}.

Applications

• Ordering relations: e.g., ≤, <, which are antisymmetric and transitive.
• Equivalence relations: e.g., 'same birth year' among people.
• Databases: modeling connections between elements of two tables.
• Graph theory: relations can be represented as graphs, where elements are vertices, relations are edges.

Summary

Relations allow us to describe connections between elements of sets. The most important properties: reflexive, symmetric, transitive, antisymmetric. Their combinations determine if the relation is, for example, an ordering or equivalence relation.

Practice Exercise