Quan hệ thứ tự(Order relation)

Quan hệ trật tự cỗ phận(Partial order)

1. Các định nghĩa chung

Bạn đang xem: quan hệ thứ tự trong toán rời rạc

Định nghĩa. Một mối liên hệ nhì ngôi ≤ bên trên một luyện Phường được gọi là 1 trong những mối liên hệ trật tự cỗ phận(không ngặt) nếu như thỏa những ĐK sau đây với từng a, b, c vô 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 mối liên hệ nhì ngôi chuẩn chỉnh ≤ được sử dụng thực hiện đại diện thay mặt cho những mối liên hệ không giống vô khái niệm. a ≤ b được hiểu là a đứng trước b, ko cần là a nhỏ rộng lớn hoặc vày b theo đuổi nghĩa thường thì. Ví dụ so với mối liên hệ ≥ thì 2 ≥ 1, 2 đứng trước 1 và vô tình huống này 2 nhỏ rộng lớn 1. Nếu dùng kí hiệu mối liên hệ chuẩn chỉnh ≤, thì 2 ≤ 1.

Tương đương, một mối liên hệ trật tự phần tử là 1 trong những mối liên hệ buôn bán trật tự phản đối xứng(xem mặt mày dưới).

Một luyện với cùng 1 mối liên hệ trật tự phần tử được gọi là luyện với trật tự phần tử hoặc luyện được chuẩn bị trật tự phần tử (partially ordered mix, poset). Trong tình huống làm cho gọn gàng, tất cả chúng ta ghi chép poset thay cho mang đến tập với trật tự cỗ phận. Một poset Phường khi cần thiết tế bào mô tả chuồn cùng theo với mối liên hệ ≤ được kí hiệu là (P, ≤). Ví dụ, 0 là thành phần lớn số 1 của ({0, 1, 2, 4, 6}, |).

Hai thành phần a, b của một luyện với trật tự phần tử là đối chiếu được nếu như a ≤ b hoặc b ≤ a. Nếu ko, bọn chúng là ko đối chiếu được. Một mối liên hệ trật tự phần tử vô tê liệt từng cặp thành phần đều đối chiếu được, được gọi là quan hệ trật tự toàn phần(total order) hoặc mối liên hệ trật tự tuyến tính(linear order). Như vậy, mối liên hệ trật tự toàn phần chỉ là 1 trong những tình huống đặc trưng của mối liên hệ trật tự phần tử. Tập chuồn cặp với mối liên hệ trật tự toàn phần được gọi là tập được chuẩn bị trật tự toàn phần.

warning_32 Một số tư liệu nội địa gọi quan hệ trật tự cỗ phận là quan hệ loại tự, vì vậy là ko tế bào mô tả vừa đủ chân thành và ý nghĩa của văn cảnh. Mặt không giống, điều này eo hẹp một mối liên hệ trật tự rằng cộng đồng vô tía ĐK của mối liên hệ trật tự phần tử.

Nếu một poset Phường ko được chuẩn bị trật tự toàn phần thì tiếp tục tồn bên trên những thành phần của Phường ko đối chiếu được cùng nhau. Tuy nhiên toàn bộ những thành phần của Phường đều thỏa những ĐK của mối liên hệ trật tự phần tử. Chúng tao hãy coi, ví dụ điển hình ĐK phản đối xứng: ĐK này chỉ đòi hỏi nếu như a và b là đối chiếu được thì mới có thể vận dụng, còn nếu như không là thỏa.

warning_32 Trong cuốn sách Toán học tập thời thượng, luyện 1, xuất phiên bản năm 1998, trang 18, mối liên hệ trật tự phần tử được xem là mối liên hệ trật tự ko toàn phần, thực hiện mang đến mối liên hệ trật tự toàn phần tách tách ngoài mối liên hệ trật tự phần tử. Như vậy làm mất đi tính tổng quát tháo của mối liên hệ trật tự phần tử, kéo theo làm mất đi chuồn chân thành và ý nghĩa của những định nghĩa, quyết định lý, té đề và những hệ ngược với tương quan.

2. Phần tử lớn số 1 và bé bỏng nhất

Cho Phường là 1 trong những poset. Phần tử g ϵ Phường được gọi là thành phần lớn số 1 của Phường nếu như x ≤ g ∀x ϵ Phường. Phần tử m ϵ Phường được gọi là thành phần bé bỏng nhất của Phường nếu như x ≥ m ∀x ϵ Phường.

Về tính có một không hai của thành phần rộng lớn nhất/bé nhất: một poset rất có thể không tồn tại thành phần rộng lớn nhất/bé nhất, bao gồm khi nó là 1 trong những luyện được chuẩn bị trật tự toàn phần, ví dụ (ℝ, ≤) không tồn tại cả thành phần lớn số 1 và bé bỏng nhất; (ℕ, ≤) không tồn tại thành phần lớn số 1. Nhưng nếu như nó với, thì thành phần rộng lớn nhất/bé nhất của chính nó là có một không hai. Tính có một không hai của thành phần rộng lớn nhất/bé nhất tương quan cho tới khái niệm về giao hội. Ban đầu, hẳn tất cả chúng ta nghĩ về giao hội là tuyển chọn luyện những đối tượng người sử dụng Theo phong cách ngẫu nhiên. Vậy thì nó rất có thể với những thành phần trùng nhau. Chẳng hạn với nhì greed color, một red color, tất cả chúng ta với luyện {xanh, xanh lơ, đỏ}. Tuy nhiên, những thành phần trùng nhau thực hiện rời tính phân lớp đối tượng người sử dụng và tác động cho tới những luật lệ toán về giao hội. Ví dụ, nếu như tất cả chúng ta với nhì luyện {1, 1, 2} và {1, 2} được xem là nhì luyện không giống nhau thì rất có thể là

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

{1, 2} và {1} là những luyện bù của nhau tuy nhiên bọn chúng với gửi gắm không giống rỗng!

Cho nên những thành phần trùng nhau cần phải xem là một thành phần. Do tê liệt {1, 1, 2} = {1, 2}.

Vậy giao hội rất có thể được khái niệm như sau:

Một giao hội là 1 trong những tuyển chọn luyện xác lập rõ rệt của những đối tượng người sử dụng phân biệt. Mỗi đối tượng người sử dụng được gọi là 1 trong những thành phần của giao hội.

Vấn đề cần thiết tế bào mô tả những đối tượng người sử dụng trùng nhau rất có thể được xử lý vày ánh xạ từ là 1 luyện chỉ số vô luyện độ quý hiếm mong ước, như bọn họ tấn công chỉ số của những luyện.

Chúng tao tiếp cận kết luận: một luyện poset chỉ mất tối đa là 1 trong những thành phần lớn số 1, một thành phần bé bỏng nhất.

3. Các thành phần cực to và rất rất tiểu

Cho Phường là 1 trong những poset. Phần tử g ϵ Phường được gọi là 1 trong những thành phần cực to vô Phường nếu như nó không hề nhỏ rộng lớn thành phần này của Phường. Tương tự động, thành phần m ϵ Phường được gọi là 1 trong những thành phần rất rất tè vô Phường nếu như nó ko to hơn thành phần này của Phường. Chúng tao thấy rằng thành phần cực to rất rất không giống với thành phần rộng lớn nhất(tương tự động thành phần rất rất tè so với thành phần bé bỏng nhất). Phần tử lớn số 1 cần đối chiếu được với toàn bộ những thành phần của Phường trong những lúc so với thành phần cực to, nó rất có thể “không nhỏ hơn” một trong những thành phần của Phường nhưng mà ko đối chiếu được với nó. Do tê liệt, trong những lúc Phường chỉ mất tối đa là 1 trong những thành phần lớn số 1, thì Phường rất có thể có không ít thành phần cực to vô tình huống nó là 1 trong những poset ko được chuẩn bị trật tự toàn phần. Nói cách tiếp, với luyện được chuẩn bị trật tự toàn phần, thành phần lớn số 1 và thành phần cực to là như nhau.

