Relations

Relations are super useful and a basic concept in many areas of mathematics and computer science. We can build this concept basically directly from what we learned from set theory. You already know many examples, like $\leq$ and $>$ , and so on. We will also see that functions are simply relations with a special property.

Intuition Theory Exercises

Definition 3.9: A (binary) relation $\rho$ from a set $A$ to a set $B$ (also called an $(A, B)$ - relation) is a subset of $A \times B$ . If $A = B$ , then $\rho$ is called a relation on $A$ .

Oftentimes we will see something like:

Given some relation $\rho$ on $A$ that is ..., prove that $\rho$ fulfills ...

Intuition

⚠️

Don't use intuition to argue or prove something. This is only meant to be to get an idea of a proof, on logic level, or to get an idea of whether some statement is true or false. For example, statements like there is a relation that is ... and .... Additionally, this intuition will probably make it easier to find counterexamples. But still, you have to always argue using definitions and logic.

Graphs

⚠️

This is not to be confused with Hasse Diagrams for partial order relations

Really, if you think about a relation $\rho \subseteq A \times A$ (i.e. a relation which is defined on one set $A$ , which might be generic) and you have some property, think about the directed graph representation of this property - draw it! Oftentimes, this feels like cheating, because some exercises seem trivial when looking at them in graph representation. After learning about graphs in A&D, you might even be tempted to think about what the different graph algorithms and properties mean in the context of relations.

So what is the graph representation?

We use nodes to depict elements of the set $A$ . Of course, oftentimes $A$ is an arbitrary/generic set, we can still draw some dots for the elements of $A$ to try to understand the structure of the relation.
For each element $(a,b) \in \rho$ draw an arrow from node $a$ to node $b$ . If we again have some generic relation, that satisfies certain properties, try to understand how these properties are represented in your graph. I will elaborate on it in the section on properties. However, it is a good practice to do so.

Example: Consider the set $A = \{1,2,3,4,5,6,7,8\}$ and the relation

\rho = \{(1,2),(1,3),(2,4),(3,7),(3,8),(2,5),(4,5),(5,6),(6,7),(7,8)\}

Then we obtain the following graph representation

Simple graph representation - by Tobias Steinbrecher

Matrices

⚠️

The formalities defined in this section on matrices are not covered in the lecture. However, it might help deepen the understanding of the topic.

For relations on finite sets $A, B$ we can also represent relations as matrices in $\{0, 1\}^{n \times m}$ where $n = |A|$ and $m = |B|$ . The matrix representation gives us an additional tool for understanding different properties and operations on relations.

Let $A = \{a_1, \dots, a_n\}$ and $B = \{b_1, \dots, b_m\}$ , $\rho \subseteq A \times B$ . We define $M^{\rho} \in \{0, 1\}^{n \times m}$ as follows:

M^{\rho}(i,j) = a_i \rho b_j \\

Thus

M^{\rho} = \begin{pmatrix} a_1 \rho b_1 & a_1 \rho b_2 & \dots & a_1 \rho b_m \\ a_2 \rho b_1 & a_2 \rho b_2 & \dots & a_2 \rho b_m \\ \vdots & \vdots & \ddots & \vdots \\ a_n \rho b_1 & a_n \rho b_2 & \dots & a_n \rho b_m \\ \end{pmatrix}

Example

\ \rho = \{ (1, 3), (2, 1), (3, 2), (4, 1) \}

Let $A = B = \{1,2,3,4\}$ and $\rho = \{ (1, 3), (2, 1), (3, 2), (4, 1) \}$ . Then:

M^{\rho} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{pmatrix}

Matrix Operations

In Linear Algebra we have seen component-wise addition on matrices. Here we will define similar component-wise operations $+$ (OR) and $\ast$ (AND). Note that these definitions are the same as in LinAlg but since these matrices contain truth values instead of numbers, we define scalar addition as OR and scalar multiplication as AND.

In Algebra (chapter 5) you will see that these operations correspond to addition and multiplication on the field $\mathbb{Z}_2$ and the matrices are elements of the vector space $\mathbb{Z}_2^{n \times m}$ .

\begin{aligned} (A + B)_{i,j} &= A_{i,j} \lor B_{i,j} \\ (A \ast B)_{i,j} &= A_{i,j} \land B_{i,j} \\ \end{aligned}

Thus

