Binary Relations

Binary Relation

We begin with the definition. The following definition is nothing particularly special; it simply names the set of ordered pairs that arose in the course of explaining why ordered pairs need to be introduced in §Ordered Pairs.

Definition 1 A set \(R\) is called a binary relation if every element of \(R\) is an ordered pair.¹

Consequently, the equality (\(=\)) defined between sets cannot be regarded as a binary relation.

Example 2 If \(=\) between sets were a binary relation, then the set

\[E=\{(A,A)\mid\text{$A$ any set}\}\]

representing it would exist. That is, \(E\) would have to be the product of two universal sets.

If the product of two universal sets exists, then by the proposition below, a universal set must also exist, contradicting §ZFC Axioms, ⁋Example 4. Hence \(=\) defined between all sets cannot be a binary relation.

Proposition 3 Let \(R\) be a binary relation. Then there exist unique sets \(A\) and \(B\) such that:

• $x\in A$ is equivalent to there exists some $y$ such that $(x,y)\in R$, and
• $y\in B$ is equivalent to there exists some $x$ such that $(x,y)\in R$.

Proof

Let \(R\) be a binary relation and consider \(\bigcup(\bigcup R)\). A calculation shows that \((x,y)\in R\implies x,y\in\bigcup(\bigcup R))\). Define \(P\) as

\(P(t)\): There exists some \(s\) such that \((s,t)\in R\).

We then obtain the set

\[A=\left\{x\mid\left(x\in\bigcup\left(\bigcup R\right)\right)\wedge P(x)\right\}\]

Thus the first claim is established. Similarly, defining property \(Q\) as

\(Q(s)\): There exists some \(t\) such that \((s,t)\in R\).

yields set \(B\).

As in §Ordered Pairs, ⁋Definition 7, these are called the first and second projections respectively, and are denoted by \(\pr_1R\) and \(\pr_2R\).

At times it becomes necessary to specify which sets the first and second components of a binary relation belong to. For this purpose, given two sets \(A,B\) and a binary relation \(R\) satisfying \(\pr_1R\subseteq A\) and \(\pr_2R\subseteq B\), we may regard it as a triple \((R,A,B)\). In this case, \(A\) is called the source of \(R\), and \(B\) is called the target of \(R\). Under such circumstances, even for the same set \(R\), the triples \((R,A,B)\) and \((R,A',B')\) are regarded as distinct.

Remark Let \(R\) be a binary relation satisfying the conditions \(\pr_1R\subseteq A\) and \(\pr_2R\subseteq B\). By §Ordered Pairs, ⁋Proposition 9,

\[R\subseteq \pr_1 R\times\pr_2R\subseteq A\times B\]

Hence the Cartesian product \(A\times B\) may be described as the largest among all binary relations having \(A\) as source and \(B\) as target.

Domain and Image of a Binary Relation

Definition 5 Let \((R,A,B)\) be a binary relation and let \(A'\subseteq A\). The image of \(A'\) under \(R\), denoted by \(R(A')\), is the set of all elements related to elements of \(A'\) by \(R\).

Expressed as a formula, the above definition reads:

\[R(A')=\bigcup_{x\in A'} \{y\in B\mid(x,y)\in R\}\]

Strictly speaking, without the target \(B\) of the binary relation \(R\) being specified, the set on the right-hand side \(\{y\in B\mid(x,y)\in R\}\) would take the form

\[\{y\mid(x,y)\in R\}\]

Unlike the set above, whose existence is guaranteed by the comprehension schema, this set may fail to exist.

Such issues must always be borne in mind when studying set theory. However, since our aim is not to study set theory for its own sake, but rather to prove propositions useful elsewhere, we shall pass over such minor notational matters without further comment.

Proposition 6 Let \(R\) be a binary relation, and let \(A\) be any set with subset \(X\). Then \(R(X)\subseteq R(A)\).

Proof

Let \(y\in R(X)\). Then there exists some \(x\in X\) such that \((x,y)\in R(X)\). Since \(X\subseteq A\), we have \(x\in A\), and hence \(y\in R(A)\).

By the proposition above, for any \(A\),

\[R(A)=\pr_2\{z\in R\mid\text{$\pr_1z\in A$}\}\subset\pr_2R\]

and therefore \(R(A)\subset\pr_2R\). In particular, if \(A=\emptyset\), then \(R(A)=\emptyset\). More generally, if \(A\cap\pr_1R=\emptyset\), then \(R(A)=\emptyset\).

If \(A=\{x\}\) for some \(x\), then \(R(A)\) may be regarded as the value of \(R\) at \(x\), analogous to a function value.

Definition 7 For a binary relation \(R\), the set \(R(\{x\})\) is called the section of \(R\) at \(x\).

This set is sometimes denoted by \(R(x)\), treating it as the value of \(R\) at \(x\). This function value need not be unique, and consequently \(R(x)\) may contain multiple elements.

---

References

[HJJ] K. Hrbacek, T.J. Jeck, and T. Jech. Introduction to Set Theory. Lecture Notes in Pure and Applied Mathematics. M. Dekker, 1978.
[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

---

1. In [Bou], such a set is called a graph, and a distinction is drawn between binary relations that have graphs and those that do not. Since this is not a common convention, we follow [HJJ] and adopt the definition above. In this case, the meaning of the word “relation” becomes somewhat ambiguous, but we shall not define it separately. ↩