# Relations Relations {cite}`wiki:relation` 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: $$ X \times X = \{ (a, b) \ST a \in X \text{ and } b \in X \}. $$ In other words, $X \times X$ is the collection of all possible ordered pairs of elements of $X$. ```{index} Relation; binary ``` ````{prf:definition} Binary relation :label: def-st-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*. ```` ## Types of relations ```{index} Relation; injective ``` ```{prf:definition} Injective relation :label: def-st-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. ```{index} Relation; functional ``` ```{prf:definition} Functional relation :label: def-st-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. ```{index} Relation; one-to-one ``` ```{prf:definition} One-to-one relation :label: def-st-one-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. ```{index} Relation; one-to-many ``` ```{prf:definition} One-to-many relation :label: def-st-one-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. ```{index} Relation; many-to-one ``` ```{prf:definition} Many-to-one relation :label: def-st-many-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. ```{index} Relation; many-to-many ``` ```{prf:definition} Many-to-many relation :label: def-st-many-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. ```{index} Relation; serial ``` ```{prf:definition} Serial relation :label: def-st-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. ```{index} Relation; surjective ``` ```{prf:definition} Surjective relation :label: def-st-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. ## Operations on Relations Let $R$ and $S$ be relations over sets $X$ and $Y$. ```{index} Relation; union ``` ```{prf:definition} Union of relations :label: def-st-relation-union $$ R \cup S = \{(x, y) \ST x R y \text{ or } x S y\}. $$ ``` ```{index} Relation; intersection ``` ```{prf:definition} Intersection of relations :label: def-st-relation-intersection $$ R \cap S = \{(x, y) \ST x R y \text{ and } x S y\}. $$ ``` ```{index} Relation; composition ``` ```{prf:definition} Composition of relations :label: def-st-relation-composition Let $R : X \to Y$ and $S : Y \to Z$ be two relations. Then, there composition is defined as: $$ S \circ R \triangleq \{ (x,z) \in X \times Z \ST \text{ there exists } y \in Y \text{ such that } x R y \text{ and } y R z \}. $$ ``` ## Equivalence Relations An interesting type of relations are equivalence relations over a set $X$. ```{index} Equivalence relation ``` ````{prf:definition} Equivalence relation :label: def-st-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. ```{index} Equivalence class ``` ````{prf:definition} Equivalence class :label: def-st-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 $$ [x] = \{ y \in X \ST x \mathcal{R} y\} $$ i.e. all elements in $X$ which are related to $x$. ```` We can now look at some properties of equivalence classes and relations. ````{prf:proposition} :label: res-st-eq-class-identical-disjoint Any two equivalence classes are either disjoint or else they coincide. ```` ````{prf:example} Equivalent classes :label: ex-st-eq-class-1 Let $X$ bet the set of integers $\ZZ$. Let $\mathcal{R}$ be defined as $$ x \mathcal{R} y \iff 2 \mid (x-y) $$ 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. ```` ````{prf:proposition} :label: res-st-family-eq-classes-union-set 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$. ```` ```{index} Set partition, Partition; set ``` ````{prf:definition} Partition :label: def-st-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. $$ X = \cup_{i \in I} A_i $$ 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. ````{prf:proposition} :label: res-st-partition-induces-eq-class-relation 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 $$ \mathcal{R} = \{(x,y) \in X \times X \ST \exists \; i \in I \text{ such that } x, y \in A_i\} $$ 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$. ## Order Another important type of relation is an order relation over a set $X$. ```{index} Partial order ``` ````{prf:definition} Partial order :label: def-st-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$. ```{index} Partially ordered set ``` ````{prf:definition} Partially ordered set :label: def-st-partially-ordered-set A set equipped with a partial order is known as a *partially ordered set* (a.k.a *poset*). ```` ````{prf:example} Partially ordered set :label: ex-st-poset-1 Consider a set $A = \{1,2,3\}$. Consider the power set of $A$ which is $$ X = \{\EmptySet, \{1\}, \{2\}, \{3\}, \{1,2\} , \{2,3\} , \{1,3\}, \{1,2,3\} \}. $$ 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. ```{index} Chain ``` ````{prf:definition} Chain :label: def-st-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. ````{prf:example} Chain :label: ex-st-poset-chain Continuing from previous example consider a subset $Y$ of $X$ defined by $$ Y = \{\EmptySet, \{1\}, \{1,2\}, \{1,2,3\} \}. $$ 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$. ```` ```{index} Total order ``` ```{prf:definition} Total order :label: def-st-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). ``` ```{index} Totally ordered set ``` ```{prf:definition} Totally ordered set :label: def-st-totally-ordered-set A set equipped with a total order is known as a *totally ordered set*. ``` ````{prf:example} More ordered sets :label: ex-st-ordered-sets-2 * 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. ```` ### Upper Bounds We can now define the notion of upper bounds in a partially ordered set. ```{index} Partial order; upper bound ``` ````{prf:definition} Upper bound :label: def-st-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. ```{index} Partial order; maximal element ``` ````{prf:definition} Maximal element :label: def-st-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. ````{prf:example} Maximal elements :label: ex-st-maximal-elements-1 Consider the following set $$ Z = \{\EmptySet, \{1\}, \{2\}, \{3\}, \{1,2\} , \{2,3\} , \{1,3\} \}. $$ 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\}$. ```` ````{prf:example} Ordered sets without a maximal element :label: ex-st-ordered-set-no-max-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. ````{prf:proposition} :label: res-st-chain-upper-bound-implies-max-element If a {prf:ref}`chain ` in a partially ordered set $X$ has an upper bound in $X$, then $X$ has a maximal element. ```` ### Lower Bounds Following is corresponding notion of lower bounds. ```{index} Partial order; lower bound ``` ````{prf:definition} Lower bound :label: def-st-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$. ```` ```{index} Partial order; minimal element ``` ````{prf:definition} Minimal element :label: def-st-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.