Bài tập 5, § 4

Cho E là một tập hợp có thứ tự sao cho tồn tại một số nguyên $k$ mà $k$ là số lớn nhất các phần tử trong một tập con tự do X của E ($§ 1$, Bài tập 5). Chứng minh rằng E có thể được phân hoạch thành $k$ tập con được sắp thứ tự toàn phần (đối với thứ tự cảm sinh). Chứng minh gồm hai bước :

(a) Nếu E là hữu hạn và có $n$ phần tử, dùng quy nạp theo $n$; gọi $a$ là một phần tử cực tiểu của E và đặt $\mathrm{E}' = \mathrm{E} - \{a\}$. Nếu tồn tại một phân hoạch của $\mathrm{E}'$ thành $k$ tập hợp được sắp thứ tự toàn phần $\mathrm{C}_i$ $(1 \leqslant i \leqslant k)$, gọi $\mathrm{U}_i$ là tập hợp của mọi $x \in \mathrm{C}_i$ mà $\geqslant a$. Hãy chỉ ra rằng tồn tại ít nhất một chỉ số $i$ sao cho một tập con tự do của $\mathrm{E}' - \mathrm{U}_i$ có nhiều nhất $k - 1$ phần tử. Chứng minh điều này bằng phản chứng. Với mỗi $i$, gọi $\mathrm{S}_i$ là một tập con tự do của $\mathrm{E}' - \mathrm{U}_i$ có $k$ phần tử, gọi S là hợp của các tập hợp $\mathrm{S}_i$, và gọi $s_j$ là phần tử nhỏ nhất của $\mathrm{S} \cap \mathrm{C}_j$ với mỗi chỉ số $j \leqslant k$; hãy chỉ ra rằng $k + 1$ phần tử $a, s_1, \ldots, s_k$ lập thành một tập con tự do của E.

(b) Nếu E là tùy ý, chứng minh được thực hiện bằng quy nạp theo $k$, như sau. Một tập con C của E được gọi là liên quan mạnh trong E nếu với mỗi tập con hữu hạn F của E tồn tại một phân hoạch của F thành nhiều nhất $k$ tập hợp được sắp thứ tự toàn phần sao cho $\mathrm{C} \cap \mathrm{F}$ được chứa trong một tập hợp trong số đó. Hãy chỉ ra rằng tồn tại một tập con liên quan mạnh cực đại $\mathrm{C}_0$, và mọi tập con tự do của $\mathrm{E} - \mathrm{C}_0$ đều có nhiều nhất $k - 1$ phần tử. (Lập luận bằng phản chứng, và giả sử rằng có một tập con tự do $\{a_1, \ldots, a_k\}$ gồm $k$ phần tử trong $\mathrm{E} - \mathrm{C}_0$. Xét mỗi tập hợp $\mathrm{C}_0 \cup \{a_i\}$ $(1 \leqslant i \leqslant k)$, và phát biểu việc nó không liên quan mạnh, do đó đưa vào một tập con hữu hạn $\mathrm{F}_i$ của E với mỗi chỉ số $i$. Sau đó xét hợp F của các tập hợp $\mathrm{F}_i$ và dùng việc $\mathrm{C}_0$ là liên quan mạnh để đi đến mâu thuẫn.)