Nói cộng đồng, thành phần lớn số 1 của Phường nếu như với, là 1 trong những thành phần cực to của Phường, tuy nhiên ngược lại thì ko trúng. Tương tự động, thành phần bé bỏng nhất của Phường là 1 trong những thành phần rất rất tè của Phường.

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

Cho Phường là 1 trong những poset. Với một luyện con cái A của Phường, một thành phần a ϵ Phường là 1 trong những cận bên trên của A nếu như x ≤ a ∀x ϵ A. Cận bên trên của A ko nhất thiết ở vô A. Một cận bên trên a của A được gọi là cận bên trên bé bỏng nhất(least upper bound- LUB, supremum) của A, kí hiệu sup A, nếu như từng cận bên trên nó của A vô Phường đều thỏa nó ≥ a. Nếu A với cận bên trên, tất cả chúng ta rằng A bị ngăn bên trên.

Tương tự động, một thành phần b ϵ Phường là 1 trong những cận bên dưới của một luyện con cái A của Phường nếu như x ≥ b ∀x ϵ A. Một cận bên dưới b của A được gọi là cận bên dưới rộng lớn nhất(greatest lower bound- GLB, infimum) của A, kí hiệu inf A, nếu như từng cận bên dưới z của A vô Phường đều thỏa z ≤ b. Nếu A với cận bên dưới, tất cả chúng ta rằng A bị ngăn bên dưới.

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

5. Xích

Một xích ý niệm một luyện được chuẩn bị trật tự toàn phần, rất có thể là 1 trong những luyện con cái được chuẩn bị trật tự toàn phần vô một luyện với trật tự phần tử này tê liệt. Như vậy, toàn bộ những đôi mắt xích vô một xích là đối chiếu được và điều này còn có chân thành và ý nghĩa cần thiết so với xích vô hạn.

Một luyện con cái của một poset nhưng mà không tồn tại cặp nhì thành phần không giống nhau này đối chiếu được, được gọi là 1 trong những kháng xích(antichain).

Một xích cực to là 1 trong những xích ko là luyện con cái thực sự của một xích này không giống. Tương tự động, một kháng xích cực to là 1 trong những kháng xích ko là luyện con cái thực sự của một kháng xích này không giống.

Xem thêm: tô màu chú bộ đội

(C₁ là luyện con cái thực sự của C₂ Tức là C₁ ⊊ C₂ ⇔ C₁ ⊆ C₂ ⋀ C₁ ≠ C₂)

Tương đương, một xích C của một poset Phường là cực to nếu như không tồn tại thành phần này vô Phường \ C đối chiếu được với từng thành phần của C. Một kháng xích A của một poset Phường là cực to nếu như không tồn tại thành phần này vô Phường \ A không đối chiếu được với từng thành phần của A.

Một xích/kháng xích lớn số 1 là xích/kháng xích với cỡ lớn số 1 rất có thể với. Cụm kể từ “có thể có” được dùng vì thế nhì lý do: loại nhất, rất có thể tồn trên rất nhiều xích lớn số 1, khi tê liệt xích lớn số 1 là xích với cỡ không hề nhỏ rộng lớn xích này không giống, loại nhì, vô tình huống một xích lớn số 1 là vô hạn, nó cần là cực to. Tương tự động vì vậy so với kháng xích.

Chú ý là những tính chất “cực đại”, “lớn nhất”, “nhỏ hơn” sử dụng mang đến xích và kháng xích được hiểu theo đuổi nghĩa thường thì, ko tùy theo mối liên hệ. Để phân biệt rõ rệt rộng lớn, tất cả chúng ta gọi xích lớn số 1 là xích nhiều năm nhất, kháng xích lớn số 1 là kháng xích to lớn nhất.

