Relations

Relations are a structure on a set that pairs any two objects that satisfy certain properties. Examples of familiar relations in this context are 7 is greater than 5, Alice is married to Bob, and 3 \(\clubsuit\) matches 2 \(\clubsuit\). For each of these statements, the elements of a set are related by a statement.

A function is a special kind of relation and derives its meaning from the language of relations.

A (binary) relation \(\Re\) between two sets \(X\) and \(Y\) is a subset of the Cartesian product \( X \times Y.\)

One way to think about this definition is to think of it as that the ordered pairs correspond to the edges in a graph which links the related things.

This graph could be pictured as a relation between the set \(\left \{ A, B, C \right \} \) and the set \(\left \{ X, Y, Z \right \} \).

Every member of a set is related to every member of the other set. So, in roster form, our relation is

\[ \Re = \left \{ (A, X), (A, Y), (A, Z), (B, X), (B, Y), (B, Z), (C, X), (C, Y), (C, Z) \right \}. \]

Notice that something like \((Z,A)\) is not a part of the relation since we defined the relation to be from \(\left \{ A, B, C \right \} \) to \(\left \{ X, Y, Z \right \}. \)

Also, there is no problem with an edge connecting itself, since it is always possible that an object is related to itself. Consider the following:

This definition is also very useful when describing entities in the Cartesian plane, i.e. relations on \(\mathbb{R}.\)

Note: When we have a definition from a set to the same set, we say that the relation is on that set.

The circle above is an illustration of the relation

\[ \Re = \left \{ (x,y) \in \mathbb{R}: x^2 + y^2 = 4^2 \right \}.\]

Finally, we add a logician/computer scientist's definition of a relation.

A relation \(\Re\) is a predicate with (at least) two arguments of arbitrary types \(X\) and \(Y.\) \(_\square\)

While the set-theoretic definition and the logician's definition differ at an abstract level, they practically mean the same.

The same relation which describes the circle could also be interpreted as the following Haskell predicate:

1 2	r :: (Num a, Eq a) => a -> a -> Bool r x y = x^2 + y^2 == 4^2

The usage of \(\sim\) is more popular to denote a relation. Very often, we will say things like \(x \sim y\) to mean that \(x\) is related to \(y\), or according to the set-theoretic definition, \(\left ( x, y \right )\) belong to \(\sim.\)

So far, we have only talked about relations between two objects. Such relations are called binary relations. As you can see, it is not difficult to extend the notion of a relation to an \(n\)-ary relation, where there are n objects involved. However, we will mostly restrict the discussion of relations to binary relations, unless otherwise specified.

An ideal gas follows the ternary relation

\[ P V = nRT .\]

This could be pictured as the following subset of the \( (P,V,T) \) space:

\[ \left \{ \left ( P, V, T \right ) : P V = nRT \right \}. \]

Symmetry, reflexivity, and transitivity are some interesting properties that are possessed by relations defined on elements of the same set.

Symmetry

A relation \(\sim\) on \(A\) is said to be symmetric, if

\[ \forall a,b \in A \quad a\sim b \implies b \sim a.\]

"is married to" is a symmetric relation. Alice is married to Bob implies Bob is married to Alice.

"is older than" isn't symmetric. If Alice is older than Bob, Bob isn't older than Alice.
In fact, this relation is anti-symmetric, meaning that \(A \sim B \implies B \not \sim A .\)

Reflexivity

A relation \( \sim \) on \(A\) is reflexive if

\[ \forall a \in A \quad a \sim a. \]

Equality is a reflexive relation. Everything is equal to itself.

Coprimeness is not reflexive. 1 is coprime to itself. But other integers are not.

Transitivity

A relation \( \sim \) on \(A\) is transitive if

\[ \forall a,b,c \in A \quad \big( (a \sim b ) \wedge (b \sim c ) \big) \implies a \sim c .\]

Divisiblity is transitive. If \(a \mid b\) and \(b \mid c\), then \( a \mid c\).

If friendship was transitive, you wouldn't have the concept of a mutual friend on Facebook.
Alice and Bob are friends. Also, Bob and Carol are friends. But Alice and Carol might not necessarily be friends.

Can you think of relations which are symmetric but not transitive, transitive but not symmetric, symmetric but not reflexive, reflexive and transitive but not symmetric, and so on?

Let \(\Re \subseteq S \times T\) be a binary relation.

The inverse relation \(\Re^{-1}\) is defined as

\[\Re^{-1} \subseteq T \times S: \{(t,s):(s,t) \in \Re \}. \]

Let \(\Re\) be the relation "smaller than" on the real number set, i.e. \(\Re = \{(s,t):s<t,\;\;s,t\in \mathbb R\}.\)

Then \(\Re^{-1}\) is the relation "greater than".

This is because \(s<t \Leftrightarrow t>s\).

\(>\) is also called the dual ordering of \(<\).

Let \(\Re\) be a function.

Then \(\Re^{-1}\) is the inverse function of \(\Re\).

This notation is consistent with the inverse function notation \(f^{-1}\).

Equivalence relations are those relations which are reflexive, symmetric, and transitive at the same time.

Parallelness is an equivalence relation.

• Symmetry: If \(a \parallel b \), then \(b \parallel a.\)
• Reflexivity: All lines are parallel to itself.
• Transitivity: If \(a \parallel b \) and \(b \parallel c\), then \(a \parallel c.\)

Other equivalence relations include the following:

• modular congruence
• equality
• being in the same room
• congruence of triangles.

We define the concept of an equivalence class as follows:

The equivalence class of an element \(a \in A\) under the equivalence relation \( \sim ,\) denoted by \( [a] ,\) is

\[ [a] = \left \{ x \in A \mid x \sim a \right \}.\]

The two triangles on the left are congruent and in the same equivalence class. The other two triangles form two other distinct equivalence classes.

This is what makes the equivalence classes a useful idea:

Any equivalence \(\sim\) on a set \(X\) partitions \(X\) into equivalence classes, and conversely, corresponding to any partition of \(X\), there is an equivalence relation \(\sim\) on \(X.\)

By partition, we mean breaking up the set into disjoint subsets whose union is the set itself.

Consider the equivalence classes \([i]\) formed by the relation \(\sim\) on \(X.\)

• Since by reflexivity \(i \in [i]\ \forall i\), the union of all the equivalence classes are \(S.\)
• They are disjoint because if \(x \in [a]\) and \(x \in [b],\) then \(x \sim a\) by definition, and by symmetry, \(a \sim x\). Also, \(x \sim b\) by definition. But then \(a \sim b\) by transitivity, so \(a\in [b]\). Every \(y \in [a]\) is also in \([b]\) again by transitivity. This means that \([a]\subseteq [b]\). Swapping \(a\) and \(b\), proceeding in the same way, we conclude \([a]=[b]\). \(_\square\)

---

Conversely, given any partitioning scheme, we could define \(\sim\) as \(a \sim b\) if and only if \(a\) and \(b\) belong to the same set.

• Reflexivity: All elements belong to the set in which they belong. So, \(a \sim a.\)
• Symmetry: \(a \sim b \implies b \sim a \) since what this means is that \(a\) and \(b\) are essentially in the same set.
• Transitivity: \( (a \sim b) \wedge (b \sim c) \implies ( a \sim c ) \), since once again \(a, b, c\) are all in the same set. \(_\square\)

See order theory

Orderings are different from equivalences in that they are (mostly) antisymmetric.

Partial Ordering

A (non-strict) partial order is a relation \(\preceq \) defined on a set \(S\) which satisfies the following \( \forall a, b, c \in S\):

• Reflexivity: \(a \preceq a\)
• Antisymmetry: \((a \preceq b) \wedge (b \preceq a) \implies a = b\)
• Transitivity: \((a \preceq b) \wedge (b \preceq c) \implies (a \preceq c).\)

Here, we say non-strict, since we allow reflexivity.

A set equipped with a partial ordering is called a partially-ordered set or a poset.

Divisibility of positive integers forms posets. This is a Hasse diagram, a representation for posets. If you choose any walk on this graph, each number is divisible by the number before it.

Notice that not all pairs of elements are related, though. This is why we say the ordering is partial.

A different example would be the vertices of a directed acyclic graph ordered by reachability.

To illustrate, \(7 \preceq 11 \preceq 10\) and \(11 \preceq 9.\)

Total Order

We define the notion of totality of a relation as follows:

A relation \(\sim \) defined on a set \(X\) is total if \(\forall a, b \in X\), either \(a \sim b\) or \(b \sim a.\)

A total order is simply a partial order which also satisfies totality.

• The set of words in a dictionary equipped with a lexicographic ordering
• \(\mathbb{N}\) equipped with \(\leq\)
• People standing in a queue, equipped with their position in the queue

How many total orderings of a set consisting of \(n\) elements are there?

Relations are a structure on a set that pairs any two objects that satisfy certain properties. Examples of familiar relations in this context are 7 is greater than 5, Alice is married to Bob, and 3 \(\clubsuit\) matches 2 \(\clubsuit\). For each of these statements, the elements of a set are related by a statement.

See Function Terminology

A special case of relations are functions.

A function \(f\) from \(X\) to \(Y\), denoted

\[f : X \to Y,\]

is a relation between \(X\) to \(Y\) such that for every element \(x \in X\) (called pre-image), there exists exactly one \(y \in Y\) (called image) which is related to \(x\).

\(X\) and \(Y\) are called the domain and co-domain of \(f,\) respectively.

When we say \(f(x) = y\), we mean \((x,y) \in f\). A metaphorical description of a function could be a black-box or a machine that takes in an input and returns a corresponding output.

Function

A function mapping objects to their colors

A depiction of a function on a Cartesian plane

Not all relations are functions.

For example, the relation

\[ \Re = \left \{ (x,y) \in \mathbb{R}: x^2 + y^2 = 4^2 \right \}\]

is not a function since there are multiple values of \(y\) possible for each \(x\).

The definition of a function requires us to have exactly one image for each pre-image.

This is why the inverse of a function is not necessarily a function. For example, the inverse of \( x \mapsto x^2 \) is not a function.

When a student is first introduced to the notion of a function, he tends to believe that a function is an algorithm being run upon the image. However, this is not so. There is no constraint of computability imposed on the notion of a function.

They are just arbitrary mappings. It is perfectly possible that a function is non-computable. Popular examples include a function which could tell if a program halts (halting problem) or the minimum length of a program that outputs a given string (Kolmogorov complexity).