Dilworth’s theorem

Một quan hệ hai ngôi $R$ trên một tập hợp $X$ là một tập hợp con của $X\times X$ . Khi $(x,y)\in R$ , ta viết $xRy$ . Một tập hợp sắp thứ tự một phần, hay poset, là một tập $S$ cùng với một quan hệ hai ngôi $R$ trên $S$ , thỏa mãn đồng thời các điều kiện sau:
(1) Phản xạ: $aRa$ với mọi $a$ thuộc $S$ .

(2) Phản đối xứng: Nếu $aRb$ và $bRa$ thì $a=b$ .

(3) Bắc cầu: Nếu $aRb$ và $bRc$ thì $aRc$ .
Khi $S$ là một poset với quan hệ hai ngôi $R$ thì ta cũng nói $R$ là một quan hệ thứ tự trên $S$ . Trong trường hợp này ta hay ký hiệu $R$ bởi $\leq$ hoặc $\leq_P$ . Phần tử $a$ của $S$ được gọi là phần tử cực đại nếu với mỗi $b$ thuộc $S$ , $(a,b)$ và $(b,a)$ không thuộc $R$ , hoặc $bRa$ . Nói cách khác, $a$ được gọi là phần tử cực đại nếu với mỗi $b$ thuộc $S$ , $a$ và $b$ không so sánh được với nhau hoặc $b\leq a$ . Tương tự ta có khái niệm phần tử cực tiểu.

Ví dụ 1. Tập hợp các số thực $\mathbb R$ cùng với quan hệ hai ngôi $R$ gồm các cặp $(a,b)$ sao cho $a\leq b$ là một poset. Quan hệ này có tính chất: với mỗi số thực $a$ và $b$ , $aRb$ hoặc $bRa$ .
Ví dụ 2. Tập hợp các số nguyên dương $\mathbb N^*$ cùng với quan hệ hai ngôi $R$ gồm các cặp $(a,b)$ sao cho $a$ chia hết $b$ là một poset. Quan hệ này không có tính chất của quan hệ bên trên, nghĩa là có hai phần tử của tập các số nguyên dương không so sánh được theo quan hệ thứ tự này.
Ví dụ 3. Cho $X$ là một tập hữu hạn có nhiều hơn $1$ phần tử và ký hiệu $\mathcal{P}(X)$ là tập lũy thừa của $X$ , là tập gồm tất cả tập con của $X$ . Tập hợp $\mathcal{P}(X)$ cùng với quan hệ hai ngôi $R$ gồm các cặp $(a,b)$ sao cho $a\subset b$ là một poset. Luôn tìm được hai phần tử của tập lũy thừa không so sánh được theo quan hệ thứ tự này.

Cho $S$ là một poset. Nếu với mỗi $a,b\in S$ , $a\leq b$ hoặc $b\leq a$ , thì poset được gọi là một tập hợp sắp thứ tự toàn phần, và $\leq$ được gọi là một quan hệ thứ tự toàn phần trên $S$ . Nếu $a\leq b$ và $a\not=b$ thì ta viết $a<b$ . Một tập con của $S$ được gọi là một xích nếu $\leq$ là một quan hệ thứ tự toàn phần trên tập con đó. Một tập con của $S$ được gọi là một phản xích nếu hai phần tử bất kỳ trong nó không so sánh được theo quan hệ $\leq$ .

Quan hệ thứ tự trong ví dụ 1 là một quan hệ thứ tự toàn phần, các quan hệ thứ tự trong các ví dụ 2 và 3 không phải là quan hệ thứ tự toàn phần. Trong ví dụ 1, mọi tập các số thực đều là xích. Trong ví dụ 2, tập hợp $\{18,25,49\}$ là một phản xích. Trong ví dụ 3, khi $X=[9]$ , thì $\{\{1,2\}, \{1,2,4\},\{1,2,4,9\}\}$ là một xích.

Bây giờ ta đến với định lí chính của bài. Chứng minh được lấy từ [1].

Định lí Dilworth. Cho $P$ là một poset hữu hạn. Khi đó số nhỏ nhất các xích đôi một rời nhau có hợp là $P$ bằng số lớn nhất các phần tử trong một phản xích của $P$ .
Chứng minh. Gọi $m$ là số nhỏ nhất các xích đôi một rời nhau có hợp là $P$ , và $M$ là số lớn nhất các phần tử trong một phản xích của $P$ . Dễ thấy $m\geq M$ . Ta đi chứng minh bất đẳng thức còn lại bằng quy nạp theo $\mid P\mid$ . Khẳng định đúng với $\mid P\mid=0$ . Bây giờ gọi $C$ là một xích cực đại trong $P$ . Nếu mỗi phản xích trong $P\setminus C$ chứa tối đa $M-1$ phần tử thì ra có điều cần chứng minh. Bây giờ giả sử $\{a_1,a_2,\ldots,a_M\}$ là một phản xích trong $P\setminus C$ . Gọi $S^-$ là tập các $x$ thuộc $P$ sao cho tồn tại $i$ để $x\leq a_i$ , và $S^+$ được xác định tương tự. Vì $C$ là cực đại nên phần tử lớn nhất của $C$ không thuộc $S^-$ , và theo giả thiết quy nạp $S^-$ là hợp của $M$ xích đôi một rời nhau $S_1^-$ , $S_2^-$ , $\ldots$ , $S_M^-$ , trong đó $a_i\in S_i^-$ với mọi $i$ . Dễ thấy với mỗi $i$ , $a_i$ là phần tử lớn nhất của $S_i^-$ . Lập luận tương tự với $S^+$ , sau đó hợp các xích tương ứng ta có một biểu diễn của $P$ như là hợp của $M$ xích đôi một rời nhau. $\Box$

Định lí sau đây là một đối ngẫu của định lí Dilworth. Chứng minh được lấy từ [2]

Định lí Mirsky. Cho $P$ là một poset. Nếu $P$ không có một xích $m+1$ phần tử, thì $P$ là hợp của $m$ phản xích.

Chứng minh. Khi $m=1$ định lí là đúng theo cách hiển nhiên. Bây giờ giả sử định lí là đúng với $m-1$ . Giả sử $P$ là một poset hữu hạn không có xích gồm $m+1$ phần tử. Gọi $M$ là tập các phần tử cực đại của $P$ . Khi đó $M$ là phản xích và $P\setminus M$ không có xích với $m$ phần tử. Theo giả thiết quy nạp, $P\setminus M$ là hợp của $m-1$ phản xích. Từ đây ta có điều cần chứng minh. $\Box$
Kết quả sau là một hệ quả của định lí Mirsky.

Định lí Erdos – Szekeres. Cho hai số nguyên dương $m$ và $n$ . Khi đó mỗi dãy dài $mn+1$ các số thực phân biệt đều chứa một dãy con tăng dài $m+1$ hoặc một dãy con giảm dài $n+1$ .
Chứng minh. Xét một dãy như trong định lí, và gọi $P$ là tập các số hạng của dãy. Khẳng định là đúng khi $m=1$ , bây giờ ta xét $m>1$ . Tập hợp $P$ là một poset hữu hạn với quan hệ thứ tự $\leq_P$ được định nghĩa như sau: Với hai phần tử $x$ và $y$ của $P$ , $x\leq_P y$ nếu $x\leq y$ và $x$ không đứng sau $y$ trong dãy ban đầu. Xích trong $P$ là một dãy con tăng, và phản xích trong $P$ là một dãy con giảm. Theo định lí Mirsky, hoặc có một xích với $m+1$ phần tử hoặc $P$ là hợp của $m$ phản xích. Nếu xảy ra trường hợp đầu thì có dãy con tăng dài $m+1$ , nếu xảy ra trường hợp sau thì có một dãy con giảm dài ít nhất
$\displaystyle \left[\frac{mn+1}{m}\right]+1=n+1.$ $\Box$

Tài liệu tham khảo

[1] Tverberg, H.: On dilworth’s decomposition theorem for partially ordered sets. Journal of Combinatorial Theory 3, 305–306 (1967)

[2] L. Mirsky: A dual of Dilworth’s decomposition theorem, Amer. Math. Monthly 78, 876–877.

Pell’s equation

Trong bài này chúng tôi sẽ giới thiệu một số định lí của Dirichlet về xấp xỉ số thực bởi số hữu tỉ, và áp dụng các định lí đó vào lý thuyết phương trình Pell.

Định lí 1 (Dirichlet). Cho số thực $\theta$ và số nguyên dương $Q$ . Khi đó có số nguyên dương $q$ và số nguyên $a$ thỏa mãn $q\leq Q$ và $\displaystyle \left|\theta-\frac{a}{q}\right|\leq\dfrac{1}{q(Q+1)}.$

Chứng minh. Phân hoạch nửa đoạn $[0;1)$ thành $Q+1$ nửa đoạn

$\displaystyle I_k=\left[\frac{k}{Q+1};\frac{k+1}{Q+1}\right),\quad k=0,1,\ldots,Q.$

Xét $Q$ số $\{1.\theta\},\{2.\theta\},\ldots,\{Q.\theta\}$ .

Nếu $I_0$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{m.\theta\}$ , ta chọn $q=m$ . Nếu $I_{Q}$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{n.\theta\}$ , ta chỉ cần chọn $q=n$ . Nếu hai khoảng trên không chứa số nào thì tồn tại một khoảng $I_i$ chứa ít nhất hai số $\{j.\theta\},$ $\{k.\theta\}$ $(j<k)$ trong dãy, ta chọn $q=k-j$ . $\Box$

Như vậy mọi số thực có thể được xấp xỉ bởi một số hữu tỉ có mẫu bị chặn với độ chính xác phụ thuộc vào chặn trên của mẫu. Sau đây là một áp dụng đẹp đẽ của định lí trên:

Hệ quả. Mọi số nguyên tố dạng $4k+1$ có thể viết thành tổng của hai số chính phương.

Chứng minh. Theo định lí Wilson, tồn tại số nguyên dương $c$ sao cho $c^2+1\equiv 0\pmod{p}.$ Theo định lí Dirichlet, tồn tại các số nguyên $a,b$ sao cho $1\leq b\leq [\sqrt{p}]$ và

$\displaystyle \left|\frac{c}{p}-\frac{a}{b}\right|\leq\frac{1}{b([\sqrt{p}]+1)}<\frac{1}{b\sqrt{p}}. \quad (*)$

Từ $(*)$ ta có $|cb-ap|<\sqrt{p}$ , suy ra $0<(cb-ap)^2+b^2<2p$ , mà $(cb-ap)^2+b^2\equiv b^2(c^2+1)\equiv 0\pmod{p},$ suy ra $(cb-ap)^2+b^2=p.$ $\Box$

Định lí 2 (Dirichlet). Cho số vô tỷ $\alpha$ . Khi đó có vô hạn số hữu tỷ $\displaystyle\frac{a}{q}$ sao cho $q>0$ và $\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{q^2}.$ Hơn nữa ta có thể chọn $q$ lớn tùy ý.

Chứng minh. Ta sẽ xây dựng dãy hữu tỷ thỏa mãn bằng quy nạp.

Với số nguyên $Q\geq 1$ bất kỳ, theo định lí 1, tồn tại phân số $\displaystyle\frac{a}{q}$ sao cho $1\leq q\leq Q$ và

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}.$

Bằng cách thu gọn $\displaystyle\frac{a}{q}$ nếu cần, ta có thể xem phân số này tối giản. Do $Q+1>q$ nên từ bất đẳng thức trên ta có

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}<\frac{1}{q^2}.$

Giả sử ta đã xây dựng được dãy các phân số tối giản đôi một khác nhau $\displaystyle\frac{a_1}{q_1},\frac{a_2}{q_2},\ldots,\frac{a_m}{q_m}$ thỏa mãn bất đẳng thức trong định lí. Vì $\alpha$ là số vô tỷ nên $|\alpha-a_i/q_i|>0\,\forall i$ , bởi thế nên ta có thể chọn được số nguyên dương $Q$ để $Q>\max \{|\alpha-a_i/q_i|^{-1}\}.$ Dùng định lí 1 cho số $Q$ này ta tìm được phân số tối giản $\displaystyle\frac{a_{m+1}}{q_{m+1}}$ sao cho $1\leq q_{m+1}\leq Q$ và

$\displaystyle \left|\alpha-\frac{a_{m+1}}{q_{m+1}}\right|\leq\frac{1}{q_{m+1}(Q+1)}<\frac{1}{q_{m+1}^2}.$

Phân số này khác tất cả các phân số trước vì

$\displaystyle \left|\alpha-\frac{a_{m+1}}{q_{m+1}}\right|\leq\frac{1}{q_{m+1}(Q+1)}<\frac{1}{Q}<\min\{|\alpha-a_i/q_i|\}.$

Để kết thúc chỉ cần để ý rằng với mỗi $q>1$ chỉ có nhiều nhất hai giá trị $a$ làm cho bất đẳng thức trong định lí đúng. $\Box$

Continue reading →

Convex set

Trong bài này, $\mathbb{R}^1,$ $\mathbb{R}^2$ và $\mathbb{R}^3$ lần lượt là tập các điểm thuộc đường thẳng, mặt phẳng và không gian.

Cho số nguyên dương $d\leq 3.$ Một tập hợp $C\subset \mathbb{R}^d$ được gọi là tập hợp lồi nếu với mỗi hai điểm $A$ và $B$ thuộc $C,$ cả đoạn thẳng $AB$ cũng nằm trong $C.$

Dễ thấy giao của một họ bất kỳ các tập hợp lồi là một tập hợp lồi. Vì thế ta có thể định nghĩa bao lồi của một tập hợp $X\subset \mathbb{R}^d$ là giao của tất cả các tập hợp lồi trong $\mathbb{R}^d$ chứa $X.$ Như vậy bao lồi của một tập hợp là tập hợp lồi nhỏ nhất chứa nó.

Nếu $A$ và $B$ là hai điểm khác nhau thì bao lồi của tập hợp $\{A,B\}$ là đoạn thẳng $AB.$ Nếu $A,B$ và $C$ là ba điểm không thẳng hàng thì bao lồi của tập $\{A,B,C\}$ là tam giác $ABC$ (phần trong và biên).

Dùng tổ hợp lồi ta có một mô tả khác của bao lồi.

Định lí 1. Cho $X$ là một tập hợp con khác rỗng của $\mathbb{R}^2.$ Khi đó điểm $x$ thuộc bao lồi của $X$ khi và chỉ khi tồn tại các điểm $x_1,x_2,\ldots,x_n\in X$ và các số thực không âm $t_1,t_2,\ldots,t_n$ thỏa mãn $\sum t_i=1$ và $x=\sum t_ix_i.$

Biểu diễn $\sum t_ix_i$ như trong định lí trên được gọi là tổ hợp lồi của các điểm $x_1,$ $x_2,$ $\ldots,$ $x_n.$

Với tập hợp hữu hạn trong mặt phẳng ta có kết quả sau, kết quả này được dùng nhiều trong các bài toán thi chọn học sinh giỏi.

Định lí 2. Cho số nguyên $n>2$ và $n$ điểm $A_1,A_2,\ldots,A_n$ trong $\mathbb{R}^2.$ Khi đó bao lồi của tập $\{A_i\}$ là đa giác lồi có tập đỉnh là tập con của tập $\{A_i\}.$

Trong định lí trên một đoạn thẳng được xem là một đa giác lồi với hai đỉnh là các đầu mút.

Định lí Helly là một kết quả cơ bản trong hình học tổ hợp về giao của các tập hợp lồi. Nó được Eduard Helly phát hiện vào năm 1913, nhưng mãi đến năm 1923 ông mới công bố, lúc đó các chứng minh của Radon (1921) và Konig (1922) đã xuất hiện.

Định lí 3 (Helly). Cho số nguyên $n>3$ và $n$ tập hợp lồi $X_1,X_2,\ldots,X_n$ trong $\mathbb{R}^2.$ Khi đó nếu mỗi ba tập trong chúng có giao khác rỗng thì cả $n$ tập có giao khác rỗng.

Chứng minh. Ta chứng minh bằng quy nạp theo $n.$ Đầu tiên ta xét $n=4.$ Giả sử bốn tập hợp lồi $X_1,$ $X_2,$ $X_3$ và $X_4$ trong $\mathbb{R}^2$ có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Lấy bốn điểm $A_1,$ $A_2,$ $A_3$ và $A_4$ sao cho $A_i$ thuộc $\displaystyle \bigcap_{j\not=i}A_j$ với mỗi $i.$

Nếu bốn điểm $A_1,$ $A_2,$ $A_3$ và $A_4$ thẳng hàng theo thứ tự đó thì $A_2$ thuộc cả bốn tập lồi. Nếu bao lồi của $\{A_i\}$ là một tam giác thì điểm còn lại không phải là đỉnh của bao lồi sẽ thuộc cả bốn tập lồi. Nếu bao lồi của $\{A_i\}$ là một tứ giác thì giao điểm của hai đường chéo tứ giác sẽ thuộc cả bốn tập lồi.

Vậy khẳng định đúng với $n=4.$ Bây giờ ta giả sử khẳng định đúng với $n\, (n\geq 4),$ và đi chứng minh nó đúng với $n+1.$ Xét $n+1$ tập hợp lồi $X_1,X_2,\ldots,X_{n+1}$ trong $\mathbb{R}^2$ có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Dùng giả thiết quy nạp cho $n$ tập hợp lồi $X_1\cap X_{n+1},X_2\cap X_{n+1},\ldots,X_n\cap X_{n+1}$ ta có điều cần chứng minh. $\Box$

Một cách tổng quát ta có kết quả sau, chứng minh được thực hiện tương tự như trên.

Cho số nguyên $n>d+1$ và $n$ tập hợp lồi $X_1,X_2,\ldots,X_n$ trong $\mathbb{R}^d.$ Khi đó nếu mỗi $d+1$ tập trong chúng có giao khác rỗng thì cả $n$ tập có giao khác rỗng.

Polynomials in one variable: Basic definitions

Trong bài này $K$ là một trong các tập hợp $\mathbb{F}_p$ (tập các số nguyên modulo một số nguyên tố $p$ ), $\mathbb{Q}$ , $\mathbb{R},$ hoặc $\mathbb{C}$ .

Định nghĩa 1. Cho $n$ là một số tự nhiên và $a_0,a_1,...,a_n \in K$ . Mỗi tổng hình thức có dạng

$a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0$

được gọi là một đa thức trên $K$ theo biến $x$ với hệ số $a_0,a_1,...,a_n$ . Nếu $k$ là chỉ số lớn nhất sao cho $a_k \neq 0$ , thì ta nói đa thức $f(x)=a_k x^k+\ldots+a_1x+a_0$ có bậc $k$ , viết $\text{deg}(f(x))=k$ , $a_k$ được gọi là hệ số đầu của đa thức $f(x)$ , và $a_0$ được gọi là hệ số tự do của $f(x)$ . Nếu $a_0$ là hệ số đầu của $f(x)$ , thì $f(x)$ được gọi là đa thức hằng.

Nếu hệ số đầu của $f(x)$ là $1$ , thì $f(x)$ được gọi là đa thức monic. Tập tất cả đa thức với hệ số trong $K$ được ký hiệu bởi $K[x]$ .

Theo định nghĩa này thì đa thức không, đa thức mà mọi hệ số là không, không có bậc. Để thuận tiện, ta qui ước nó là đa thức hằng và có bậc bằng $-\infty$ . Một đa thức hằng $f(x)=a_0$ có bậc $0$ nếu $a_0 \neq 0$ . Hai đa thức bằng nhau nếu chúng có cùng bậc và tất cả các hệ số tương ứng bằng nhau. Cần phân biệt giữa đa thức $f(x)$ và hàm đa thức tương ứng từ $K$ đến $K$ xác định bởi thay một phần tử của $K$ vào vị trí của $x$ . Nếu $f(x)=a_m x^m+\ldots+a_1x+a_0$ và $c \in K$ , thì $f(c)=a_m c^m+\ldots+a_1c+a_0$ được gọi là giá trị của $f(x)$ tại $c$ . Nếu $K$ là $\mathbb{F}_p$ thì có thể có hai đa thức khác nhau xác định cùng một hàm đa thức.

Ví dụ 1. Cho $K$ là $\mathbb{F}_3$ và xét các đa thức $x^3$ và $x$ . Với mỗi $c \in \mathbb{F}_3$ , ta có $c^3 \equiv c\pmod{3},$ do đó các hàm đa thức $f(x)=x^3$ và $g(x)=x$ là bằng nhau như các hàm từ $\mathbb{F}_3$ tới $\mathbb{F}_3$ .