Bài tập 10, § 6

(a) Nếu $R\{x, y\}$ là một quan hệ bất kỳ, thì "$R\{x, y\}$ và $R\{y, x\}$" là một quan hệ đối xứng. Dưới điều kiện nào thì quan hệ đó phản xạ trên tập hợp $E$?

*(b) Cho $R\{x, y\}$ là một quan hệ phản xạ và đối xứng trên một tập hợp $E$. Cho $S\{x, y\}$ là quan hệ "tồn tại một số nguyên $n > 0$ và một dãy $(x_i)_{0 \leqslant i \leqslant n}$ gồm các phần tử của $E$ sao cho $x_0 = x$, $x_n = y$, và với mỗi chỉ số $i$ thỏa mãn $0 \leqslant i < n$, $R\{x_i, x_{i+1}\}$". Chứng minh rằng $S\{x, y\}$ là một quan hệ tương đương trên $E$ và đồ thị của nó là nhỏ nhất trong tất cả các đồ thị của các quan hệ tương đương trên $E$ chứa đồ thị của $R$. Các lớp tương đương đối với $S$ được gọi là các thành phần liên thông của $E$ đối với quan hệ $R$.

(c) Gọi $\mathfrak{F}$ là tập hợp các tập con $A$ của $E$ sao cho, với mỗi cặp phần tử $(y, z)$ sao cho $y \in A$ và $z \in E - A$, ta có "không $R\{y, z\}$".

Với mỗi $x \in \mathrm{E}$, hãy chỉ ra rằng giao của các tập hợp $\mathrm{A} \in \mathfrak{F}$ sao cho $x \in \mathrm{A}$ là thành phần liên thông của $x$ đối với quan hệ R.\*