Exercise 11, § 6

(a) Let $\mathrm{R}\{x,\ y\}$ be a reflexive and symmetric relation on a set E. R is said to be intransitive of order 1 if for any four distinct elements $x$, $y$, $z$, $t$ of E the relations $\mathrm{R}\{x,\ y\}$, $\mathrm{R}\{x,\ z\}$, $\mathrm{R}\{x,\ t\}$, $\mathrm{R}\{\ y,\ z\}$, and $\mathrm{R}\{\ y,\ t\}$ imply $\mathrm{R}\{z,\ t\}$. A subset A of E is said to be stable with respect to the relation R if $\mathrm{R}\{x,\ y\}$ for all $x$ and $y$ in A. If $a$ and $b$ are two distinct elements of E such that $\mathrm{R}\{a,\ b\}$, show that the set $\mathrm{C}(a,\ b)$ of elements $x \in \mathrm{E}$ such that $\mathrm{R}\{a,\ x\}$ and $\mathrm{R}\{b,\ x\}$ is stable and that

for each pair of distinct elements $x$, $y$ of $\mathrm{C}(a,\ b)$. The sets $\mathrm{C}(a,\ b)$ (for each ordered pair $(a,\ b)$ such that $\mathrm{R}\{a,\ b\}$) and the connected components (Exercise 10) with respect to R which consist of a single element are called the constituents of E with respect to the relation R. Show that the intersection of two distinct constituents of E contains at most one element and that if A, B, C are three mutually distinct constituents, at least one of the sets $\mathrm{A} \cap \mathrm{B}$, $\mathrm{B} \cap \mathrm{C}$, $\mathrm{C} \cap \mathrm{A}$ is empty.

(b) Conversely, let $(\mathrm{X}_\lambda)_{\lambda \in \mathrm{L}}$ be a covering of a set E consisting of non-empty subsets of E and having the following properties : (1) if $\lambda$, $\mu$ are two distinct indices, $\mathrm{X}_\lambda \cap \mathrm{X}_\mu$ contains at most one element; (2) if $\lambda$, $\mu$, $\nu$ are three distinct indices, then at least one of the three sets $\mathrm{X}_\lambda \cap \mathrm{X}_\mu$, $\mathrm{X}_\mu \cap \mathrm{X}_\nu$, $\mathrm{X}_\nu \cap \mathrm{X}_\lambda$ is empty. Let $\mathrm{R}\{x,\ y\}$ be the relation "there exists $\lambda \in \mathrm{L}$ such that $x \in \mathrm{X}_\lambda$ and $y \in \mathrm{X}_\lambda$"; show that R is reflexive on E, symmetric and intransitive of order 1, and that the $\mathrm{X}_\lambda$ are the constituents of E with respect to R.

(c) \* Similarly, a relation $\mathrm{R}\{x,\ y\}$ which is reflexive and symmetric on E is said to be intransitive of order $n - 3$ if, for every family $(x_i)_{1 \leqslant i \leqslant n}$ of distinct elements of E, the relations $\mathrm{R}\{x_i,\ x_j\}$ for each pair $(i,\ j) \neq (n - 1,\ n)$ imply $\mathrm{R}\{x_{n-1},\ x_n\}$. Generalize the results of (a) and (b) to intransitive relations of arbitrary order. Show that a relation which is intransitive of order $p$ is also intransitive of order $q$ for all $q > p$. \*