Cỡ của xích nhiều năm nhất được xem là chiều cao của poset. Cỡ của kháng xích to lớn nhất được xem là chiều rộng của poset.

Nếu tất cả chúng ta rất có thể phân hoạch một poset Phường trở nên k xích, thì k ko thể nhỏ rộng lớn chiều rộng lớn của Phường, vì thế nếu như như vậy tiếp tục tồn bên trên một xích với tối thiểu 2 thành phần của một kháng xích to lớn nhất A, và A không thể là 1 trong những kháng xích. Định lý Dilworth tuyên bố rằng một poset hữu hạn Phường luôn luôn rất có thể được phân hoạch trở nên những xích với số xích vày chiều rộng lớn của Phường. Một phiên phiên bản của quyết định lý mang đến poset vô hạn tuyên bố rằng một poset với chiều rộng lớn hữu hạn w nếu như và chỉ nếu như nó rất có thể được phân hoạch trở nên w xích. Định lý Mirsky tuyên bố rằng ngẫu nhiên poset Phường với độ cao hữu hạn rất có thể được phân hoạch trở nên những kháng xích, vô tê liệt số kháng xích nhỏ nhất rất có thể phân hoạch được vày với độ cao của Phường.

6. Bổ đề Zorn

Cho rằng một luyện với trật tự phần tử Phường với đặc điểm là từng xích với cùng 1 cận bên trên vô Phường. Thì Phường chứa chấp tối thiểu một thành phần cực to.

Luận bàn. Bổ đề là trúng tầm thông thường khi luyện Phường là trống rỗng. Tập trống rỗng là 1 trong những xích trống rỗng và đòi hỏi về cận bên trên là ko đạt được vì thế cận bên trên là 1 trong những thành phần tuy nhiên luyện trống rỗng không tồn tại thành phần này, vì thế này được bỏ dở. Nói cách tiếp, té đề ko sai khi Phường = ∅.

Trường thích hợp Phường ko trống rỗng, tất cả chúng ta xét về xích trống rỗng. Bây giờ thì từng thành phần của Phường đều là cận bên trên của xích trống rỗng, bởi vậy xích trống rỗng với cận bên trên và ko tác động cho tới ĐK của té đề, thành quả chỉ với tùy theo những xích ko trống rỗng của Phường, là tồn bên trên, vì thế Phường ko trống rỗng.

Như vậy, nếu như Phường là trống rỗng hoặc Phường với xích trống rỗng đều ko thực hiện thay cho thay đổi xác định của té đề. Nếu tất cả chúng ta chỉ việc tóm lại “P chứa chấp tối thiểu một thành phần rất rất đại” khi với đầy đủ fake thiết, các bạn hãy tưởng tượng vô một thuật toán, tiếp tục không tồn tại yếu tố. Tuy nhiên, nếu như tất cả chúng ta vận dụng té đề vô một minh chứng toán học tập này đấy như thể một nguyên tố chắc chắn đang được tồn bên trên, trong những lúc lại rớt vào tình huống Phường là trống rỗng hoặc Phường với xích trống rỗng như bên trên thì sẽ không còn hoặc. Như vậy dễ dàng giắt chính vì khi thao tác làm việc với té đề, tất cả chúng ta thông thường va vấp cần những luyện vô hạn và những lập luận trừu tượng, ví dụ điển hình lấy cận bên trên vày thích hợp vô hạn của những luyện vô hạn, thông thường ko nhắc nhở tất cả chúng ta về sơ sót. Cho nên cần phải có một tuyên bố tương tự, không giống một chút ít tuy nhiên trọn vẹn chỉ đem chân thành và ý nghĩa thận trọng:

Cho rằng một luyện với trật tự phần tử Phường ko trống rỗng với đặc điểm là từng xích ko trống rỗng với cùng 1 cận bên trên vô Phường. Thì Phường chứa chấp tối thiểu một thành phần cực to.

Bổ đề này nhường nhịn như đã cho thấy từng xích rất có thể tìm kiếm ra một xích cực to chứa chấp nó. Rồi “mọi xích với cùng 1 cận bên trên vô P” là tương tự với “mọi xích cực to với cận bên trên vô P”, vì thế cận bên trên của một xích cực to cũng là 1 trong những cận bên trên của những xích con cái của chính nó. Cho C là 1 trong những xích cực to ko trống rỗng. Cận bên trên của C nếu như với là thành phần lớn số 1 của chính nó. Vì không thể thành phần này ở ngoài C đối chiếu được với toàn bộ những thành phần của chính nó, cận bên trên của C là có một không hai, và cũng là 1 trong những thành phần cực to của Phường. Như vậy chỉ việc đã cho thấy một xích cực to ko trống rỗng bị ngăn bên trên là đầy đủ nhằm Phường với cùng 1 thành phần cực to. Chúng tao với cùng 1 phiên phiên bản mạnh rộng lớn một chút ít của té đề Zorn, tựa như bên trên, vô hiệu tình huống Phường là rỗng:

Nếu từng xích cực to ko trống rỗng vô một poset Phường ko trống rỗng bị ngăn bên trên thì Phường với cùng 1 thành phần cực to ứng.

Phát biểu bên dưới đó là yếu hèn rộng lớn, vì thế đòi hỏi “mọi xích rất rất đại”, tuy nhiên vẫn tồn tại mạnh rộng lớn té đề Zorn; tuy vậy, ko cần thiết ĐK “xích cực to ko rỗng” vì thế một thành phần của Phường đã và đang được chỉ ra:

Nếu từng xích cực to vô một poset Phường ko trống rỗng bị ngăn bên trên thì ngẫu nhiên thành phần này của Phường đều nhỏ rộng lớn hoặc vày một thành phần cực to này tê liệt của Phường.

Nếu tất cả chúng ta xuất phát điểm từ một xích A₀ ko chắc chắn là xích cực to, tất cả chúng ta rất có thể tiếp cận xích cực to của chính nó như sau: vì thế từng xích với cận bên trên, bởi vậy A₀ với cận bên trên, tất cả chúng ta lần một cận bên trên a₀ ∉ A₀. Nếu ko tìm kiếm ra thì A₀ với cận bên trên có một không hai là thành phần lớn số 1 của chính nó, và A₀ là xích cực to hoặc đoạn xích phía bên trên của xích cực to. Nếu tìm kiếm ra, tất cả chúng ta thêm thắt cận bên trên a₀ vô A₀ và được luyện A₁ = A₀ ⋃ {a₀}. Vì a₀ là cận bên trên của A₀ nên nó đối chiếu được với toàn bộ những thành phần của A₀. Do tê liệt A₁ cũng là 1 trong những xích. Quá trình tái diễn vì vậy tiếp tục tiến bộ dần dần cho tới cận bên trên của xích cực to. Xích sau cùng, rất có thể ko trọn vẹn là xích cực to, tuy nhiên nó chứa chấp cận bên trên của xích cực to và vô góc nhìn chỉ việc xét cận bên trên, coi như xích cực to.

Bây giờ, tưởng tượng rằng tất cả chúng ta rời chuồn đoạn bên dưới nằm trong của từng xích cực to bên trên từng điểm xác lập so với xích này không xẩy ra ngăn bên dưới, bọn chúng trở nên những tập được chuẩn bị trật tự tốt(xem mặt mày dưới). Và tất cả chúng ta lại sở hữu tuyên bố tương tự với tuyên bố tiếp bên trên. Giống như so với xích, một luyện được chuẩn bị trật tự chất lượng cũng rất có thể là trống rỗng. Do tê liệt tình huống Phường là trống rỗng vẫn cần thiết quăng quật qua:

Nếu từng luyện con cái được chuẩn bị trật tự chất lượng vô một poset Phường ko trống rỗng bị ngăn bên trên thì ngẫu nhiên thành phần này của Phường đều nhỏ rộng lớn hoặc vày một thành phần cực to này tê liệt của Phường.

Tập được chuẩn bị trật tự tốt(well-ordered set)

Quan hệ trật tự chất lượng bên trên một luyện S là 1 trong những mối liên hệ trật tự toàn phần bên trên S với tính chất là từng luyện con cái ko trống rỗng của S với cùng 1 thành phần bé bỏng nhất vô mối liên hệ trật tự này. Tập S cùng theo với mối liên hệ trật tự chất lượng được gọi là tập được chuẩn bị trật tự chất lượng.

Tập ℕ với mối liên hệ trật tự chuẩn chỉnh ≤ là luyện được chuẩn bị trật tự chất lượng. Tập ℤ với mối liên hệ trật tự chuẩn chỉnh ≤ ko cần là luyện được chuẩn bị trật tự chất lượng chính vì nó không tồn tại thành phần bé bỏng nhất.

Quan hệ buôn bán loại tự(Preorder, quasiorder)

Một mối liên hệ buôn bán trật tự là 1 trong những mối liên hệ nhì ngôi với tính hành động tự nhiên và bắc cầu. Quan hệ buôn bán trật tự ko nhất thiết phản đối xứng hoặc đối xứng. Nếu một mối liên hệ buôn bán trật tự thỏa phản đối xứng, nó là 1 trong những mối liên hệ trật tự cỗ phận; nếu như đối xứng, nó là 1 trong những mối liên hệ tương tự. Nói cách tiếp, mối liên hệ buôn bán trật tự tổng quát tháo rộng lớn, cả nhì mối liên hệ trật tự phần tử và mối liên hệ tương tự đều là những tình huống đặc trưng của mối liên hệ buôn bán trật tự. Thuật ngữ bán loại tự được hiểu là mối liên hệ tê liệt gần như là là mối liên hệ trật tự phần tử, tuy nhiên ko trọn vẹn, chỉ “một nửa”.

Định nghĩa. Một mối liên hệ nhì ngôi ≤ bên trên một luyện Phường được gọi là 1 trong những mối liên hệ buôn bán trật tự nếu như ≤ thỏa những ĐK sau đây với từng a, b, c vô P:

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

Một luyện với cùng 1 mối liên hệ buôn bán trật tự được gọi là tập buôn bán loại tự hoặc tập được chuẩn bị buôn bán loại tự (preordered mix, proset).

Một ví dụ mang đến mối liên hệ buôn bán trật tự là mối liên hệ tinh luyện bên trên luyện những phủ vô một không khí tôpô. Nếu những phủ tinh luyện là bọn họ những luyện con cái của những luyện vô phủ mối cung cấp, thì mối liên hệ tinh luyện là mối liên hệ trật tự phần tử. Hai phủ C và D là phủ tinh luyện của nhau chỉ khi bọn chúng cân nhau. Nhưng nếu như tất cả chúng ta lấy một phiên bản sao C’ của C, rồi thêm nữa C’ một luyện con cái của một luyện này tê liệt vô C’, thì C tinh luyện C’ và C’ tinh luyện C tuy nhiên bọn chúng ko cân nhau. Đó là mối liên hệ tương tự. Như vậy kéo theo một hệ ngược là nếu như tất cả chúng ta thêm thắt vào trong 1 phủ tinh luyện những luyện con cái của những luyện của chính nó thì ko thực hiện thay cho thay đổi thực chất của phủ tinh luyện.

Xem thêm: mèo hoạt hình

Quan hệ trật tự phần tử ngặt(Strict partial order)

Một mối liên hệ nhì ngôi < bên trên một luyện Phường được gọi là 1 trong những mối liên hệ trật tự phần tử ngặt nếu như thỏa những ĐK sau đây với từng a, b, c vô P: