Bài tập 10, § 4

(a) Một tập hợp có thứ tự E đẳng cấu với một tập con của tích của $n$ tập hợp được sắp thứ tự toàn phần khi và chỉ khi đồ thị của thứ tự trên E là giao của các đồ thị của $n$ thứ tự toàn phần trên E. (Để chứng minh điều kiện là cần, hãy chứng minh rằng nếu

là tích của $n$ tập hợp được sắp thứ tự toàn phần, thì đồ thị của thứ tự tích trên F là giao của $n$ đồ thị của các thứ tự từ điển trên F.)

(b) Một tập hợp có thứ tự E đẳng cấu với một tập con của tích của hai tập hợp được sắp thứ tự toàn phần khi và chỉ khi thứ tự $\Gamma$ trên E có tính chất là tồn tại một thứ tự khác $\Gamma'$ trên E sao cho bất kỳ hai phần tử phân biệt nào của E đều so sánh được theo đúng một trong hai thứ tự $\Gamma$, $\Gamma'$.

(c) Cho A là một tập hợp hữu hạn gồm $n$ phần tử. Cho E là tập con của $\mathfrak{P}(A)$ gồm tất cả các tập hợp $\{x\}$ và $A - \{x\}$ khi $x$ chạy qua A. Hãy chứng minh rằng $n$ là số nguyên $m$ nhỏ nhất sao cho E, có thứ tự theo quan hệ bao hàm, đẳng cấu với một tập con của một tích của $m$ tập hợp được sắp thứ tự toàn phần (dùng (a)).