(91) 350-9520 support@omarine.org M-F: 7 AM - 7 PM; Weekends: 9 AM - 5 PM

Quan hệ thứ tự(Order relation)

Quan hệ thứ tự bộ phận(Partial order)

1. Các khái niệm chung

Định nghĩa. Một quan hệ hai ngôi ≤ trên một tập P được gọi là một quan hệ thứ tự bộ phận(không ngặt) nếu thỏa các điều kiện dưới đây với mọi a, b, c trong P:

  • a ≤ a                                                 (phản xạ)
  • nếu a ≤ b và b ≤ a thì a = b           (phản đối xứng)
  • nếu a ≤ b và b ≤ c thì a ≤ c            (bắc cầu)

Kí hiệu ≤ của quan hệ hai ngôi chuẩn ≤ được dùng làm đại diện cho các quan hệ khác trong định nghĩa. a ≤ b được hiểu là a đứng trước b, không phải là a nhỏ hơn hoặc bằng b theo nghĩa thông thường. Ví dụ đối với quan hệ ≥ thì 2 ≥ 1, 2 đứng trước 1 và trong trường hợp này 2 nhỏ hơn 1. Nếu sử dụng kí hiệu quan hệ chuẩn ≤, thì 2 ≤ 1.

Tương đương, một quan hệ thứ tự bộ phận là một quan hệ bán thứ tự phản đối xứng(xem bên dưới).

Một tập với một quan hệ thứ tự bộ phận được gọi là tập có thứ tự bộ phận hay tập được sắp thứ tự bộ phận (partially ordered set, poset). Trong trường hợp để cho gọn, chúng ta viết poset thay cho tập có thứ tự bộ phận. Một poset P khi cần mô tả đi cùng với quan hệ ≤ được kí hiệu là (P, ≤). Ví dụ, 0 là phần tử lớn nhất của ({0, 1, 2, 4, 6}, |).

Hai phần tử a, b của một tập có thứ tự bộ phận là so sánh được nếu a ≤ b hoặc b ≤ a. Nếu không, chúng là không so sánh được. Một quan hệ thứ tự bộ phận trong đó mọi cặp phần tử đều so sánh được, được gọi là quan hệ thứ tự toàn phần(total order) hay quan hệ thứ tự tuyến tính(linear order). Như vậy, quan hệ thứ tự toàn phần chỉ là một trường hợp đặc biệt của quan hệ thứ tự bộ phận. Tập đi cặp với quan hệ thứ tự toàn phần được gọi là tập được sắp thứ tự toàn phần.

warning_32Một số tài liệu trong nước gọi quan hệ thứ tự bộ phậnquan hệ thứ tự, như vậy là không mô tả đầy đủ ý nghĩa của ngữ cảnh. Mặt khác, điều đó bó hẹp một quan hệ thứ tự nói chung vào ba điều kiện của quan hệ thứ tự bộ phận.

Nếu một poset P không được sắp thứ tự toàn phần thì sẽ tồn tại những phần tử của P không so sánh được với nhau. Tuy nhiên tất cả các phần tử của P đều thỏa các điều kiện của quan hệ thứ tự bộ phận. Chúng ta hãy xem, chẳng hạn điều kiện phản đối xứng: điều kiện này chỉ yêu cầu nếu a và b là so sánh được thì mới áp dụng, nếu không là thỏa.

warning_32Trong cuốn sách Toán học cao cấp, tập 1, xuất bản năm 1998, trang 18, quan hệ thứ tự bộ phận được coi là quan hệ thứ tự không toàn phần, làm cho quan hệ thứ tự toàn phần tách rời khỏi quan hệ thứ tự bộ phận. Điều này làm mất tính tổng quát của quan hệ thứ tự bộ phận, dẫn đến làm mất đi ý nghĩa của các khái niệm, định lý, bổ đề và các hệ quả có liên quan.

2. Phần tử lớn nhất và bé nhất

Cho P là một poset. Phần tử g ϵ P được gọi là phần tử lớn nhất của P nếu x ≤ g ∀x ϵ P. Phần tử m ϵ P được gọi là phần tử bé nhất của P nếu x ≥ m ∀x ϵ P.

Về tính duy nhất của phần tử lớn nhất/bé nhất: một poset có thể không có phần tử lớn nhất/bé nhất, kể cả khi nó là một tập được sắp thứ tự toàn phần, ví dụ (ℝ, ≤) không có cả phần tử lớn nhất và bé nhất; (ℕ, ≤) không có phần tử lớn nhất. Nhưng nếu nó có, thì phần tử lớn nhất/bé nhất của nó là duy nhất. Tính duy nhất của phần tử lớn nhất/bé nhất liên quan tới định nghĩa về tập hợp. Ban đầu, hẳn chúng ta nghĩ tập hợp là tuyển tập các đối tượng theo cách tự nhiên. Vậy thì nó có thể có những phần tử trùng nhau. Chẳng hạn với hai màu xanh, một màu đỏ, chúng ta có tập {xanh, xanh, đỏ}. Tuy nhiên, các phần tử trùng nhau làm giảm tính phân lớp đối tượng và ảnh hưởng đến các phép toán về tập hợp. Ví dụ, nếu chúng ta có hai tập {1, 1, 2} và {1, 2} được coi là hai tập khác nhau thì có thể là

{1, 1, 2} \ {1, 2} = {1}

{1, 2} và {1} là các tập bù của nhau nhưng chúng có giao khác rỗng!

Cho nên các phần tử trùng nhau cần được coi là một phần tử. Do đó {1, 1, 2} = {1, 2}.

Vậy tập hợp có thể được định nghĩa như sau:

Một tập hợp là một tuyển tập xác định rõ của các đối tượng phân biệt. Mỗi đối tượng được gọi là một phần tử của tập hợp.

Vấn đề cần mô tả các đối tượng trùng nhau có thể được xử lý bằng ánh xạ từ một tập chỉ số vào tập giá trị mong muốn, như họ đánh chỉ số của các tập.

Chúng ta đi tới kết luận: một tập poset chỉ có nhiều nhất là một phần tử lớn nhất, một phần tử bé nhất.

3. Các phần tử cực đại và cực tiểu

Cho P là một poset. Phần tử g ϵ P được gọi là một phần tử cực đại trong P nếu nó không nhỏ hơn phần tử nào của P. Tương tự, phần tử m ϵ P được gọi là một phần tử cực tiểu trong P nếu nó không lớn hơn phần tử nào của P. Chúng ta thấy rằng phần tử cực đại rất khác với phần tử lớn nhất(tương tự phần tử cực tiểu đối với phần tử bé nhất). Phần tử lớn nhất phải so sánh được với tất cả các phần tử của P trong khi đối với phần tử cực đại, nó có thể “không nhỏ hơn” một số phần tử của P mà không so sánh được với nó. Do đó, trong khi P chỉ có nhiều nhất là một phần tử lớn nhất, thì P có thể có nhiều phần tử cực đại trong trường hợp nó là một poset không được sắp thứ tự toàn phần. Nói cách khác, với tập được sắp thứ tự toàn phần, phần tử lớn nhất và phần tử cực đại là như nhau.

Nói chung, phần tử lớn nhất của P nếu có, là một phần tử cực đại của P, nhưng ngược lại thì không đúng. Tương tự, phần tử bé nhất của P là một phần tử cực tiểu của P.

4. Cận trên và cận dưới

Cho P là một poset. Với một tập con A của P, một phần tử a ϵ P là một cận trên của A nếu x ≤ a ∀x ϵ A. Cận trên của A không nhất thiết ở trong A. Một cận trên a của A được gọi là cận trên bé nhất(least upper bound- LUB, supremum) của A, kí hiệu sup A, nếu mọi cận trên y của A trong P đều thỏa y ≥ a. Nếu A có cận trên, chúng ta nói A bị chặn trên.