\begin{aligned} A + B &= \begin{pmatrix} A_{1,1} \lor B_{1,1} & \dots & A_{1,m} \lor B_{1,m} \\ \vdots & \ddots & \vdots \\ A_{1,n} \lor B_{1,n} & \dots & A_{n,m} \lor B_{n,m} \\ \end{pmatrix} \\ A \ast B &= \begin{pmatrix} A_{1,1} \land B_{1,1} & \dots & A_{1,m} \land B_{1,m} \\ \vdots & \ddots & \vdots \\ A_{1,n} \land B_{1,n} & \dots & A_{n,m} \land B_{n,m} \\ \end{pmatrix} \\ \end{aligned}

We define standard matrix multiplication again using OR as addition and AND as scalar multiplication:

(A \cdot B)_{i,j} = \bigvee_{k=1}^{n} A_{i,k} \land B_{k,j}

Operations on Relations

Proven by intimidation or alternatively by the reader, we can find the following correspondence between operations on relations and operations on matrices:

M^{\rho \cap \sigma} = M^{\rho} \ast M^{\sigma} \\ M^{\rho \cup \sigma} = M^{\rho} + M^{\sigma} \\ M^{\rho \circ \sigma} = M^{\rho} \cdot M^{\sigma} \\ M^{\hat\rho} = (M^{\rho})^\top \\

\rho \subseteq \sigma \iff M^{\rho} \ast M^{\sigma} = M^{\rho} \\

For a relation $\rho$ on $A$ we further find that

M^{\rho^k} = (M^{\rho})^k \\ M^{\rho^*} = \sum_{k \in \mathbb{N}\setminus\{0\}} (M^{\rho})^k

The transitive closure of a relation $\rho$ can be determined algorithmically using the following pseudocode. It can be shown that the while loop terminates after at most $\mathcal{O}(\log n)$ iterations.

A = zero_matrix(n,n)
B = matrix(\rho)
while A != B:
    A = B
    B += B.multiply(B)
return A

Special Relation Matrices

\begin{aligned} \rho \text{ is reflexive} &\iff \text{for all } 1 \leq i \leq n \hspace{1em} M^{\rho}_{i,i} = 1 \\ &\iff \text{diagonal of } M^\rho \text{ all } 1 \\[2em] \rho \text{ is irreflexive} &\iff \text{for all } 1 \leq i \leq n \hspace{1em} M^{\rho}_{i,i} = \textbf{0}_n \\ &\iff \text{diagonal of } M^\rho \text{ all 0} \\[2em] \rho \text{ is symmetric} &\iff M^{\rho} = (M^{\rho})^\top \\ &\iff \text{for all } 1 \leq i,j \leq n \hspace{1em} M^{\rho}_{i,j} = M^{\rho}_{j,i} \\ &\iff \text{matrix } M^\rho \text{ is symmetric} \\[2em] \rho \text{ is antisymmetric} &\iff \text{for all } 1 \leq i,j \leq n \hspace{1em} M^{\rho}_{i,j} \land M^{\rho}_{j,i} = \textbf{0}_n \\[2em] \rho \text{ is transitive} &\iff (M^{\rho})^2 \ast M^{\rho} = (M^{\rho})^2 \\ \end{aligned}

Theory

Properties

Reflexive Relations

A relation is called $\rho$ is called reflexive, if for all $a \in A$ :

a \rho a

To prove reflexivity of a relation, we often start with something like:

Let $a \in A$ be arbitrary...

Then our goal is to derive that $a \rho a$ (from some given properties about $\rho$ ).

In the graph visualization of a reflexive relation, we must have a self-loop at each node:

Example of a graph of a reflexive relation - by Tobias Steinbrecher

Irreflexive Relations

A relation $\rho$ is called irreflexive if for all $a \in A$ :

\lnot(a \rho a)

Symmetric Relation

A relation is called symmetric if for all $a,b\in A$ :

a \rho b \implies b \rho a

To prove symmetry of a relation, we often start with something like:

Let $a,b \in A$ be arbitrary, such that $a \rho b$ .
$\begin{aligned} a \rho b &\overset{\cdot}{\implies} \dots \\ & \overset{\cdot}{\implies} \dots \\ &\overset{\cdot}{\implies} b \rho a \end{aligned}$
Therefore $\dots$

In the graph representation, all the edges have to go in both directions:

Example of a graph of a symmetric relation - by Tobias Steinbrecher

Transitive Relations

A relation is called transitive if for all $a,b,c \in A$ :

a \rho b \land b \rho c \implies a \rho c

To prove transitivity of a relation, we often start with something like:

Let $a,b,c \in A$ be arbitrary, such that $a \rho b$ and $b \rho c$ .
$\begin{aligned} a \rho b \land b \rho c &\overset{\cdot}{\implies} \dots \\ & \overset{\cdot}{\implies} \dots \\ &\overset{\cdot}{\implies} a \rho c \end{aligned}$
Therefore $\dots$

The following graph is an example of a transitive relation

Example of a graph of a transitive relation - by Tobias Steinbrecher

Antisymmetric Relation

A relation is called antisymmetric if for all $a,b \in A$ :

a \rho b \land b\rho a \implies a = b

To prove antisymmetry of a relation, we often start with something like:

Let $a,b \in A$ be arbitrary, such that $a \rho b$ and $b \rho a$ .
$\begin{aligned} a \rho b \land b \rho a &\overset{\cdot}{\implies} \dots \\ & \overset{\cdot}{\implies} \dots \\ &\overset{\cdot}{\implies} a = b \end{aligned}$
Therefore $\dots$

In the graph of an antisymmetric relation, it can never be the case that there is an edge from node $a$ to $b$ and an edge from node $b$ to $a$ . Otherwise, the two elements corresponding to the nodes would have to be equal, which is a contradiction, as we draw different nodes for different elements.

Equivalence Relations

An equivalence relation needs to satisfy three properties:

An equivalence relation is a relation over a set $A$ which satisfies reflexivity, symmetry and transitivity.

This means to show that a relation is an equivalence relation, we simply need to confirm all of the three properties one by one. To disprove that a relation is an equivalence relation, it is enough to disprove one of the properties (often using a concrete counterexample). The graphs of equivalence relations look like this:

Example of a graph of an equivalence relation

We can see that the graph is divided into connected components. Symmetry and transitivity ensure that an element is either connected to all other elements in a component or none. This motivates the following definition:

Equivalence classes

For a set $A$ with an equivalence relation $\theta$ , the equivalence class of a is a set including all elements which are in relation with $a$ :

[a]_\theta = \{ b \in A \medspace | \medspace b \thinspace \theta \thinspace a \}

Intuitively, an equivalence relation builds a "complete" connection between the elements in an equivalence class. For example, for the relation $R$ in the picture above we would have:

\begin{align*} [A]_R &= \{ A, B, C \} \\ [D]_R &= \{ D, E \} \\ [F]_R &= \{ F \} \end{align*}

Note that the same equivalence class can have multiple notations. Here $[A]_R = [B]_R$ .

Equivalence classes of an equivalence relation over $A$ form a partition of $A$ :

A partition of a set $A$ is a set $\{ S_i \medspace | \medspace i \in \mathcal{I} \}$ (for some index set $\mathcal{I}$ ) which satisfies two properties:

$S_i \cap S_j = \varnothing$ for $i \neq j$
$\bigcup_{i \in \mathcal{I}} S_i = A$

The sets in a partition are disjunct while "covering" the entire set $A$ . We name the set of all equivalence classes of $\theta$ over $A$ the quotient set of $A$ by $\theta$ and write $A / \theta$ . Since $A / \theta$ is a partition of $A$ , this means that every element of $A$ is contained in exactly one equivalence class.

Partial Order Relations

Hasse Diagrams

Special Elements in Posets

Lattices

Exercises

Verifying Properties

Commutativity of MatricesDifficulty: 2/5Relevance: 🎓🎓Source: Tobias Steinbrecher

Let $\mathbb{R}^{n \times n}$ be the set of all $n \times n$ matrices over the reals. Define a relation $\sim$ on $\mathbb{R}^{n \times n}$ by

A \sim B \iff AB = BA

Prove or disprove the following properties:

$\sim$ is reflexive
$\sim$ is symmetric
$\sim$ is transitive

Less ThanDifficulty: 4/5Relevance: 🎓🎓🎓🎓Source: Yannick Funke and Philipp Barski

For any poset $(A, \leq)$ we can define a relation $<$ on $A$ such that

a < b \iff a \leq b \land a \neq b

Prove that $<$ is irreflexive, antisymmetric, and transitive.

Ad-hoc

Collatz ConjectureSource: Max Obreiter

The Collatz Conjecture (opens in a new tab) states that for any positive integer $x_0 = n$ , the following sequence will eventually reach 1:

x_{n + 1} = \begin{cases} x_n / 2 & \text{if } x_n \text{ is even} \\ 3x_n + 1 & \text{if } x_n \text{ is odd} \end{cases}

Give a formula in predicate logic that is true iff the Collatz Conjecture is true. (Note that predicates are not allowed to be recursive.) The universe should be $U = \mathbb N \setminus \{ 0 \}$ .

Equivalence Relations

Intersection of equivalence relationsSource: Lemma 3.10

Let $\rho$ and $\sigma$ be equivalence relations on a set $A$ . Prove that $\rho \cap \sigma$ is also an equivalence relation on $A$ .

Equivalence Relation on Vector SpacesDifficulty: 3/5Relevance: 🎓Source: Tobias Steinbrecher

Let $V$ be a real vector space, and define a relation $\sim$ on $V$ as follows: For $u, v \in V$ , we say $u \sim v$ if and only if $u - v \in W$ , where $W$ is a subspace of $V$ . Prove that this relation is an equivalence relation.

Lattices

Missing joinDifficulty: 4/5Relevance: 🎓🎓🎓Source: Max Obreiter/GCA Ex. 10.21

Let $(\mathcal F; \preceq)$ be a finite poset with the greatest element $f_\text{max}$ . Show that if every pair of elements has a meet, then $(\mathcal F; \preceq)$ is a lattice, i.e. every pair of elements has a join.

Source: HS24 Geometry: Combinatorics and Algorithms, Chapter 10 Exercise 10.21 (opens in a new tab)

Combinatorics

☕️

Once upon a time, in the mystical land of Lernphase, there came a fateful day when I innocently decided to tackle some "quick exercises" on relations. Easy, right? I'd seen problems like, "How many reflexive relations are there on a set of $n$ elements?" before. Armed with some intuition from graph theory and a sprinkle of combinatorics, I managed to crack it. "Not bad," I thought. "This was actually a fun exercise!" (Feel free to try it below.)

But then I started wondering... What if they ask about symmetric relations? What about transitive ones? What if they combine different properties? Damn! And what about partial order relations or equivalence? That's when things started to spiral. In the spirit of thoroughness, I began constructing this giant table, trying to work out every possible combination myself. I figured I could add the formulas to my cheat sheet later. Little did I know what I was getting into.

I really should have read the Wikipedia article beforehand—because when I got to transitive relations, I was stuck for hours. There was no simple solution in sight. At some point, I thought, "Surely, they won't ask this on the exam.". But something wouldn't let me quit. So, I first shifted to counting partial order relations, thinking they might be easier since they have more structure. Still, I couldn't let go of the problem.

In a last-ditch effort, I started writing brute-force programs to count relations and derived some recurrences that seemed to work. Of course, verifying this recurrence and brute-forcing larger sets wasn't feasible because there were just too many possibilities.

I won't tell you how it ended. You'll have to figure that out yourself! But you'll definitely learn a lot about combinatorics and graphs in the process.

Check out the problems below. The first few are good practice, but if you're feeling adventurous, try the hard ones! Otherwise, skimming the Wikipedia (opens in a new tab) article first might save you some headaches.

Number of relationsSource: Max Obreiter

How many relations are there from a finite set $A$ to a finite set $B$ ?

Number of reflexive relationsSource: Tobias Steinbrecher

How many reflexive relations are there on a set of $n$ elements?

Number of symmetric relations

How many symmetric relations are there on a set of $n$ elements?

Number of Irreflexive Relations

How many irreflexive relations are there on a set of $n$ elements?

Number of antisymmetric relations

How many anti-symmetric relations are there on a set of $n$ elements?

Number of Reflexive and Symmetric Relations

How many relations are both reflexive and symmetric on a set of $n$ elements?

Number of Equivalence RelationsDifficulty: 5/5Relevance: 🪩Source: Tobias Steinbrecher

How many equivalence relations are there on a set of $n$ elements?

Number of transitive relationsDifficulty: 🐉Relevance: 🪩

How many transitive relations are there on a set of $n$ elements?

References

To delve deeper into this topic the Wikipedia Article (opens in a new tab) is actually quite interesting and not bloated with stuff that involves higher-level mathematics.

Sets Functions