4.4 Binary relations

Definition of binary relations

A binary relation connects elements from one set to elements of another. It gives you a precise way to say "this element is related to that element," which turns out to be the foundation for functions, orderings, equivalence, and many other structures in mathematics.

Sets and ordered pairs

A binary relation $R$ from set $A$ to set $B$ is defined as a subset of the Cartesian product $A \times B$. In practice, that means $R$ is just a collection of ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.

• Notation: Writing $aRb$ or $(a, b) \in R$ both mean "$a$ is related to $b$ under $R$."
• Order matters: $(a, b) \neq (b, a)$ unless the relation specifically makes them equal. The first element comes from $A$, the second from $B$.

For example, if $A = \{1, 2\}$ and $B = \{x, y\}$, then $R = \{(1, x), (2, y)\}$ is a binary relation from $A$ to $B$.

Domain and codomain

Three terms come up constantly when working with relations:

• Domain of $R$: the set of all first elements that actually appear in the relation. $\text{Dom}(R) = \{a \in A \mid \exists\, b \in B,\; (a, b) \in R\}$
• Codomain of $R$: the entire set $B$, whether or not every element of $B$ shows up in a pair. $\text{Cod}(R) = B$
• Range of $R$: the set of second elements that actually appear in the relation. $\text{Range}(R) = \{b \in B \mid \exists\, a \in A,\; (a, b) \in R\}$

The distinction between codomain and range trips people up. The codomain is the whole target set; the range is only the part of it that gets "hit" by the relation.

Types of binary relations

Different types of relations are defined by specific properties they satisfy. Recognizing which properties a relation has tells you a lot about how it behaves.

Reflexive relations

A relation $R$ on set $A$ is reflexive if every element relates to itself:

$\forall\, a \in A,\; (a, a) \in R$

The identity relation on any set is always reflexive. The "less than or equal to" relation ($\leq$) on real numbers is reflexive because every number is $\leq$ itself. By contrast, the strict "less than" relation ($<$) is not reflexive, since no number is strictly less than itself.

Symmetric relations

A relation $R$ on $A$ is symmetric if whenever $a$ is related to $b$, then $b$ is also related to $a$:

$\forall\, a, b \in A,\; (a, b) \in R \Rightarrow (b, a) \in R$

"Is a sibling of" is symmetric: if Alice is a sibling of Bob, then Bob is a sibling of Alice. Equality ($=$) is also symmetric. But "is a parent of" is not symmetric, since the relationship only goes one direction.

Transitive relations

A relation $R$ on $A$ is transitive if relating $a$ to $b$ and $b$ to $c$ forces $a$ to relate to $c$:

$\forall\, a, b, c \in A,\; (a, b) \in R \text{ and } (b, c) \in R \Rightarrow (a, c) \in R$

The "greater than" relation ($>$) on real numbers is transitive: if $a > b$ and $b > c$, then $a > c$. Ancestry works the same way. A common counterexample: "is a friend of" in a social network is typically not transitive.

Equivalence relations

A relation that is reflexive, symmetric, and transitive all at once is called an equivalence relation. These are especially important because they partition a set into disjoint subsets called equivalence classes.

A classic example: "has the same remainder when divided by $n$" defines an equivalence relation on the integers. Congruence of geometric shapes is another. Equivalence relations show up throughout abstract algebra when constructing quotient structures.

Properties of binary relations

Beyond reflexivity, symmetry, and transitivity, relations can have additional properties that connect them to functions and mappings.

Functionality

A relation $R$ from $A$ to $B$ is functional if each element of $A$ relates to at most one element of $B$:

$\forall\, a \in A,\; \text{if } (a, b_1) \in R \text{ and } (a, b_2) \in R, \text{ then } b_1 = b_2$

Functions are exactly the relations that have this property (and where every element of the domain has an output). On a graph, the vertical line test checks functionality: if any vertical line crosses the graph more than once, the relation isn't functional.

Injectivity

An injective (one-to-one) relation maps distinct domain elements to distinct codomain elements:

$\forall\, a_1, a_2 \in A,\; \text{if } (a_1, b) \in R \text{ and } (a_2, b) \in R, \text{ then } a_1 = a_2$

No two different inputs share the same output. The exponential function $f(x) = e^x$ is injective. The function $f(x) = x^2$ on all real numbers is not, because $f(2) = f(-2) = 4$. Graphically, the horizontal line test checks this.

Surjectivity

A relation $R$ from $A$ to $B$ is surjective (onto) if every element of $B$ is related to by at least one element of $A$:

$\forall\, b \in B,\; \exists\, a \in A \text{ such that } (a, b) \in R$

The linear function $f(x) = 2x + 1$ from $\mathbb{R}$ to $\mathbb{R}$ is surjective because every real number is an output. But $f(x) = x^2$ from $\mathbb{R}$ to $\mathbb{R}$ is not surjective, since negative numbers never appear as outputs.

Bijectivity

A bijective relation is both injective and surjective. It creates a perfect one-to-one correspondence between domain and codomain, meaning every element pairs up exactly once. Bijections are the only relations that have a well-defined inverse function.

For example, $f(x) = 3x + 2$ on the reals is bijective. Bijections are crucial in set theory for proving that two sets have the same cardinality.

Representation of binary relations

There are several ways to represent a relation, and each one makes different properties easier to see.

Matrix representation

You can represent a relation $R$ from a finite set $A$ to a finite set $B$ as a Boolean matrix $M(R)$:

• Rows correspond to elements of $A$, columns to elements of $B$.
• Entry $m_{ij} = 1$ if $(a_i, b_j) \in R$, and $m_{ij} = 0$ otherwise.

This representation makes certain properties easy to check. A reflexive relation has all 1s on the main diagonal. A symmetric relation has a matrix equal to its own transpose.

Graph representation

Relations can be visualized as directed graphs (digraphs). Each element becomes a vertex, and a directed edge from $a$ to $b$ means $(a, b) \in R$. This is especially useful for spotting cycles, paths, and connectivity patterns.

Set notation

The most direct representation: list the relation as a set of ordered pairs.

$R = \{(a, b) \mid a \in A,\; b \in B,\; \text{and } aRb\}$

This is the standard way to define relations in proofs and formal definitions, and it supports set-theoretic operations like union, intersection, and complement.

Operations on binary relations

You can build new relations from existing ones using several operations.

Composition of relations

Given a relation $R$ from $A$ to $B$ and a relation $S$ from $B$ to $C$, the composition $R \circ S$ (sometimes written $S \circ R$ depending on convention) is:

$R \circ S = \{(a, c) \mid \exists\, b \in B,\; (a, b) \in R \text{ and } (b, c) \in S\}$

Think of it as chaining: $a$ connects to some $b$ through $R$, and that $b$ connects to $c$ through $S$. In matrix form, you compute $M(R) \times M(S)$ (using Boolean multiplication). Composition is generally not commutative.

Inverse relations

The inverse of a relation $R$ from $A$ to $B$ simply flips every pair:

$R^{-1} = \{(b, a) \mid (a, b) \in R\}$

In matrix form, $M(R^{-1})$ is the transpose of $M(R)$. Note that even if $R$ is a function, $R^{-1}$ might not be (it could map one element to multiple elements).

Complement of relations

The complement $R^c$ contains every pair in $A \times B$ that is not in $R$:

$R^c = \{(a, b) \mid a \in A,\; b \in B,\; (a, b) \notin R\}$

In matrix form, $M(R^c) = J - M(R)$, where $J$ is the all-ones matrix. Complements are useful for analyzing properties like irreflexivity and asymmetry.

Special binary relations

Some relations have specific combinations of properties that make them particularly important.

Partial orders

A partial order is a relation that is reflexive, antisymmetric, and transitive. Antisymmetry means: if $a \leq b$ and $b \leq a$, then $a = b$.

• The subset relation $\subseteq$ on the power set of any set is a partial order.
• Hasse diagrams provide a compact visual representation of partial orders.
• Not all elements need to be comparable. Two elements $a$ and $b$ might have neither $a \leq b$ nor $b \leq a$.

Total orders

A total order is a partial order where every pair of elements is comparable:

$\forall\, a, b \in A,\; a \leq b \text{ or } b \leq a$

The natural numbers under $\leq$ form a total order. Lexicographic (dictionary) ordering of strings is another example. Total orders are what let you meaningfully talk about "minimum" and "maximum" elements.

Equivalence classes

Given an equivalence relation $R$ on set $A$, the equivalence class of an element $a$ is:

$[a]_R = \{b \in A \mid aRb\}$

Every element in the class is related to every other element in that class. The equivalence classes partition $A$ into non-overlapping groups that cover the entire set.

In modular arithmetic, for instance, the equivalence classes mod 3 are $\{..., -3, 0, 3, 6, ...\}$, $\{..., -2, 1, 4, 7, ...\}$, and $\{..., -1, 2, 5, 8, ...\}$. These classes are the building blocks of quotient structures in abstract algebra.

Applications of binary relations

Binary relations appear throughout mathematics and computer science as a modeling tool.

Databases and relational algebra

Relational databases are built on binary (and more generally, $n$-ary) relations. Tables represent relations, and operations like join, projection, and selection come from relational algebra. Functional dependencies, which drive database normalization, are a special type of relation between attributes.

Graph theory connections

Directed graphs are essentially binary relations visualized. The adjacency relation of a graph is a binary relation, and computing the transitive closure of that relation tells you which vertices can reach which others. Graph algorithms like shortest path and cycle detection rely on relational operations.

Social network analysis

Social connections between people can be modeled as binary relations. From there, you can compute centrality measures, detect communities through clustering, model how influence propagates (using transitivity), and predict new links based on the structure of existing relations.

Binary relations vs functions

Functions are a special case of binary relations, so understanding how they relate helps you choose the right tool.

Similarities and differences

• Both map elements from one set to another using ordered pairs.
• A function requires exactly one output for each input; a general relation allows multiple outputs, no output, or one output per input.
• Domain, codomain, and range apply to both, but a function's domain is the entire source set.
• Every relation has an inverse relation; a function's inverse only exists as a function if the original is bijective.
• Composition works for both, but composing general relations can produce results that aren't functions.

When to use each concept

• Use relations when you need to model general associations: symmetric relationships, many-to-many connections, or situations where not every element needs a partner.
• Use functions when each input must produce exactly one output: deterministic processes, mathematical operations, transformations.

Proofs involving binary relations

Proving properties of relations is a core skill in this course. Most proofs follow a predictable structure.

Proving relation properties

Here's the standard approach for each property:

1. Reflexivity: Take an arbitrary $a \in A$ and show $(a, a) \in R$, usually by applying the definition of $R$.
2. Symmetry: Assume $(a, b) \in R$ and show $(b, a) \in R$ follows.
3. Transitivity: Assume $(a, b) \in R$ and $(b, c) \in R$, then show $(a, c) \in R$.
4. Antisymmetry: Assume $(a, b) \in R$ and $(b, a) \in R$, then show $a = b$ (proof by contradiction often works here).
5. Equivalence relation: Prove all three of reflexivity, symmetry, and transitivity.

To disprove a property, you only need one counterexample.

Constructing relation examples

When you need to build a relation with specific properties:

• Work with small finite sets (like $\{1, 2, 3\}$) to keep things manageable.
• Use set-builder notation for precise definitions.
• Check each required property systematically after constructing the relation.
• You can modify existing relations or combine them using union, intersection, or composition to get the properties you need.

Binary relations in set theory

Relations connect deeply to foundational set theory concepts.

Power sets and relations

The power set $P(A)$ contains all subsets of $A$. Since a binary relation from $A$ to $B$ is any subset of $A \times B$, the set of all possible relations from $A$ to $B$ is $P(A \times B)$. For finite sets, the number of possible relations is $2^{|A| \times |B|}$, which grows very fast.

Cartesian products

The Cartesian product $A \times B$ is the foundation: every binary relation is a subset of it. Properties of Cartesian products (like how they distribute over union and intersection) directly affect how relation operations work. Projections from $A \times B$ onto $A$ or $B$ recover the domain and range of a relation.

Computational aspects

When relations are implemented in software, efficiency matters.

Algorithms for relation operations

• Composition: Matrix multiplication gives you the composition. Naive approach runs in $O(n^3)$; advanced algorithms can do better.
• Transitive closure: Warshall's algorithm computes this in $O(n^3)$.
• Union/intersection: $O(n^2)$ for matrix representations (element-wise OR or AND).
• Property checking: Verifying reflexivity or symmetry on a matrix is $O(n^2)$.
• Graph traversal: DFS and BFS for reachability analysis run in $O(V + E)$.
• Topological sorting of partially ordered sets also runs in $O(V + E)$.

Complexity considerations

• Matrix representations use $O(n^2)$ space; sparse representations (adjacency lists) use $O(E)$, which is better when the relation has few pairs relative to $|A| \times |B|$.
• Some relational problems are NP-complete (e.g., finding the largest clique in a graph), meaning no known efficient algorithm exists for them.
• The choice between matrix and graph representations involves a time-space tradeoff that depends on how dense the relation is and what operations you need to perform.