Relations — Mathematics Knowledge System

Overview

A binary relation associates some elements of one set, called the domain, with some elements of another set, called the codomain. Precisely, a binary relation over sets X and Y is a set R of ordered pairs (x, y), where x is an element of X and y is an element of Y. It encodes the common concept of relation: an element x is related to an element y — written xRy — if and only if the pair (x, y) belongs to R. Familiar examples include 'is less than' on numbers, 'is a subset of' on sets, and 'is the parent of' on people — each is fully captured by the set of ordered pairs for which the relation holds.

Intuition

Think of a relation as a directed wiring diagram between two piles of objects: draw an arrow from x to y exactly when x is related to y. The relation itself is nothing more than the complete list of arrows — the set of pairs (x, y). Special patterns of arrows give relations useful properties: if every object has an arrow to itself, the relation is reflexive; if an arrow from x to y always comes with one from y to x, it's symmetric; if arrows chain together (x→y and y→z always forces x→z), it's transitive. A relation with all three properties groups objects into clusters where everything in a cluster is mutually related — an equivalence relation.

Formal Definition

Definition

A binary relation R from a set X to a set Y is any subset of the Cartesian product X × Y. When X = Y, R is a relation on a single set. Relations support algebraic operations: union, intersection, composition, and converse (transpose).

R \subseteq X \times Y

Definition of a binary relation

R \cup S = \{(x,y) \mid xRy \text{ or } xSy\}

Union of relations

S \circ R = \{(x,z) \mid \exists y \in Y,\; xRy \land ySz\}

Composition of relations

R^{T} = \{(y,x) \mid xRy\}

Converse (transpose) of a relation

Notation

Notation	Meaning
$xRy$	x is related to y under relation RAlso written: (x,y) ∈ R
$R^{T}$	The converse relation: yR⁻¹x whenever xRy
$S \circ R$	Composition: relate x to z if some y links xRy and ySz
$\operatorname{dom}(R)$	The set of all x that appear as a first coordinate in R
$\operatorname{ran}(R)$	The set of all y that appear as a second coordinate in R (the range/image)

Properties

Reflexive

\forall x \in X,\; xRx

Symmetric

\forall x,y,\; xRy \to yRx

Antisymmetric

\forall x,y,\; (xRy \land yRx) \to x=y

Transitive

\forall x,y,z,\; (xRy \land yRz) \to xRz

Equivalence relation

R \text{ is reflexive, symmetric, and transitive}

Example: Congruence mod n on the integers

Partial order

R \text{ is reflexive, antisymmetric, and transitive}

Example: ⊆ on the power set of a set

Applications

Relational databases are literally built on relations: a table is a subset of the Cartesian product of its column domains, and joins are relational composition.

Worked Examples

Reflexive requires (x,x) ∈ R for every x ∈ X; (2,2) and (3,3) are missing, so R is not reflexive.
$(2,2) \notin R,\; (3,3) \notin R$
Transitive requires that (1,2) and (2,3) together force (1,3); but (1,3) ∉ R, so R is not transitive.
$(1,2) \in R \land (2,3) \in R \text{ but } (1,3) \notin R$

Answer: R is neither reflexive nor transitive.

Practice Problems

Difficulty 3/10

Is the relation ≤ on the integers a partial order? Justify briefly.

Difficulty 4/10

Which property does the relation 'is a sibling of' fail to have (assuming no one is their own sibling)?

SymmetricTransitiveReflexiveNone — it has all three

Difficulty 5/10

A relational database table 'Enrollment(student, course)' is literally a mathematical relation between students and courses. If it links 200 students to 30 courses, what set is it a subset of, and what does one row represent?

Difficulty 5/10

Grouping files by their type (all .pdf together, all .png together, etc.) partitions them. Which kind of relation does 'has the same file type as' represent, and what are its three defining properties?

Common Mistakes

Common Mistake

Assuming every relation that is symmetric and transitive is automatically reflexive.

This is a classic trap: symmetric + transitive does NOT imply reflexive in general, because an element with no related partner at all is never forced through the symmetric+transitive chain back to itself. (It does hold whenever every element is related to at least one other element.)

Common Mistake

Confusing antisymmetric with 'not symmetric'.

Antisymmetric means xRy and yRx together force x=y; a relation can fail to be symmetric without being antisymmetric, and can even be both (e.g. equality itself).

Quiz

Summary

A binary relation R from X to Y is any subset of the Cartesian product X × Y.
Key properties — reflexive, symmetric, antisymmetric, transitive — classify how a relation's arrows are patterned.
An equivalence relation (reflexive + symmetric + transitive) partitions a set into equivalence classes.
A partial order (reflexive + antisymmetric + transitive) captures notions like ≤ and ⊆.
Relations support algebraic operations — union, intersection, composition, converse — mirroring set algebra.

References

WebsiteWikipedia — Binary relation
BookRosen, K. Discrete Mathematics and Its Applications, 8th ed., Ch. 9.