Discrete Math › Section C · Graph theory › Topic C.7

Relations and their properties

"Is less than", "divides", "is enrolled in", "has a direct flight to": a relation records which things are connected to which. A handful of properties, reflexive, symmetric, antisymmetric and transitive, sort relations into the families that the rest of this section uses.

A relation is a set of pairs

A relation \(R\) from a set \(A\) to a set \(B\) is any subset of \(A \times B\), the set of ordered pairs \((a, b)\) with \(a \in A\) and \(b \in B\). We write \(a \mathrel{R} b\) when \((a, b) \in R\). A relation on \(A\) is a subset of \(A \times A\). For example, with students \(A\) and courses \(B\), "is enrolled in" is a relation from \(A\) to \(B\). A function is a special relation in which every element of \(A\) is paired with exactly one element of \(B\). Since any subset will do, a set of 3 elements has \(2^9 = 512\) relations on it.

Three ways to show a relation

A relation from \(A\) to \(B\) can be drawn as two columns of dots with an arrow from \(a\) to \(b\) for each pair, which looks like a bipartite graph. A relation on one set is drawn as a directed graph: one vertex per element, an arrow \(a \to b\) for each pair, and a loop at \(a\) when \(a \mathrel{R} a\). A third way is a 0-1 matrix with a 1 in row \(a\), column \(b\) exactly when \(a \mathrel{R} b\). Each picture makes some properties easy to spot, as the cards below show.

Inverse and composition

The inverse \(R^{-1}\) reverses every pair: \((b, a) \in R^{-1}\) exactly when \((a, b) \in R\). The inverse of "is enrolled in" is "has as a student". If \(R\) goes from \(A\) to \(B\) and \(S\) from \(B\) to \(C\), the composition \(S \circ R\) relates \(a\) to \(c\) when some \(b\) has \(a \mathrel{R} b\) and \(b \mathrel{S} c\). The order matters and matches function composition: \(R\) is applied first, although it is written second. If \(R\) is "is a parent of", then \(R \circ R\) is "is a grandparent of".

Worked example: composing relations

Let \(A = \{1, 2, 3\}\), \(B = \{x, y\}\) and \(C = \{p, q, r\}\), with \(R = \{(1,x), (2,x), (3,y)\}\) and \(S = \{(x,p), (x,q), (y,r)\}\). 1. Start from 1: \(R\) sends it to \(x\), and \(S\) sends \(x\) to \(p\) and \(q\), giving \((1,p)\) and \((1,q)\). 2. Likewise 2 goes through \(x\): \((2,p)\) and \((2,q)\). 3. Then 3 goes through \(y\): \((3,r)\). 4. So

S \circ R = \{(1,p), (1,q), (2,p), (2,q), (3,r)\}

5. Separately, \(R^{-1} = \{(x,1), (x,2), (y,3)\}\), a relation from \(B\) to \(A\). It is not a function, because \(x\) is paired with two elements.

Reflexive, symmetric, transitive

Let \(R\) be a relation on \(A\). It is reflexive if \(a \mathrel{R} a\) for every \(a \in A\): every vertex of the directed graph has a loop, and the matrix diagonal is all 1s. It is symmetric if \(a \mathrel{R} b\) always implies \(b \mathrel{R} a\): every arrow has a partner going back, and the matrix equals its transpose. It is transitive if \(a \mathrel{R} b\) and \(b \mathrel{R} c\) together imply \(a \mathrel{R} c\): every two-step route has a direct shortcut. Equality has all three. "Divides" on the positive integers is reflexive and transitive but not symmetric, since 2 divides 4 and 4 does not divide 2.

Antisymmetric

