Bài tập 11, § 6

(a) Cho $\mathrm{R}\{x,\ y\}$ là một quan hệ phản xạ và đối xứng trên một tập hợp E. Ta nói R là không bắc cầu bậc 1 nếu với mọi bốn phần tử phân biệt $x$, $y$, $z$, $t$ của E, các quan hệ $\mathrm{R}\{x,\ y\}$, $\mathrm{R}\{x,\ z\}$, $\mathrm{R}\{x,\ t\}$, $\mathrm{R}\{\ y,\ z\}$, và $\mathrm{R}\{\ y,\ t\}$ kéo theo $\mathrm{R}\{z,\ t\}$. Một tập con A của E được gọi là ổn định đối với quan hệ R nếu $\mathrm{R}\{x,\ y\}$ với mọi $x$ và $y$ trong A. Nếu $a$ và $b$ là hai phần tử phân biệt của E sao cho $\mathrm{R}\{a,\ b\}$, hãy chứng minh rằng tập $\mathrm{C}(a,\ b)$ gồm các phần tử $x \in \mathrm{E}$ sao cho $\mathrm{R}\{a,\ x\}$ và $\mathrm{R}\{b,\ x\}$ là ổn định và rằng

với mỗi cặp phần tử phân biệt $x$, $y$ của $\mathrm{C}(a,\ b)$. Các tập hợp $\mathrm{C}(a,\ b)$ (với mỗi cặp có thứ tự $(a,\ b)$ sao cho $\mathrm{R}\{a,\ b\}$) và các thành phần liên thông (Bài tập 10) đối với R chỉ gồm một phần tử được gọi là các cấu tử của E đối với quan hệ R. Chứng minh rằng giao của hai cấu tử phân biệt của E chứa nhiều nhất một phần tử và rằng nếu A, B, C là ba cấu tử đôi một phân biệt thì ít nhất một trong các tập hợp $\mathrm{A} \cap \mathrm{B}$, $\mathrm{B} \cap \mathrm{C}$, $\mathrm{C} \cap \mathrm{A}$ là rỗng.

(b) Ngược lại, cho $(\mathrm{X}_\lambda)_{\lambda \in \mathrm{L}}$ là một phủ của một tập hợp E gồm các tập con không rỗng của E và có các tính chất sau đây: (1) nếu $\lambda$, $\mu$ là hai chỉ số phân biệt, thì $\mathrm{X}_\lambda \cap \mathrm{X}_\mu$ chứa nhiều nhất một phần tử; (2) nếu $\lambda$, $\mu$, $\nu$ là ba chỉ số phân biệt, thì ít nhất một trong ba tập hợp $\mathrm{X}_\lambda \cap \mathrm{X}_\mu$, $\mathrm{X}_\mu \cap \mathrm{X}_\nu$, $\mathrm{X}_\nu \cap \mathrm{X}_\lambda$ là rỗng. Cho $\mathrm{R}\{x,\ y\}$ là quan hệ "tồn tại $\lambda \in \mathrm{L}$ sao cho $x \in \mathrm{X}_\lambda$ và $y \in \mathrm{X}_\lambda$"; hãy chỉ ra rằng R phản xạ trên E, đối xứng và không bắc cầu bậc 1, và rằng các $\mathrm{X}_\lambda$ là các thành phần của E đối với R.

(c) \* Tương tự, một quan hệ $\mathrm{R}\{x,\ y\}$ phản xạ và đối xứng trên E được gọi là không bắc cầu thứ tự $n - 3$ nếu, với mọi họ $(x_i)_{1 \leqslant i \leqslant n}$ gồm các phần tử phân biệt của E, các quan hệ $\mathrm{R}\{x_i,\ x_j\}$ đối với mỗi cặp $(i,\ j) \neq (n - 1,\ n)$ kéo theo $\mathrm{R}\{x_{n-1},\ x_n\}$. Hãy khái quát hóa các kết quả của (a) và (b) cho các quan hệ không bắc cầu có thứ tự tùy ý. Chứng minh rằng một quan hệ không bắc cầu thứ tự $p$ cũng không bắc cầu thứ tự $q$ với mọi $q > p$. \*