Bài tập 6, § 4

(a) Cho A là một tập hợp và cho $(\mathrm{X}_i)_{1 \leqslant i \leqslant m}$, $(\mathrm{Y}_j)_{m+1 \leqslant j \leqslant m+n}$ là hai họ hữu hạn các tập con của A. Gọi $h$ là số nguyên nhỏ nhất sao cho, với mỗi số nguyên $r \leqslant m - h$ và mỗi tập con $\{i_1, \ldots, i_{r+h}\}$ gồm $r + h$ phần tử của $[1, m]$, tồn tại một tập con $\{j_1, \ldots, j_r\}$ gồm $r$ phần tử của $[m + 1, m + n]$ sao cho hợp của các tập $\mathrm{X}_{i_\alpha}$ $(1 \leqslant \alpha \leqslant r + h)$ cắt mỗi tập $\mathrm{Y}_{j_\beta}$ $(1 \leqslant \beta \leqslant r)$ (điều này kéo theo $m \leqslant n + h$). Chứng minh rằng tồn tại một tập con hữu hạn B của A có nhiều nhất $n + h$ phần tử sao cho mọi $\mathrm{X}_i$ $(1 \leqslant i \leqslant m)$ và mọi $\mathrm{Y}_j$ $(m + 1 \leqslant j \leqslant m + n)$ đều cắt B. (Xét quan hệ thứ tự trên khoảng $[1, m + n]$ mà đồ thị của nó là hợp của đường chéo và tập hợp các cặp $(i, j)$ sao cho $1 \leqslant i \leqslant m$ và $m + 1 \leqslant j \leqslant m + n$ và $\mathrm{X}_i \cap \mathrm{Y}_j \neq \emptyset$, rồi áp dụng Bài tập 5 cho tập hợp có thứ tự này.)

(b) Cho E và F là hai tập hợp hữu hạn và cho $x \rightarrow \mathrm{A}(x)$ là một ánh xạ từ E vào $\mathfrak{P}(\mathrm{F})$. Khi đó tồn tại một đơn ánh $f$ từ E vào F sao cho $f(x) \in \mathrm{A}(x)$ với mỗi $x \in \mathrm{E}$ khi và chỉ khi với mỗi tập con H của E ta có Card $\left( \bigcup_{x \in \mathrm{H}} \mathrm{A}(x) \right) \geqslant$ Card (H) (phương pháp chứng minh tương tự như phương pháp chứng minh của (a), với $h = 0$).

(c) Với các giả thiết của (b), cho G là một tập con của F. Khi đó tồn tại một đơn ánh $f$ từ E vào F sao cho $f(x) \in \mathrm{A}(x)$ với mỗi $x \in \mathrm{E}$ và sao cho $f(E)\supset G$ khi và chỉ khi $f$ thỏa mãn điều kiện của (b) và với mỗi tập con $L$ của $G$, lực lượng của tập hợp tất cả các $x\in E$ sao cho $A(x)\cap L\neq\varnothing$ là $\geq\operatorname{Card}(L)$. (Cho $(a_i)_{1\leq i\leq p}$ là dãy các phần tử phân biệt của $G$, được sắp theo một thứ tự nào đó; cho $(b_j)_{p+1\leq j\leq p+m}$ là dãy các phần tử phân biệt của $F$, được sắp theo một thứ tự nào đó; và cho

là dãy các phần tử phân biệt của $E$, được sắp xếp theo một thứ tự nào đó. Xét quan hệ thứ tự trên tập hợp $[1,p+m+n]$ có đồ thị là hợp của đường chéo và tập hợp các cặp $(i,j)$ sao cho hoặc

hoặc $1\leq i\leq p$ và $p+m+1\leq j\leq p+m+n$ và $a_i\in A(c_j)$,

hoặc $p+1\leq i\leq p+m$ và $p+m+1\leq j\leq p+m+n$ và $b_i\in A(c_j)$;

sau đó áp dụng Bài tập 5.)