Bourbaki exercise on intransitive relations

225 Views Asked by At

This is Exercise II.6.11 of Bourbaki's Theory of sets (or II.6.10 in the newer edition).

Its intention is to generalize the correspondence between equivalence relations and partitions.

Given a symmetric and reflexive relation $R$ in a set $X$:

1) A connected component of $R$ is an equivalence class of the smallest equivalence relation containing $R$.

2) $R$ is said intransitive of order 1 iff for any distinct elements $x$, $y$, $z$, $w$ of $X$, if $xRy$, $xRz$, $xRw$, $yRz$, $yRw$, then $zRw$.

3) For distinct elements $a$ and $b$ of $X$ such that $aRb$, we define $C(a,b)=\{x\in X:(aRx\wedge bRx)\}$.

4) A constituent of $R$ is a set in the form $C(a,b)$ or a connected component that consists of a single element.

Then here are the questions:

a) Show that the intersection of two distinct constituents of $R$ has at most one element, and for distinct constituents $A$, $B$, $C$, at least one of $A\cap B$, $A\cap C$, $B\cap C$ is empty, or these three are equal. Moreover, the constituents are nonempty, and cover $X$, and for $x,y\in X$, then $xRy$ iff there is a constituent $A$ such that $\{x,y\}\subseteq A$.

b) Conversely, let $(U_i)_{i\in I}$ be a covering of $X$ by nonempty sets, such that for distinct indices $i$, $j$, then $U_i\cap U_j$ has at most one element, and for distinct indices $i$, $j$, $k$, at least one of $U_i\cap U_j$, $U_i\cap U_k$, $U_j\cap U_k$ is empty, or these three are equal. Let $R=\{\langle x,y\rangle\in X\times X:\exists i\in I:\{x,y\}\subseteq U_i\}$. Show that $R$ is symmetric and reflexive in $X$ and intransitive of order 1, and that the $U_i$ are the constituents of $R$.

This is how the exercise was written. I was able to do (a) and to prove that the relation in (b) is symmetric and reflexive in $X$ and intransitive of order 1. However, I think I found some error in (b), for I thought about the example $X=\{0,1,2\}$, with $U_0=\{0\}$, $U_1=\{0,1\}$, $U_2=\{0,2\}$, that satisfies the initial conditions of the question, but the set $U_0$ is not a constituent of $R$. I really do not know how to correct the exercise so that such relations and coverings be in correspondence, or, if any, what error I have done.

1

There are 1 best solutions below

1
On BEST ANSWER

An even easier counterexample is $E = \{x, y\}$ where $x$ and $y$ are distinct, $X_{1} = \{x, y\}$ and $X_{2} = \{x\}$. Then $X_{2}$ is not a constituent of the relation $R$ for $E$.

To fix this, after "or these three are equal.", add the condition "For two distinct indices $\lambda$, $\mu$, $X_{\lambda}$ is not a subset of $X_{\mu}$."