Relations
Contents
1.3. Relations#
Relations [89] between two sets \(X\) and \(Y\) are subsets of the Cartesian product of two sets \(X \times Y\).
Relations on a set \(X\) are subsets of the Cartesian product \(X \times X\). We recall:
In other words, \(X \times X\) is the collection of all possible ordered pairs of elements of \(X\).
Definition 1.23 (Binary relation)
Given sets \(X\) and \(Y\), a binary relation over sets \(X\) and \(Y\) is defined as a subset \(\RRR\) of the Cartesian product \(X \times Y\).
If \((x,y) \in \RRR\) then \(x\) is said to be in relation \(\RRR\) with \(y\). This is denoted by \(x \RRR y\).
\(X\) is called the domain or set of departure of \(\RRR\) and \(Y\) is called the codomain or set of destination of \(\RRR\).
A binary relation on a set \(X\) is defined as a subset of \(X \times X\). It is also known as a homogeneous relation.
When \(X \neq Y\), then the relation is called a heterogeneous relation.
1.3.1. Types of relations#
Definition 1.24 (Injective relation)
A relation \(\RRR : X \to Y\) is called injective if \(x \RRR y\) and \(z \RRR y\) implies \(x = z\). In other words, for each \(y \in Y\), there is at-most one \(x \in X\) such that \(x \RRR y\).
If \(X\) is the set of men, \(Y\) is the set of women and \(\RRR\) is the relation of marriage, then we are saying that each woman can have at most one husband.
A man may have multiple wives. Some men or women may be unmarried too.
Definition 1.25 (Functional relation)
A relation \(\RRR : X \to Y\) is called functional if \(x \RRR y\) and \(x \RRR z\) implies \(y = z\). In other words, for each \(x \in X\), there is at-most one \(y \in Y\) such that \(x \RRR y\). Such binary relations are also called partial functions.
We are saying that each man can have at most one wife.
A woman may have multiple husbands. Some men or women may be unmarried too.
Definition 1.26 (One-to-one relation)
A relation is called one-to-one if it is injective and functional.
We are saying that each woman can have at most one husband and each man can have at most one wife.
Some men or women may still be unmarried.
Definition 1.27 (One-to-many relation)
A relation is called one-to-many if it is injective but not functional.
While each woman has at most one husband, there are some men who have multiple wives.
Some men or women may still be unmarried.
Definition 1.28 (Many-to-one relation)
A relation is called many-to-one if it is functional but not injective.
While each man can have at most one wife, there are women who have multiple husbands.
Some men or women may still be unmarried.
Definition 1.29 (Many-to-many relation)
A relation is called many-to-many if it is neither injective nor functional.
No spouse, one spouse, multiple spouses, all are permitted.
Definition 1.30 (Serial relation)
A relation \(\RRR : X \to Y\) is called serial if for every \(x \in X\) there exists at least one \(y\in Y\) such that \(x \RRR y\).
Every man has at least one wife.
Some women may still be unmarried.
Definition 1.31 (Surjective relation)
A relation \(\RRR : X \to Y\) is called surjective if for every \(y \in Y\) there exists at least one \(x\in X\) such that \(x \RRR y\).
Every woman has at least one husband.
Some men may still be unmarried.
1.3.2. Operations on Relations#
Let \(R\) and \(S\) be relations over sets \(X\) and \(Y\).
Definition 1.32 (Union of relations)
Definition 1.33 (Intersection of relations)
Definition 1.34 (Composition of relations)
Let \(R : X \to Y\) and \(S : Y \to Z\) be two relations. Then, there composition is defined as:
1.3.3. Equivalence Relations#
An interesting type of relations are equivalence relations over a set \(X\).
Definition 1.35 (Equivalence relation)
A relation \(\mathcal{R}\) on a set \(X\) is said to be an equivalence relation if it satisfies the following properties:
\(x \mathcal{R} x\) for each \(x \in X\) (reflexivity).
If \(x \mathcal{R} y\) then \(y \mathcal{R} x\) (symmetry).
If \(x \mathcal{R} y\) and \(y \mathcal{R} z\) then \(x \mathcal{R} z\) (transitivity).
We can now introduce equivalence classes on a set.
Definition 1.36 (Equivalence class)
Let \(\mathcal{R}\) be an equivalence relation on a set \(X\). Then the equivalence class determined by the element \(x \in X\) is denoted by \([x]\) and is defined as
i.e. all elements in \(X\) which are related to \(x\).
We can now look at some properties of equivalence classes and relations.
Proposition 1.3
Any two equivalence classes are either disjoint or else they coincide.
Example 1.4 (Equivalent classes)
Let \(X\) bet the set of integers \(\ZZ\). Let \(\mathcal{R}\) be defined as
i.e. \(x\) and \(y\) are related if the difference of \(x\) and \(y\) given by \(x-y\) is divisible by \(2\).
Clearly, the set of odd integers and the set of even integers forms two disjoint equivalent classes.
Proposition 1.4
Let \(\mathcal{R}\) be an equivalence relation on a set \(X\). Since \(x \in [x]\) for each \(x \in X\), there exists a family \(\{A_i\}_{i \in I}\) of pairwise disjoint sets (a family of equivalence classes) such that \(X = \cup_{i \in I} A_i\).
Definition 1.37 (Partition)
If a set \(X\) can be represented as a union of a family \(\{A_i\}_{i \in I}\) of pairwise disjoint sets i.e.
then we say that \(\{A_i\}_{i \in I}\) is a partition of \(X\).
A partition over a set \(X\) also defines an equivalence relation on it.
Proposition 1.5
If there exists a family \(\{A_i\}_{i \in I}\) of pairwise disjoint sets which partitions a set \(X\), (i.e. \(X = \cup_{i \in I} A_i \)), then by letting
an equivalence relation is defined on \(X\) whose equivalence classes are precisely the sets \(A_i\).
In words, the relation \(\mathcal{R}\) includes only those tuples \((x,y)\) from the Cartesian product \(X\times X\) for which there exists one set \(A_i\) in the family of sets \(\{A_i\}\) such that both \(x\) and \(y\) belong to \(A_i\).
1.3.4. Order#
Another important type of relation is an order relation over a set \(X\).
Definition 1.38 (Partial order)
A relation, denoted by \(\leq\), on a set \(X\) is said to be a partial order for \(X\) (or that \(X\) is partially ordered by \(\leq\)) if it satisfies the following properties:
\(x \leq x\) holds for every \(x \in X\) (reflexivity).
If \(x \leq y\) and \(y \leq x\), then \(x = y\) (antisymmetry).
If \(x \leq y\) and \(y \leq z\), then \(x \leq z\) (transitivity).
An alternative notation for \(x \leq y\) is \(y \geq x\).
Definition 1.39 (Partially ordered set)
A set equipped with a partial order is known as a partially ordered set (a.k.a poset).
Example 1.5 (Partially ordered set)
Consider a set \(A = \{1,2,3\}\). Consider the power set of \(A\) which is
Define a relation \(\mathcal{R}\) on \(X\) such that \(x \mathcal{R} y\) if \(x \subseteq y\).
Clearly
\(x \subseteq x \quad \forall x \in X\).
If \(x \subseteq y\) and \(y \subseteq x\) then \(x =y\).
If \(x \subseteq y\) and \(y \subseteq z\) then \(x \subseteq y\).
Thus the relation \(\mathcal{R}\) defines a partial order on the power set \(X\).
We can look at how elements are ordered within a set a bit more closely.
Definition 1.40 (Chain)
A subset \(Y\) of a partially ordered set \(X\) is called a chain if for every \(x, y \in Y\) either \(x \leq y\) or \(y \leq x\) holds.
A chain is also known as totally ordered.
In a partially ordered set \(X\), we don’t require that for every \(x,y \in X\), either \(x \leq y\) or \( y \leq x\) should hold. Thus there could be elements which are not connected by the order relation.
In a totally ordered set \(Y\), for every \(x,y \in Y\) we require that either \(x \leq y\) or \(y \leq x\) holds.
If a set is totally ordered, then it is partially ordered also.
Example 1.6 (Chain)
Continuing from previous example consider a subset \(Y\) of \(X\) defined by
Clearly, for every \(x, y \in Y\), either \(x \subseteq y\) or \(y \subseteq x\) holds.
Hence \(Y\) is a chain or a totally ordered set within \(X\).
Definition 1.41 (Total order)
A relation, denoted by \(\leq\), on a set \(X\) is said to be a total order for \(X\) (or that \(X\) is totally ordered by \(\leq\)) if it satisfies the following properties:
\(x \leq x\) holds for every \(x \in X\) (reflexivity).
If \(x \leq y\) and \(y \leq x\), then \(x = y\) (antisymmetry).
If \(x \leq y\) and \(y \leq z\), then \(x \leq z\) (transitivity).
\(x \leq y\) or \(y \leq x\) holds for every \(x, y \in X\) (strongly connected).
Definition 1.42 (Totally ordered set)
A set equipped with a total order is known as a totally ordered set.
Example 1.7 (More ordered sets)
The set of natural numbers \(\Nat\) is totally ordered.
The set of integers \(\ZZ\) is totally ordered.
The set of real numbers \(\RR\) is totally ordered.
Suppose we define an order relation in the set of complex numbers as follows. Let \(x+jy\) and \(u+jv\) be two complex numbers. We say that
\[ x+jy \leq u+jv \iff x \leq u \text{ and } y \leq v. \]With this definition, the set of complex numbers \(\CC\) is partially ordered.
\(\RR\) is a totally ordered subset of \(\CC\) since the imaginary component is 0 for all real numbers in the complex plane.
In fact, any line or a ray or a line segment in the complex plane represents a totally ordered set in the complex plane.
1.3.4.1. Upper Bounds#
We can now define the notion of upper bounds in a partially ordered set.
Definition 1.43 (Upper bound)
If \(Y\) is a subset of a partially ordered set \(X\) such that \(y \leq u\) holds for all \(y \in Y\) and for some \(u \in X\), then \(u\) is called an upper bound of \(Y\).
Note that there can be more than one upper bounds of \(Y\). Upper bound is not required to be unique.
Definition 1.44 (Maximal element)
An element \(m \in X\) is called a maximal element whenever the relation \(m \leq x\) implies \(x = m\).
This means that there is no other element in \(X\) which is greater than \(m\).
A maximal element need not be unique. A partially ordered set may contain more than one maximal element.
Example 1.8 (Maximal elements)
Consider the following set
The set is partially ordered w.r.t. the relation \(\subseteq\).
There are three maximal elements in this set namely \(\{1,2\} , \{2,3\} , \{1,3\}\).
Example 1.9 (Ordered sets without a maximal element)
The set of natural numbers \(\Nat\) has no maximal element.
What are the conditions under which a maximal element is guaranteed in a partially ordered set \(X\)?
Following statement known as Zorn’s lemma guarantees the existence of maximal elements in certain partially ordered sets.
Proposition 1.6
If a chain in a partially ordered set \(X\) has an upper bound in \(X\), then \(X\) has a maximal element.
1.3.4.2. Lower Bounds#
Following is corresponding notion of lower bounds.
Definition 1.45 (Lower bound)
If \(Y\) is a subset of a partially ordered set \(X\) such that \(u \leq y\) holds for all \(y \in Y\) and for some \(u \in X\), then \(u\) is called an lower bound of \(Y\).
Definition 1.46 (Minimal element)
An element \(m \in X\) is called a minimal element whenever the relation \(x \leq m\) implies \(x = m\).
As before there can be more than one minimal elements in a set.