Tương tự, một phần tử b ϵ P là một cận dưới của một tập con A của P nếu x ≥ b ∀x ϵ A. Một cận dưới b của A được gọi là cận dưới lớn nhất(greatest lower bound- GLB, infimum) của A, kí hiệu inf A, nếu mọi cận dưới z của A trong P đều thỏa z ≤ b. Nếu A có cận dưới, chúng ta nói A bị chặn dưới.

Tập con A được gọi là giới nội(bounded), nếu A vừa bị chặn trên vừa bị chặn dưới.

5. Xích

Một xích ngụ ý một tập được sắp thứ tự toàn phần, có thể là một tập con được sắp thứ tự toàn phần trong một tập có thứ tự bộ phận nào đó. Như vậy, tất cả các mắt xích trong một xích là so sánh được và điều này có ý nghĩa quan trọng đối với xích vô hạn.

Một tập con của một poset mà không có cặp hai phần tử khác nhau nào so sánh được, được gọi là một kháng xích(antichain).

Một xích cực đại là một xích không là tập con thực sự của một xích nào khác. Tương tự, một kháng xích cực đại là một kháng xích không là tập con thực sự của một kháng xích nào khác.

(C1 là tập con thực sự của C2 có nghĩa là C1 ⊊ C2 ⇔ C1 ⊆ C2 ⋀ C1 ≠ C2)

Tương đương, một xích C của một poset P là cực đại nếu không có phần tử nào trong P \ C so sánh được với mọi phần tử của C. Một kháng xích A của một poset P là cực đại nếu không có phần tử nào trong P \ A không so sánh được với mọi phần tử của A.

Một xích/kháng xích lớn nhất là xích/kháng xích có cỡ lớn nhất có thể có. Cụm từ “có thể có” được sử dụng vì hai lý do: thứ nhất, có thể tồn tại nhiều xích lớn nhất, khi đó xích lớn nhất là xích có cỡ không nhỏ hơn xích nào khác, thứ hai, trong trường hợp một xích lớn nhất là vô hạn, nó phải là cực đại. Tương tự như vậy đối với kháng xích.

Chú ý là các thuộc tính “cực đại”, “lớn nhất”, “nhỏ hơn” dùng cho xích và kháng xích được hiểu theo nghĩa thông thường, không phụ thuộc vào quan hệ. Để phân biệt rõ hơn, chúng ta gọi xích lớn nhất là xích dài nhất, kháng xích lớn nhất là kháng xích to nhất.

Cỡ của xích dài nhất được coi là chiều cao của poset. Cỡ của kháng xích to nhất được coi là chiều rộng của poset.

Nếu chúng ta có thể phân hoạch một poset P thành k xích, thì k không thể nhỏ hơn chiều rộng của P, vì nếu như thế sẽ tồn tại một xích có ít nhất 2 phần tử của một kháng xích to nhất A, và A không còn là một kháng xích. Định lý Dilworth phát biểu rằng một poset hữu hạn P luôn có thể được phân hoạch thành các xích với số xích bằng chiều rộng của P. Một phiên bản của định lý cho poset vô hạn phát biểu rằng một poset có chiều rộng hữu hạn w nếu và chỉ nếu nó có thể được phân hoạch thành w xích. Định lý Mirsky phát biểu rằng bất kỳ poset P có chiều cao hữu hạn có thể được phân hoạch thành các kháng xích, trong đó số kháng xích nhỏ nhất có thể phân hoạch được bằng với chiều cao của P.

6. Bổ đề Zorn

Cho rằng một tập có thứ tự bộ phận P có tính chất là mọi xích có một cận trên trong P. Thì P chứa ít nhất một phần tử cực đại.

Luận bàn. Bổ đề là đúng tầm thường khi tập P là rỗng. Tập rỗng là một xích rỗng và yêu cầu về cận trên là không đạt được vì cận trên là một phần tử nhưng tập rỗng không có phần tử nào, do đó được bỏ qua. Nói cách khác, bổ đề không sai khi P = ∅.

Trường hợp P không rỗng, chúng ta xét về xích rỗng. Bây giờ thì mọi phần tử của P đều là cận trên của xích rỗng, do đó xích rỗng có cận trên và không ảnh hưởng tới điều kiện của bổ đề, kết quả chỉ còn phụ thuộc vào các xích không rỗng của P, là tồn tại, vì P không rỗng.

