4.2 Binary Relations and Their Properties

Section 4.1 treated a function as a special collection of ordered pairs. We now remove the “exactly one output” restriction and study arbitrary connections.

A social network may connect one person to many people. A number may divide several other numbers. A web page may link to itself, to another page, or to no page at all. These situations are modeled by binary relations.

What a binary relation records

Given sets $A$ and $B$, a binary relation from $A$ to $B$ is a subset

If $(a,b)\in R$, we write

and say “$a$ is related to $b$.” The symbol $R$ does not have one fixed meaning; the definition of the relation tells us what connection it represents.

For example, let

and define $R$ by “is less than.” Then

The pair $(1,3)$ belongs to $R$ because $1<3$, while $(3,1)$ does not.

A relation on $A$ is a relation from $A$ to itself:

The properties in this section—reflexive, symmetric, antisymmetric, and transitive—are normally discussed for relations on one set.

Four ways to represent the same finite relation

Let $A=\{1,2,3\}$ and

We can view the same information in several forms:

1. Roster form: list the ordered pairs, as above.

2. Arrow diagram: draw an arrow from $a$ to $b$ whenever $(a,b)\in R$.

3. Directed graph: use one vertex for each element and the same rule for directed edges.

4. Zero-one matrix: put $1$ in row $a$, column $b$ when $(a,b)\in R$, and $0$ otherwise.

Using the order $1,2,3$ for rows and columns, the matrix is

At this point the matrix is a compact grid of membership answers; no matrix algebra is required. Each cell simply answers, “Does this ordered pair belong to $R$?”

Reflexive: every element relates to itself

A relation $R$ on $A$ is reflexive when

In roster form, every pair $(a,a)$ must be present. In a directed graph, every vertex has a loop. In a matrix, every main-diagonal entry equals $1$.

The relation $\le$ on integers is reflexive because $a\le a$ for every integer $a$. The relation $<$ is not reflexive because $a<a$ is always false.

To disprove reflexivity, one missing loop is enough:

Symmetric: every arrow has a reverse arrow

A relation is symmetric when

In a matrix, symmetry means the entries mirror across the main diagonal:

“Has the same birthday month as” is symmetric: if Alice has the same birthday month as Bo, then Bo has the same birthday month as Alice.

“Is the parent of” is not symmetric. A single pair $aRb$ with $bRa$ absent is a counterexample.

Antisymmetric is not the opposite of symmetric

A relation is antisymmetric when

This says that two different elements cannot have arrows in both directions. Loops are allowed.

For example, $\le$ on integers is antisymmetric: if $a\le b$ and $b\le a$, then $a=b$. Divisibility on positive integers is also antisymmetric: if $a\mid b$ and $b\mid a$, then $a=b$.

Symmetric and antisymmetric are not logical opposites. The equality relation

is both symmetric and antisymmetric. A relation containing no two-way connection between distinct elements can also satisfy both.

Transitive: two steps force a shortcut

A relation is transitive when

In a directed graph, every two-edge route

requires a direct shortcut $a\to c$.

The relation $\le$ is transitive: $a\le b$ and $b\le c$ imply $a\le c$. “Is the parent of” is not transitive: a parent of a parent is usually a grandparent, not a parent.

A relation can be transitive even if it has very few edges. If no pair of edges forms the premise $aRb\land bRc$, then the implication is true because there is no violating chain. This is the same implication logic studied in Chapter 2.

Property audit of one relation

For

we have:

Paint cells in a relation matrix and watch the matching directed network update. Four inspectors identify missing loops, unpaired arrows, forbidden two-way connections, and missing transitive shortcuts; every failure includes a concrete witness.

Repairing relations with closures

Sometimes a relation does not have a desired property, but we want to add the fewest ordered pairs needed to obtain it. A closure keeps every original pair and adds required pairs; it does not delete data.

Let

Reflexive closure

Add every missing loop:

Symmetric closure

For each pair, add its reverse:

This can be written compactly using the inverse relation

as

Here $R^{-1}$ means reversing ordered pairs. It is related to, but more general than, the inverse function from Section 4.1: every relation has an inverse relation, while only bijective functions have inverse functions.

Transitive closure

Because

transitivity requires $1R3$. Therefore

For a longer network, adding one shortcut may create a new two-step route, which may require another shortcut. The process continues until every reachable destination has a direct relation from its starting point.

One useful interpretation is:

Closures are smallest by inclusion: they contain the original relation, have the requested property, and do not include an unnecessary ordered pair.

Operate a metro network whose direct tracks are relation pairs. Passenger routes reveal which shortcuts transitivity demands. Add proposed express tracks, run the propagation animation, and repair the network without adding irrelevant connections.

Section bridge

We can now recognize structural patterns in arbitrary relations. The next section combines three of them—reflexive, symmetric, and transitive—to formalize the idea that different objects should count as “the same kind.” Those relations will divide a set into clean, non-overlapping groups.