Xét một quan hệ R trên tập S thỏa mãn các tính chất sau:
- R là phản xạ, tức là xRx với mọi x ∈ S.
- R là phản đối xứng, tức là, nếu xRy và yRx, thì x = y.
- R có tính bắc cầu, tức là xRy và yRz, sau đó là xRz.
Khi đó R được gọi là quan hệ thứ tự từng phần, và tập S cùng với thứ tự từng phần được gọi là tập có thứ tự từng phần hay POSET và được ký hiệu là (S, ≤).
Các bài viết liên quan:
Ví dụ:
Tập hợp N các số tự nhiên tạo thành một tập hợp theo quan hệ ‘≤’ vì trước hết x ≤ x, thứ hai, nếu x ≤ y và y ≤ x, thì chúng ta có x = y và cuối cùng nếu x ≤ y và y ≤ z, nó ngụ ý x ≤ z với mọi x, y, z ∈ N.
Tập hợp N gồm các số tự nhiên chia hết tức là ‘x chia y’ tạo thành một tập hợp vì x / x với mọi x ∈ N. Ngoài ra nếu x / y và y / x, ta có x = y. Một lần nữa nếu x / y, y / z ta có x / z, với mọi x, y, z ∈ N.
Xét một tập S = {1, 2} và tập hợp lũy thừa của S là P (S). Quan hệ của tập hợp bao gồm ⊆ là một bậc riêng phần. Vì, với bất kỳ tập A, B, C nào trong P (S), đầu tiên chúng ta có A ⊆ A, thứ hai, nếu A ⊆B và B⊆A, thì chúng ta có A = B. Cuối cùng, nếu A ⊆B và B ⊆ C thì A⊆C. Do đó, (P (S), ⊆) là một tập hợp.
Các yếu tố của POSET
- Phần tử cực đại: Phần tử a ∈ A được gọi là phần tử cực đại của A nếu không có phần tử nào trong c trong A sao cho a ≤ c.
- Phần tử cực tiểu: Một phần tử b ∈ A được gọi là phần tử tối giản của A nếu không có phần tử nào trong c trong A sao cho c ≤ b.
Lưu ý: Có thể có nhiều hơn một phần tử cực đại hoặc nhiều hơn một phần tử tối thiểu.
Ví dụ: Xác định tất cả các phần tử cực đại và cực tiểu của poset có biểu đồ Hasse được hiển thị trong hình:
Lời giải: Các phần tử cực đại là b và f.
Các phần tử tối giản là d và e.
Các yếu tố có thể so sánh được:
Xét một tập có thứ tự A. Hai phần tử a và b của tập A được gọi là có thể so sánh được nếu
a ≤ b hoặc b ≤ a
Các yếu tố không thể so sánh:
Xét một tập có thứ tự A. Hai phần tử a và b của tập A được gọi là không so sánh được nếu cả a ≤ b và b ≤ a.
Ví dụ: Xét A = {1, 2, 3, 5, 6, 10, 15, 30} được sắp xếp theo phép chia hết. Xác định tất cả các cặp nguyên tố có thể so sánh và không so sánh được của A.
Bài giải: Các cặp nguyên tố có thể so sánh được của A là:
{1, 2}, {1, 3}, {1, 5}, {1, 6}, {1, 10}, {1, 15}, {1, 30}
{2, 6}, {2, 10}, {2, 30}
{3, 6}, {3, 15}, {3, 30}
{5, 10}, {5, 15}, {5, 30}
{6, 30}, {10, 30}, {15, 30}
Cặp phần tử không thể so sánh của A là:
{2, 3}, {2, 5}, {2, 15}
{3, 5}, {3, 10}, {5, 6}, {6, 10}, {6, 15}, {10, 15}
Ordered Set
Xét một tập có thứ tự A. Tập A được gọi là tập có thứ tự tuyến tính hoặc tập có thứ tự hoàn toàn, nếu mọi cặp phần tử trong A đều có thể so sánh được.