A relation is antisymmetric if \(a \mathrel{R} b\) and \(b \mathrel{R} a\) together force \(a = b\). In the directed graph, no two distinct vertices have arrows both ways; in the matrix, no pair of off-diagonal positions \((a, b)\) and \((b, a)\) both hold 1. The relation \(\le\) is antisymmetric, and so is "divides" on the positive integers. Antisymmetric is not the opposite of symmetric. Equality is both. The relation \(\{(1,2), (2,1), (1,3)\}\) on \(\{1, 2, 3\}\) is neither: the pair 1, 2 goes both ways, but \((1,3)\) has no partner.

Worked example: testing the properties

On \(A = \{1, 2, 3, 4\}\), let \(R\) contain the four loops \((1,1)\) to \((4,4)\) and also \((1,2)\), \((2,3)\) and \((1,3)\). 1. Reflexive: all four loops are present, so yes. 2. Symmetric: \((1,2)\) is in but \((2,1)\) is not, so no. 3. Antisymmetric: no two distinct elements are related both ways, so yes. 4. Transitive: the only two-step route between different elements is 1 to 2 to 3, and \((1,3)\) is present; routes through loops add nothing new. So yes. Now take \(S = \{(1,2), (2,1)\}\) on \(\{1, 2, 3\}\). It is symmetric, but not transitive: \((1,2)\) and \((2,1)\) would require \((1,1)\).

Closures

When a relation lacks a property, we can add the fewest pairs that give it the property; the result is a closure. The reflexive closure adds every missing loop, and the symmetric closure adds every missing reverse pair. The transitive closure is the most useful: \(a\) is related to \(c\) when some chain of arrows leads from \(a\) to \(c\). If \(R = \{(a,b), (b,c), (c,d)\}\) means "has a direct flight to", the transitive closure adds \((a,c)\), \((b,d)\) and \((a,d)\), and means "can be reached by some sequence of flights". Warshall's algorithm computes it for \(n\) elements in about \(n^3\) steps.

Relations in databases

A table in a relational database is a relation in exactly this sense, a set of rows, with each row a tuple of values. Edgar Codd built the relational model on this mathematics in 1970, and SQL, the standard language for such databases, rests on it. Joining two tables on a shared column, then dropping that column, is composition: joining a table of students and courses to a table of courses and rooms tells you which students meet in which rooms. Asking which records can be reached by following links again and again is a transitive closure query.

Common mistakes to avoid

First, reading composition in the wrong order: in \(S \circ R\), apply \(R\) first. Second, calling a relation reflexive because some elements relate to themselves; every element of \(A\) must. Third, treating antisymmetric as "not symmetric"; a relation can be both or neither. Fourth, missing the transitivity trap in which \((a,b)\) and \((b,a)\) are present: transitivity then demands \((a,a)\) and \((b,b)\). Fifth, thinking an empty or vacuous case fails a property; the empty relation is symmetric, antisymmetric and transitive, because no pair breaks the rules.

Key takeaways

A relation from \(A\) to \(B\) is a subset of \(A \times B\); functions are special relations. Relations can be drawn as arrow diagrams or directed graphs, or stored as 0-1 matrices. The inverse reverses every pair, and \(S \circ R\) applies \(R\) first, then \(S\). A relation on \(A\) may be reflexive (all loops), symmetric (arrows come in pairs), antisymmetric (no two-way arrows between distinct elements) or transitive (two-step routes have shortcuts). Closures add the fewest pairs needed, and the transitive closure records reachability.

Flashcards

Flashcard

Relation from A to B

Any subset of A × B

Write a R b when (a, b) is in R.

Test your understanding

Question 1 of 5

On {1, 2, 3}, let R = {(1,1), (2,2), (1,2), (2,1), (2,3), (3,2)}. Which property does R have?

Question 2 of 5

Let R = {(1,a), (2,b)} and S = {(a,x), (b,y), (b,z)}. What is S ∘ R?

Question 3 of 5

How many different relations are there on a set with 3 elements?

Question 4 of 5

On {a, b, c}, what is the transitive closure of R = {(a,b), (b,c)}?

Question 5 of 5

Which properties does the relation "is a proper subset of" have on the subsets of {1, 2, 3}?

← Previous topicNext topic →