Như vậy, nếu P là rỗng hoặc P có xích rỗng đều không làm thay đổi khẳng định của bổ đề. Nếu chúng ta chỉ cần kết luận “P chứa ít nhất một phần tử cực đại” khi có đủ giả thiết, bạn hãy hình dung trong một thuật toán, sẽ không có vấn đề. Tuy nhiên, nếu chúng ta áp dụng bổ đề trong một chứng minh toán học nào đấy như thể một yếu tố nhất định đã tồn tại, trong khi lại rơi vào trường hợp P là rỗng hoặc P có xích rỗng như trên thì sẽ không hay. Điều này dễ mắc bởi vì khi làm việc với bổ đề, chúng ta thường chạm phải những tập vô hạn và các lập luận trừu tượng, chẳng hạn lấy cận trên bằng hợp vô hạn của các tập vô hạn, thường không nhắc nhở chúng ta về sai sót. Cho nên cần có một phát biểu tương đương, khác một chút nhưng hoàn toàn chỉ mang ý nghĩa thận trọng:

Cho rằng một tập có thứ tự bộ phận P không rỗng có tính chất là mọi xích không rỗng có một cận trên trong P. Thì P chứa ít nhất một phần tử cực đại.

Bổ đề này dường như chỉ ra mỗi xích có thể tìm được một xích cực đại chứa nó. Rồi “mọi xích có một cận trên trong P” là tương đương với “mọi xích cực đại có cận trên trong P”, vì cận trên của một xích cực đại cũng là một cận trên của các xích con của nó. Cho C là một xích cực đại không rỗng. Cận trên của C nếu có là phần tử lớn nhất của nó. Vì không còn phần tử nào ở ngoài C so sánh được với tất cả các phần tử của nó, cận trên của C là duy nhất, và cũng là một phần tử cực đại của P. Như vậy chỉ cần chỉ ra một xích cực đại không rỗng bị chặn trên là đủ để P có một phần tử cực đại. Chúng ta có một phiên bản mạnh hơn một chút của bổ đề Zorn, giống như trên, loại bỏ trường hợp P là rỗng:

Nếu mỗi xích cực đại không rỗng trong một poset P không rỗng bị chặn trên thì P có một phần tử cực đại tương ứng.

Phát biểu dưới đây là yếu hơn, vì yêu cầu “mọi xích cực đại”, nhưng vẫn còn mạnh hơn bổ đề Zorn; tuy nhiên, không cần điều kiện “xích cực đại không rỗng” vì một phần tử của P đã được chỉ ra:

Nếu mọi xích cực đại trong một poset P không rỗng bị chặn trên thì bất kỳ phần tử nào của P đều nhỏ hơn hoặc bằng một phần tử cực đại nào đó của P.

Nếu chúng ta xuất phát từ một xích A0 chưa chắc là xích cực đại, chúng ta có thể đi tới xích cực đại của nó như sau: vì mọi xích có cận trên, do đó A0 có cận trên, chúng ta tìm một cận trên a0 ∉ A0. Nếu không tìm được thì A0 có cận trên duy nhất là phần tử lớn nhất của nó, và A0 là xích cực đại hoặc đoạn xích phía trên của xích cực đại. Nếu tìm được, chúng ta thêm cận trên a0 vào A0 và được tập A1 = A0 ⋃ {a0}. Vì a0 là cận trên của A0 nên nó so sánh được với tất cả các phần tử của A0. Do đó A1 cũng là một xích. Quá trình lặp lại như vậy sẽ tiến dần tới cận trên của xích cực đại. Xích cuối cùng, có thể không hoàn toàn là xích cực đại, nhưng nó chứa cận trên của xích cực đại và trong phương diện chỉ cần xét cận trên, coi như xích cực đại. 

Bây giờ, tưởng tượng rằng chúng ta cắt đi đoạn dưới cùng của mỗi xích cực đại tại mỗi điểm xác định đối với xích nào không bị chặn dưới, chúng trở thành các tập được sắp thứ tự tốt(xem bên dưới). Và chúng ta lại có phát biểu tương đương với phát biểu kế trên. Giống như đối với xích, một tập được sắp thứ tự tốt cũng có thể là rỗng. Do đó trường hợp P là rỗng vẫn cần bỏ qua:

Nếu mọi tập con được sắp thứ tự tốt trong một poset P không rỗng bị chặn trên thì bất kỳ phần tử nào của P đều nhỏ hơn hoặc bằng một phần tử cực đại nào đó của P.

Tập được sắp thứ tự tốt(well-ordered set)

Quan hệ thứ tự tốt trên một tập S là một quan hệ thứ tự toàn phần trên S với thuộc tính là mọi tập con không rỗng của S có một phần tử bé nhất trong quan hệ thứ tự này. Tập S cùng với quan hệ thứ tự tốt được gọi là tập được sắp thứ tự tốt.

Tập ℕ với quan hệ thứ tự chuẩn ≤ là tập được sắp thứ tự tốt. Tập ℤ với quan hệ thứ tự chuẩn ≤ không phải là tập được sắp thứ tự tốt bởi vì nó không có phần tử bé nhất.

Quan hệ bán thứ tự(Preorder, quasiorder)

Một quan hệ bán thứ tự là một quan hệ hai ngôi có tính phản xạ và bắc cầu. Quan hệ bán thứ tự không nhất thiết phản đối xứng hay đối xứng. Nếu một quan hệ bán thứ tự thỏa phản đối xứng, nó là một quan hệ thứ tự bộ phận; nếu đối xứng, nó là một quan hệ tương đương. Nói cách khác, quan hệ bán thứ tự tổng quát hơn, cả hai quan hệ thứ tự bộ phận và quan hệ tương đương đều là những trường hợp đặc biệt của quan hệ bán thứ tự. Thuật ngữ bán thứ tự được hiểu là quan hệ đó gần như là quan hệ thứ tự bộ phận, nhưng không hoàn toàn, chỉ “một nửa”.

Định nghĩa. Một quan hệ hai ngôi ≤ trên một tập P được gọi là một quan hệ bán thứ tự nếu ≤ thỏa các điều kiện dưới đây với mọi a, b, c trong P:

  • a ≤ a                                             (phản xạ)
  • nếu a ≤ b và b ≤ c thì a ≤ c        (bắc cầu)

Một tập với một quan hệ bán thứ tự được gọi là tập bán thứ tự hay tập được sắp bán thứ tự (preordered set, proset).

Một ví dụ cho quan hệ bán thứ tự là quan hệ tinh chế trên tập các phủ trong một không gian tôpô. Nếu các phủ tinh chế là họ các tập con của các tập trong phủ nguồn, thì quan hệ tinh chế là quan hệ thứ tự bộ phận. Hai phủ C và D là phủ tinh chế của nhau chỉ khi chúng bằng nhau. Nhưng nếu chúng ta lấy một bản sao C’ của C, rồi thêm vào C’ một tập con của một tập nào đó trong C’, thì C tinh chế C’ và C’ tinh chế C nhưng chúng không bằng nhau. Đó là quan hệ tương đương. Điều này dẫn đến một hệ quả là nếu chúng ta thêm vào một phủ tinh chế các tập con của các tập của nó thì không làm thay đổi bản chất của phủ tinh chế.

Quan hệ thứ tự bộ phận ngặt(Strict partial order)

Một quan hệ hai ngôi < trên một tập P được gọi là một quan hệ thứ tự bộ phận ngặt nếu thỏa các điều kiện dưới đây với mọi a, b, c trong P:

  • không a < a                                 (bất phản xạ)
  • nếu a < b thì không b < a          (bất đối xứng)
  • nếu a < b và b < c thì a < c        (bắc cầu)

Quan hệ thứ tự bộ phận ngặt còn được gọi là quan hệ thứ tự bộ phận bất phản xạ.

 

Advertisements

Gửi phản hồi

%d bloggers like this: