Rate this post

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.

Leave a Reply

Call now
%d bloggers like this: