Tài liệu Về định lý helly và một số ứng dụng

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ HÂN VỀ ĐỊNH LÝ HELLY VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ HÂN VỀ ĐỊNH LÝ HELLY VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. Nguyễn Thị Thu Thủy THÁI NGUYÊN - 2017 i Mục lục Lời cảm ơn ii Mở đầu 2 Chương 1. Một số kiến thức chuẩn bị 4 1.1 1.2 Tập compact trong Rn . . . . . . . . . . . . . . . . . . . . . 1.1.1 Tập compact . . . . . . . . . . . . . . . . . . . . . . 4 4 1.1.2 Dãy Cauchy . . . . . . . . . . . . . . . . . . . . . . . 11 Tập hợp lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1 1.2.2 Khái niệm và ví dụ . . . . . . . . . . . . . . . . . . . 13 Tính chất của tập lồi . . . . . . . . . . . . . . . . . . 14 Chương 2. Về định lý Helly và một số ứng dụng 20 2.1 Định lý Helly . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.1 2.1.2 2.2 Một số ứng dụng của Định lý Helly . . . . . . . . . . . . . . 28 2.2.1 2.2.2 2.3 Tính chất giao hữu hạn . . . . . . . . . . . . . . . . 20 Định lý Helly . . . . . . . . . . . . . . . . . . . . . . 23 Định lý Thư viện Nghệ thuật . . . . . . . . . . . . . 28 Bài toán của Vincensini . . . . . . . . . . . . . . . . 36 Một số bài toán áp dụng . . . . . . . . . . . . . . . . . . . . 44 Kết luận 48 Tài liệu tham khảo 49 ii Lời cảm ơn Với lòng biết ơn sâu sắc em xin chân thành gửi tới PGS.TS. Nguyễn Thị Thu Thủy - người cô đã tận tâm, nhiệt tình chỉ bảo, động viên giúp đỡ em trong suốt quá trình nghiên cứu và hoàn thành luận văn. Em xin chân thành cảm ơn các thầy cô trong khoa Toán - Tin, Trường Đại học Khoa học – Đại học Thái Nguyên, các giáo sư của Trường Đại học Khoa học Tự nhiên – Đại học quốc gia Hà Nội; của Viện Toán học – Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện thuận lợi giúp đỡ em trong quá trình học tập và nghiên cứu tại trường Đại học Khoa học. Em xin chân thành cảm ơn các anh chị và bạn bè đồng nghiệp trong lớp Cao học Toán K9B2 đã luôn giúp đỡ em trong suốt quá trình học tập và nghiên cứu. Thái Nguyên, tháng 10 năm 2017 Tác giả luận văn Nguyễn Thị Hân 2 Mở đầu Tập hợp lồi là một khái niệm xuất hiện từ lâu trong nhiều ngành của Toán học, nó được nhiều nhà toán học quan tâm nghiên cứu như E. Buchman và F.A. Vanlentine, V.L. Klee, C. Carathéodery . . . Đặc biệt là nhà toán học E. Helly. Định lý Helly là một kết quả cơ bản trong hình học rời rạc về giao của các tập hợp lồi. Định lý cho ta một điều kiện đủ để nhận biết khi nào một họ các hình lồi sẽ có giao khác rỗng. Nó được phát hiện bởi E. Helly năm 1913, nhưng chỉ được xuất bản vào năm 1923, khi các chứng minh khác của Radon (1921) và König (1922) đã được đăng. Định lý Helly được phát biểu như sau: Giả sử F := {F1 , F2 , . . . , Fk } là họ gồm k tập hợp lồi F1 , F2 , . . . , Fk trong Rn , trong đó k > n. Nếu giao của mọi bộ n+1 tập của họ F là khác rỗng, thì giao của tất cả các tập hợp T trong họ F là khác rỗng, nghĩa là kj=1 Fj 6= ∅. Để áp dụng cho một số vô hạn các tập hợp ta cần có thêm tính chất compact: Nếu F := {Fα , α ∈ I} là một họ các tập hợp lồi compact trong Rn và giao của mọi bộ không quá n + 1 tập của họ F là khác rỗng thì giao của tất cả các tập hợp trong họ đó là khác rỗng. Mục đích của đề tài luận văn là tìm hiểu và trình bày các chứng minh của định lý Helly, trình bày một số ứng dụng của định lý Helly như định lý Thư Viện Nghệ Thuật, bài toán của Vincensini, đồng thời tìm hiểu một số đề thi học sinh giỏi toán quốc gia và quốc tế áp dụng định lý Helly để giải. Nội dung của đề tài luận văn được trình bày trong hai chương. Chương 1 giới thiệu một số khái niệm và tính chất của tập compact, tập hợp lồi 3 trong không gian Rn . Chương 2 trình bày chứng minh định lý Helly, một số ứng dụng của định lý Helly và một số bài toán áp dụng định lý Helly để giải. 4 Chương 1 Một số kiến thức chuẩn bị Chương này trình bày một số kiến thức về tập hợp compact và tập hợp lồi trong không gian Rn . Mục 1.1 giới thiệu khái niệm tập hợp compact và một số tính chất của tập compact trong Rn . Mục 1.2 giới thiệu về tập hợp lồi và một số tính chất của tập hợp lồi. Nội dung của chương được viết trên cơ sở tài liệu [6], [7]. 1.1 1.1.1 Tập compact trong Rn Tập compact Định nghĩa 1.1.1 Một tập con K của Rn được gọi là tập compact nếu mỗi tập con vô hạn của K có một điểm tụ thuộc K. Chú ý 1.1.2 Cho K ∈ Rn là tập compact, Định nghĩa 1.1.1 thỏa mãn hai điều kiện: (i) Mỗi tập hợp con vô hạn của K đều có ít nhất một điểm tụ p; (ii) Điểm tụ p phải thuộc K. Định lý 1.1.3 (xem [6]) Tập hợp con K của Rn là compact nếu và chỉ nếu (i) Mỗi tập hợp con vô hạn của K đều có ít nhất một điểm tụ p; (ii) Tất cả các điểm tụ của K đều thuộc K. 5 Định lý 1.1.4 (xem [6]) Tập tập hợp con K compact của Rn là tập đóng và bị chặn. Cho I = {(x1 , x2 , . . . , xn )} ∈ Rn ; ai ≤ xi ≤ bi , i = 1, n với a = (a1 , a2 , . . . , an ) và b = (b1 , b2 , . . . , bn ) và ta đặt l (I) là cạnh lớn nhất của I, nghĩa là l (I) = sup {b1 − a1 , b2 − a2 , . . . , bn − an } . Định lý 1.1.5 (Bolzano–Weierstrass) (xem [6]) Mọi tập con vô hạn bị chặn của Rn đều có điểm tụ. Chứng minh. Giả sử A là một tập hợp con vô hạn bị chặn của Rn và cho I1 là một hình đóng chứa A. Chia I1 thành 2n hình đóng bằng cách cắt ngang mỗi cạnh của nó. Vì I1 chứa vô số điểm của A, nên tồn tại ít nhất một hình I2 trong số những hình được chia nhỏ sẽ chứa vô số điểm của A. Tiếp theo ta lại chia hình I2 thành 2n hình đóng bằng cách cắt ngang mỗi cạnh của nó, sao cho có ít nhất một hình đóng I3 , trong số những hình được chia nhỏ, chứa vô số điểm của A. Tiếp tục theo cách này, ta nhận được dãy {Ik }k≥1 các hình đóng lồng nhau khác rỗng, mỗi một hình trong đó chứa vô hạn điểm của A. Chú ý rằng cạnh dài nhất của hình thứ k thỏa mãn 0 < l (Ik ) = l (I1 ) 2k−1 và dãy các số thực {l(Ik )}k≥1 hội tụ đến 0. Như vậy, với mỗi i thỏa mãn 1 ≤ i ≤ n, các khoảng đóng [ak,i , bk,i ] của Ik tạo thành một dãy các tập con lồng nhau khác rỗng compact của R. Do đó, tồn tại một điểm pi ∈ R thỏa mãn: ∞ \ pi ∈ [ak,i , bk,i ]. k=1 Nếu ta đặt p = (p1 , p2 , . . . , pn ) ∈ Rn thì suy ra mỗi hình cầu B (p, ε) chứa điểm của A khác p, ở đây ε là số dương bé tùy ý. Vì vậy, p là điểm tụ của A.  6 Định lý 1.1.6 (Heine–Borel) (xem [6]) Mỗi tập hợp con của Rn là tập compact nếu và chỉ nếu nó đóng và bị chặn. Hệ quả 1.1.7 (xem [6]) Tập hợp con đóng của tập hợp bị chặn là tập compact. Hệ quả 1.1.8 (xem [6]) Tập hợp con đóng của tập hợp compact là tập compact. Hệ quả 1.1.9 (xem [6]) Nếu K là tập compact và S là tập đóng, thì K ∩S cũng là tập compact. Định lý 1.1.10 (Định lý các tập hợp lồng nhau) (xem [6]) Nếu K1 , K2 , K3 , . . . là một họ các tập con khác rỗng compact của Rn thỏa mãn K1 ⊇ K2 ⊇ K3 ⊇ . . . thì ∞ T Ki 6= ∅. i=1 Sau đây sự tương đương của định nghĩa tập compact trong Rn ở trên với định nghĩa theo quan điểm của phủ các tập hợp mở. Định lý 1.1.11 (xem [6]) Tập con K của không gian Rn là tập compact khi và chỉ khi mọi phủ mở của K đều có phủ con hữu hạn. Chứng minh. Từ những kết quả trên, ta chỉ cần chứng minh K đóng và bị chặn (và do đó compact) nếu và chỉ nếu mỗi phủ mở của K đều có phủ con hữu hạn. Giả sử mỗi phủ mở của K đều có phủ con hữu hạn. Đặt U là họ các hình cầu mở dạng B (k, 1) tâm k bán kính 1, trong đó k ∈ K. Hình cầu B (k, 1) này là một phủ mở của tập compact K và do đó có phủ con hữu hạn. Nếu {k1 , k2 , . . . , km } là tâm của các phủ con này, thì K⊂ m [ B (ki , 1) i=1 và tập K bị chặn. Bây giờ, giả sử mọi phủ mở của K đều có một một phủ con hữu hạn. Gọi U = Rn \K là phần bù của K. Vì tập K bị chặn nên U 6= ∅. Ta sẽ 7 chỉ ra rằng không có điểm q ∈ U nào là điểm tụ của K. Thật vậy, giả sử q ∈ U là một điểm tùy ý, và với mỗi p ∈ K ta xét hình cầu mở B (p, δ (p)) = {x ∈ Rn : kx − pk < δ (p)} , ở đây δ (p) = 1 2 kp − qk > 0 nếu p 6= q. Họ U = {B (p, δ (p)) : p ∈ K} là một phủ mở của K, và do đó có phủ con hữu hạn. Vì vậy ta có các điểm {p1 , p2 , . . . , pm } của K thỏa mãn K⊂ m [ B (pi , δ (pi )). i=1 Đặt r = min {δ (pi ) : i = 1, 2, . . . } và xét lân cận B (p, r) của q. Nếu 1 ≤ i ≤ m và s ∈ B (q, r) thì 2δ (pi ) = kq − pi k ≤ kq − sk < r + ks − pi k + ks − pi k ≤ δ (pi ) + ks − pi k , vì vậy ks − pi k > δ (pi ) với mọi i = 1, . . . , m và do đó s ∈ / B (pi , δ (pi )) với mọi i = 1, . . . , m. Suy ra "m # m [ [ B (q, r)∩K ⊂ B (q, r)∩ B (pi , δ (pi )) = B (q, r)∩B (pi , δ (pi )) = ∅. i=1 i=1 Vì vậy B (p, r) ⊂ Rn \K và do đó Rn \K là tập mở nên K là tập đóng. Ngược lại, giả sử tập K là tập đóng và bị chặn của Rn và U = {Uα : α ∈ I} là một họ các tập mở của Rn sao cho K ⊂ ∪ {Uα : α ∈ I}. Giả sử K không chứa trong hợp của bất kỳ họ hữu hạn các tập mở của U. Vì tập K là bị chặn nên có một số M > 0 sao cho K ⊆ I1 trong đó I1 là hình đóng trong Rn được cho bởi I1 = {(x1 , x2 , . . . , xn ) ∈ Rn : |xk | ≤ M, k = 1, . . . , n} . Bằng cách cắt ngang mỗi cạnh của I1 , ta nhận được 2n khoảng đóng trong I1 chứa các điểm của K nhưng không được chứa trong hợp của bất kỳ số 8 hữu hạn nào các tập trong tập U. Gọi I2 là một hình đóng bất kỳ trong những hình đóng được chia của I1 sao cho tập hợp K ∩ I2 không chứa trong hợp của bất kỳ số hữu hạn nào của tập U. Tiếp tục, ta lại cắt ngang mỗi cạnh của I2 để được 2n hình đóng chứa trong I2 . Gọi I3 là một hình đóng tùy ý trong những hình đóng được phân chia từ I2 sao cho tập hợp khác rỗng K ∩ I3 không chứa trong hợp của bất kỳ số hữu hạn nào của tập U. Ta tiếp tục quá trình này và thu được một dãy {Ik }k≥1 các hình đóng sao cho độ dài l (Ik ) của cạnh dài nhất của Ik thỏa mãn 0 < l (Ik ) ≤ 2M l (I1 ) ≤ , 2k−1 2k−i k > 1. Theo chứng minh của Định lý Bolzano–Weierstrass trong Rn , vì dãy các số thực {Ik }k≥1 hội tụ đến 0, thì với mọi i ≥ 1, khoảng đóng và bị chặn tương ứng [ak,i , bk,i ] của Ik tạo thành dãy các tập con compact của R, do đó tồn tại pi ∈ R sao cho pi ∈ ∞ \ [ak,i , bk,i ]. k=1 n Nếu ta đặt p = (p1 , . . . , pn ) ∈ R thì p ∈ ∞ T Ik . Vì mỗi Ik đều chứa các k=1 điểm của K nên suy ra điểm p là điểm tụ của K và vì K đóng nên p ∈ K. Bây giờ, vì U là một phủ mở của K, nên tồn tại số α sao cho p ∈ Uα và do đó tồn tại số δ > 0 sao cho B (p, δ) ⊂ Uα . Vì lim l (Ik ) = 0, nên ta có k→∞ δ 2 thể chọn k đủ lớn sao cho 0 < l (Ik ) < và toàn bộ điểm của Ik đều được chứa trong tập hợp Uα . Điều này là mâu thuẫn với cách xây dựng Ik tức là K ∩ Ik không chứa trong hợp của một số hữu hạn các tập hợp của U. Do đó, K được phủ bằng họ hữu hạn các phần tử của U.  Định lý 1.1.12 (Bolzano–Weierstrass) (xem [6]) Mọi dãy vô hạn bị chặn của Rn đều có dãy con hội tụ. Chứng minh. Giả sử {xk }k≥1 là một dãy bị chặn trong Rn . Nếu chỉ có một số hữu hạn các điểm phân biệt trong dãy này, thì ít nhất một trong những điểm này, gọi là x0 , phải xuất hiện một cách vô hạn. Xác định một 9 dãy con của dãy {xk }k≥1 bằng cách chọn các phần tử này mỗi lần khi nó xuất hiện. Đây là dãy con hội tụ của dãy gốc. Mặt khác, nếu dãy {xk }k≥1 chứa vô số điểm phân biệt trong Rn , thì theo Định lý Bolzano–Weierstrass suy ra rằng có ít nhất một điểm tụ, gọi là x0 , của tập hợp vô hạn điểm phân biệt từ dãy này. Giả sử xk1 là phần tử của dãy sao cho kxk1 − x0 k < 1.
Xét hình cầu mở B x0 , 12 , vì x0 là điểm tụ của tập hợp S1 = {xk : k ≥ 1}, nó cũng là điểm tụ của tập hợp S2 = {xk : k > k1 } bằng cách xóa đi một số
hữu hạn điểm của S1 . Do đó, có một điểm xk2 của S2 thuộc vào B x0 , 21 . Chú ý rằng từ xk2 ∈ S2 , suy ra k2 > k1 .
Lại xét hình cầu mở B x0 , 31 và cho S2 = {xk : k > k2 }. Vì x0 là điểm
tụ của S3 nên có một điểm xk3 ∈ S3 sao cho xk3 ∈ B x0 , 31 . Chú ý rằng k3 > k2 vì xk3 ∈ S3 . Tiếp tục thực hiện các bước như trên ta thu được dãy con {xki }i≥1 của dãy {xk }k≥1 thỏa mãn 1 kxki − x0 k < , i sao cho lim xki = x0 . i→∞ Những điều này chứng tỏ rằng nếu dãy {xk }k≥1 là bị chặn và x0 là điểm tụ của tập hợp S = {xk : k ≥ 1} thì có một dãy con{xki }i≥1 của dãy {xk }k≥1 hội tụ đến x0 .  Sau đây là đặc điểm của tính compact trong Rn theo quan điểm dãy. Định lý 1.1.13 (xem [6]) Tập hợp con K của Rn là tập hợp compact nếu và chỉ nếu mọi dãy trong K đều có dãy con hội tụ đến điểm của K. Chứng minh. Giả sử tập hợp con K của Rn là tập compact, và giả sử {xk }k≥1 là dãy các điểm với xk ∈ K, k ≥ 1. Do K là tập bị chặn nên dãy này là bị chặn và theo Định lý Bolzano–Weierstrass, dãy này có dãy con hội tụ {xki }i≥1 , với lim xki = x0 . Vì tập K là đóng và {xki }i≥1 là dãy các i→∞ điểm của K hội tụ đến x0 , nên x0 ∈ K. Ngược lại, giả sử bất kỳ dãy {xk }k≥1 các điểm của xk ∈ K, với mọi k ≥ 1, đều có dãy con {xki }i≥1 với x0 = lim xki ∈ K. i→∞ 10 Đầu tiên ta chỉ ra rằng K bị chặn. Nếu K không bị chặn thì với mỗi số dương k, ta đều tìm được điểm xk ∈ K sao cho kxk k ≥ k. Bây giờ, theo giả thiết, có dãy con hội tụ {xki }i≥1 của dãy này sao cho x0 = lim xki ∈ K, i→∞ và theo bất đẳng thức tam giác ta có kxki k ≤ kxki − x0 k + kx0 k , ∀i > 1. Chọn số nguyên i0 thỏa mãn kxki − x0 k < 1 với i > i0 sao cho  kxki k ≤ max kxk1 k , . . . , xki0 −1 , 1 + kx0 k , ∀i ≥ 1. Tuy nhiên, từ cách mà dãy {xk }k≥1 được xây dựng, ta có kxki k ≥ ki → ∞ khi i → ∞, điều này là mâu thuẫn. Do đó, K bị chặn. Tiếp theo, ta sẽ chỉ ra tập K là tập đóng. Thật vậy, giả sử a là một điểm tụ của K, với mỗi số nguyên k ≥ 1, tồn tại một điểm xk trong
B a, k1 \ {a}. Từ 1 kxk − ak < k với mọi k ≥ 1, nên dãy {xk }k≥1 hội tụ tới a. Theo giả thiết, vì dãy {xk }k≥1 nằm trong K, nó có một dãy con hội tụ đến một số x0 ∈ K. Tuy nhiên, dãy {xk }k≥1 hội tụ tới a, do đó dãy {xk }k≥1 cũng hội tụ với a. Vì giới hạn là duy nhất, nên x0 = a và a ∈ K. Do đó, K là tập đóng. Vì K đóng và bị chặn nên K là tập compact.  Định lý 1.1.14 (xem [6]) Nếu K là tập hợp con của Rn , các điều kiện sau là tương đương: (i) Mỗi phủ mở của K đều có phủ con hữu hạn; (ii) K đóng và bị chặn; (iii) Mỗi tập hợp con vô hạn của K có điểm tụ trong K; (iv) Mỗi dãy trong K có dãy con hội tụ đến điểm của K. Do đó, K ⊂ R là tập compact nếu và chỉ nếu bất kỳ một trong những điều kiện ở trên đúng. 11 1.1.2 Dãy Cauchy Định nghĩa 1.1.15 Một dãy các điểm {xk }k≥1 trong Rn là một dãy Cauchy nếu có bất kỳ ε > 0, tồn tại một số nguyên k0 = k0 (ε) sao cho kxk − xm k < ε với k, m > k0 . Chúng ta có các bổ đề sau, và các chứng minh tương tự cho các dãy Cauchy trong R. Bổ đề 1.1.16 (xem [6]) Nếu {xk }k≥1 là dãy Cauchy trong Rn thì dãy {xk }k≥1 là bị chặn. Bổ đề 1.1.17 (xem [6]) Nếu {xk }k≥1 là dãy Cauchy trong Rn và dãy con {xki }i≥1 của {xk }k≥1 hội tụ, nghĩa là lim xki = x0 , thì dãy {xk }k≥1 cũng i→∞ hội tụ đến x0 . Bây giờ ta sẽ chỉ ra không gian tuyến tính định chuẩn Rn là không gian đầy đủ, nghĩa là một dãy hội tụ nếu và chỉ nếu nó là dãy Cauchy. Định nghĩa 1.1.18 Cho A là một tập hợp con khác rỗng bị chặn của Rn . Đường kính của A, gọi diam(A), được định nghĩa như sau: diam (A) = sup {kx − yk , x ∈ A, y ∈ A} . Nếu A không bị chặn ta định nghĩa diam (A) = ∞. Định lý 1.1.19 (xem [6]) Một tập khác rỗng A trong Rn và bao đóng A
của nó có cùng đường kính, nghĩa là, diam A =diam(A). Chứng minh. Từ A ⊂ A suy ra  sup {kx − yk : x ∈ A, y ∈ A} ≤ sup kx − yk : x ∈ A, y ∈ A ,
nên diam(A) ≤ diam A . Ngược lại, giả sử x0 ∈ A và y 0 ∈ A và đặt δ > 0 tùy ý. Khi đó tồn tại x ∈ A và y ∈ A sao cho kx − x0 k < δ 2 và δ ky − y 0 k < . 2 12 do đó kx0 − y 0 k ≤ kx0 − xk + kx − yk + ky − y 0 k ≤ diam (A) + δ, ∀x, y ∈ A. Nên
diam A ≤ diam (A) + δ
và do δ > 0 bé tùy ý nên ta có diam A ≤ diam(A).
Vậy ta được diam A = diam(A).  Định lý 1.1.20 (xem [6]) Một dãy {xk }k≥1 trong Rn hội tụ nếu và chỉ khi nó là dãy Cauchy. Chứng minh. Giả sử {xk }k≥1 là dãy Cauchy trong Rn và đặt Ak = {xk , xk+1 , xk+2 , . . . } với k = 1, 2, 3, . . . . Ta có A1 ⊃ Ak ⊃ Ak+1 và A1 ⊃ Ak ⊃ Ak+1 với k = 1, 2, 3, . . . . Vì A1 là bị chặn nên mỗi một tập Ak là đóng và bị chặn và do đó nó là tập compact. Từ định lý Nested cho tập hợp n Lấy x0 ∈ R sao cho x0 ∈ ∞ T k=1 ∞ T Ak là một tập compact khác rỗng. k=1 Ak . Dãy {xk }k≥1 là một dãy Cauchy, nên với mọi ε > 0 bé tùy ý, tồn tại một số nguyên k0 sao cho kxk − xj k < ε với k, j ≥ k0 . Mặt khác, k ≥ k0 và j ≥ k0 suy ra xk ∈ Ak0 và xj ∈ Ak0 nên diam(Ak0 ) < ε. Bây giờ, x0 ∈ Ak0 và x0 ∈ Ak0 ⊂ Ak0 với mọi k ≥ k0 . Do đó từ
diam Ak0 = diam(Ak0 ) ta có
kxk − x0 k ≤ diam Ak0 = diam (Ak0 ) ≤ ε khi k ≥ k0 , suy ra {xk }k≥1 hội tụ đến x0 . Ngược lại, dễ thấy bất kỳ dãy hội tụ trong Rn đều là dãy Cauchy.  13 1.2 Tập hợp lồi 1.2.1 Khái niệm và ví dụ Ta sẽ sử dụng ký hiệu như khoảng của đường thẳng thực và sử dụng cho thuật ngữ trong R, mặc dù (p, q) không là tập mở trong Rn ngoại trừ khi n = 1 như sau: (i) [p, q] là hình đóng nối p và q xác định bởi: [p, q] = {x ∈ Rn : x − (1 − µ) p + µq : 0 ≤ µ ≤ 1} . (ii) (p, q) là hình mở nối p và q: (p, q) = {x ∈ Rn : x − (1 − µ) p + µq : 0 < µ < 1} . (iii) [p, q), (p, q] là hình nửa mở nối p và q: [p, q) = {x ∈ Rn : x − (1 − µ) p + µq : 0 ≤ µ < 1} , (p, q] = {x ∈ Rn : x − (1 − µ) p + µq : 0 < µ ≤ 1} . Chú ý rằng vô hướng µ tăng từ µ = 0 tới µ = 1 , điểm x di chuyển dọc trên đường x = p đến đường x = q. Định nghĩa 1.2.1 Tập con C của Rn được gọi là tập lồi nếu nó chứa tất cả các đoạn thẳng được xác định bởi hai điểm bất kỳ của tập con C. Theo định nghĩa này thì tập rỗng, tập một điểm, không gian con là các tập lồi. Định lý 1.2.2 (xem [6]) Giả sử f là hàm tuyến tính khác không của Rn và β một số thực. Siêu phẳng Hβ = f −1 (β) = {x ∈ Rn : f (x) = β} và nửa không gian mở H = {x ∈ Rn : f (x) < β} là các tập lồi. 14 Chứng minh. Lấy x và y thuộc Hβ và 0 < λ < 1, ta sẽ chỉ ra rằng tổ hợp lồi λx+(1 − λ) y cũng thuộc Hβ . Thật vậy, vì f là tuyến tính và x, y ∈ Hβ , nên f (λx + (1 − λ) y) = λf (x) + (1 − λ) f (y) = λβ + (1 − λ) β = β suy ra λx + (1 − λ) y ∈ Hβ . Tương tự lấy x và y thuộc H và 0 < λ < 1. Vì λ > 0 và 1 − λ > 0, ta có f (λx + (1 − λ) y) = λf (x) + (1 − λ) f (y) < λβ + (1 − λ) β = β suy ra λx + (1 − λ) y ∈ H.  1.2.2 Tính chất của tập lồi Nếu K là một tập hợp trong Rn thì αK := {αx ∈ Rn : x ∈ K} cũng là tập hợp trong Rn . Nếu α > 0, thì tập αK + x0 được gọi là phép vị tự dương của K. Định lý 1.2.3 (xem [6]) Nếu [p, q] là một hình đóng nối p và q trong Rn thì (a) [p, q] + x0 = [p + x0 , q + x0 ] với mọi x0 ∈ Rn , và (b) α [p, q] = [αp, αq] với mọi số thực α 6= 0. Chứng minh. (a) Ta có x ∈ [p, q] + x0 nếu và chỉ nếu tồn tại số λ với 0 ≤ λ ≤ 1 sao cho x = (1 − λ) p + λq + x0 = (1 − λ) p + λq + (1 − λ) x0 + λx0 = (1 − λ) (p + x0 ) + λ (q + x0 ) . Điều này xảy ra nếu và chỉ nếu x ∈ [p + x0 , q + x0 ]. Vậy [p, q] + x0 = [p + x0 , q + x0 ] với mọi x0 ∈ Rn . 15 (b) Phần tử x ∈ α [p, q] nếu và chỉ nếu tồn tại số λ với 0 ≤ λ ≤ 1 sao cho x = α [(1 − λ)p + λq] = (1 − λ) αp + λαq. Điều này xảy ra nếu x ∈ [αp, αq]. Khi đó α [p, q] = [αp, αq].  Hệ quả 1.2.4 (xem [6]) Nếu C là một tập con lồi của Rn thì C + x0 và αC là các tập hợp lồi với mọi x0 ∈ Rn và α ∈ Rn . Chứng minh. Lấy p và q là các điểm tùy ý trong tập C + x0 . Khi đó, p − x0 và q − x0 là các điểm thuộc C. Vì C là tập hợp lồi nên đoạn thẳng [p − x0 , q − x0 ] thuộc C. Theo định lý trên, [p − x0 , q − x0 ] + x0 = [p − x0 + x0 , q − x0 + x0 ] = [p, q] . Suy ra [p, q] ⊂ C + x0 , và vì p và q là các điểm tùy ý của của C + x0 nên C + x0 là tập lồi.  Nếu α = 0 thì αC = 0 là lồi (kể cả khi C không lồi), vì thế ta chỉ cần xét trường hợp α 6= 0. Lấy p và q là hai điểm tùy ý trong αC, khi đó p = αx và q = αy với x và y là hai điểm nào đó trong C. Vì C là tập lồi nên [x, y] ⊂ C và α [x, y] ⊂ αC. Từ định lý trên thì [p, q] ⊂ αC, do đó αC là tập lồi.  Từ hệ quả trước, giúp chúng ta không gặp phải các vấn đề về tìm tính lồi. Ví dụ để chứng minh rằng hình cầu B (x0 , p) là lồi, ta cần chú ý đến sự phân bố và tích vô hướng thích hợp. Ta sẽ chứng minh hình cầu đơn vị

mở B 0, 1 là tập hợp lồi. Thật vậy nếu x và y nằm trong B 0, 1 , ta chỉ
cần chứng minh rằng nếu 0 ≤ λ ≤ 1 thì (1 − λ) x + λy cũng thuộc B 0, 1 . Ta sử dụng bất đẳng thức tam giác: k(1 − λ) x + λyk ≤ k(1 − λ) xk + kλyk = (1 − λ) kxk + λ kyk < (1 − λ) + λ = 1. 16

Để chứng minh rằng (1 − λ) x + λy ∈ B 0, 1 khi x, y ∈ B 0, 1 và 0 ≤ λ ≤ 1. Định lý tiếp theo, mà đã được đề cập và chứng minh trong chương một đã chỉ ra rằng tính lồi được bảo toàn dưới các đường giao nhau. Thêm vào đó, họ F trong điều kiện của định lý có thể hữu hạn hoặc vô hạn. Định lý 1.2.5 (xem [6]) Nếu F là họ các tập con lồi khác rỗng của Rn thì T tập C = {A : A ∈ F } là tập lồi. Chứng minh. Lấy x và y là hai điểm tùy ý trong C. Ta chứng minh rằng [x, y] ⊂ C. Vì C là giao của tất cả các phần tử của F nên x ∈ A với mỗi A ∈ F và y ∈ A với mỗi A ∈ F , do đó tập A là lồi. Từ đó suy ra T [x, y] ⊂ C = {A : A ∈ F } và C là tập lồi.   Ví dụ 1.2.6 Chứng minh rằng tập S = (x, y) ∈ R2 : y ≥ x1 , x > 0 là tập lồi. Chứng minh. S = {(x, y) ∈ R2 : y ≥ 1/x; 0 < x < ∞} Chứng minh sau đây sử dụng bất đẳng thức a + a1 ≥ 2 với mọi a > 0, đẳng thức xảy ra nếu và chỉ nếu a = 1. Giả sử p1 = (x1 , y1 ) , p2 = (x2 , y2 ) ∈ C và 0 ≤ λ ≤ 1. Nếu x1 > 0 và x2 > 0 thì (1 − λ) x1 + λx2 > 0. Suy ra, [(1 − λ) x1 + λx2 ] [(1 − λ) y1 + λy2 ] = (1 − λ)2 x1 y1 + λ (1 − λ) [x1 y2 + x2 y1 ] + λ2 x2 y2 . 17 Vì x1 y1 ≥ 1, x2 y2 ≥ 1, và x1 y2 + x2 y1 ≥ x1 1 1 + x2 ≥ 2 x2 x1 nên [(1 − λ) x1 + λx2 ] [(1 − λ) y1 + λy2 ] ≥ (1 − λ)2 + 2λ (1 − λ) + λ2 = [(1 − λ) + λ]2 = 1. Mặt khác, (1 − λ) y1 + λy2 ≥ 1 (1 − λ) x1 + λx2 nên (1 − λ) p1 + λp2 = ((1 − λ) x1 + λx2 , (1 − λ) y1 + λy2 ) ∈ S và S là tập lồi.  Một trong những lý do mà tập lồi được sử dụng là tính lồi được bảo toàn qua các phép biến đổi tuyến tính. Định nghĩa 1.2.7 Phép biến đổi tuyến tính là ánh xạ T : Rn → Rn thỏa mãn (i) T (x + y) = T (x) + T (y) với mọi x, y ∈ Rn , và (ii) T (αx) = αT (x) với mọi x ∈ Rn với mọi α ∈ R. Ta có định nghĩa tương đương sau đây. Định nghĩa 1.2.8 Ánh xạ T : Rn → Rn là phép biến đổi tuyến tính nếu T (αx + βy) = αT (x) + βT (y) với mọi x, y ∈ Rn và với mọi α và β thuộc R. Định lý 1.2.9 (xem [6]) Ảnh của phân đoạn đường thẳng dưới phép biến đổi tuyến tính là phân đoạn đường thẳng. Chứng minh. Giả sử T là phép biến đổi tuyến tính và cho phân đoạn đường thẳng [p, q]. Ta sẽ chứng minh {T (x) ∈ Rn : x ∈ [p, q]} = [T (p) , T (q)] .