Question

A binary relation on a set that is reflexive and symmetric is called a compatible relation. Let A be a set. A cover of A is a set of non-empty subsets of A, say { A_(1,) A_2,A_3……A_n} such that union of A_i's is equal to A. Suggest a way to define a compatible relation on A from a cover of A.

Answer 1

Question 1. A binary relation on a set that is reflexive and symmetric is called a compatible relation. Let $A$ be a set. A cover of $A$ is a set of non-empty subsets of $A$, say $\{A_1, A_2, A_3, \ldots, A_n\}$, such that union of $A_i$'s is equal to $A$. Suggest a way to define a compatible relation on $A$ from a cover of $A$.

Solution. Let $\mathcal{A} = \{A_1, A_2, A_3, \ldots, A_n\}$ be a cover of $A$, so that $A = \bigcup_{i=1}^{n} A_i$. We define a binary relation $\rho_{\mathcal{A}}$ on $A$ as follows:

$$(a, b) \in \rho_{\mathcal{A}} \Leftrightarrow \{a, b\} \subseteq A_i$$

for some $i = 1, \ldots, n$. Let us show that $\rho_{\mathcal{A}}$ is compatible.

Reflexivity. Indeed, since $A = \bigcup_{i=1}^{n} A_i$, then for any $a \in A$ there is $i = 1, \ldots, n$ such that $a \in A_i$. Consequently, $\{a, a\} = \{a\} \subseteq A_i$ and hence $(a, a) \in \rho_{\mathcal{A}}$ by the definition of $\rho_{\mathcal{A}}$.

Symmetry. Take $a, b \in A$ such that $(a, b) \in \rho_{\mathcal{A}}$. We need to show that $(b, a) \in \rho_{\mathcal{A}}$. By definition $\{a, b\} \subseteq A_i$ for some $i = 1, \ldots, n$. But $\{b, a\} = \{a, b\}$, so $\{b, a\} \subseteq A_i$. This exactly means that $(b, a) \in \rho_{\mathcal{A}}$.