Tập hợp được sắp thứ tự riêng phần

Tập hợp được sắp thứ tự riêng phần, hay poset, là một tập hợp cùng với một quan hệ thể hiện ý tưởng một phần tử đứng trước hoặc nằm dưới một phần tử khác, mà không yêu cầu tất cả các cặp phải so sánh được.

Definition

Một tập hợp được sắp thứ tự riêng phần là một tập hợp có quan hệ nhị phân có tính phản xạ, phản đối xứng và bắc cầu; các phần tử có thể so sánh được hoặc không so sánh được theo quan hệ này.

Scope

Chủ đề này bao gồm các tiên đề của thứ tự riêng phần, biểu đồ Hasse, chuỗi và đối chuỗi, các phần tử cực đại và cực tiểu, các ánh xạ bảo toàn thứ tự và tính đối ngẫu, và các định lý cấu trúc tổ hợp của Dilworth và Mirsky. Nó cũng giới thiệu hàm Mobius của một poset, động cơ lý thuyết thứ tự đằng sau nguyên lý bao hàm-loại trừ tổng quát.

Core questions

• Quan hệ thứ tự ưu tiên giữa các phần tử được tiên đề hóa và biểu diễn như thế nào?
• Các phần tử của một poset được phân chia thành các chuỗi hoặc đối chuỗi như thế nào?
• Đối chuỗi lớn nhất hoặc chuỗi dài nhất trong một poset là gì?
• Hàm Mobius tổng quát hóa việc đếm bằng nguyên lý bao hàm-loại trừ như thế nào?

Key concepts

• Các tiên đề thứ tự riêng phần
• Biểu đồ Hasse
• Chuỗi và đối chuỗi
• Các phần tử cực đại và cực tiểu
• Định lý Dilworth
• Hàm Mobius

Key theories

Định lý Dilworth

Trong bất kỳ poset hữu hạn nào, số chuỗi tối thiểu cần thiết để bao phủ tất cả các phần tử bằng kích thước tối đa của một đối chuỗi, một tính đối ngẫu min-max cơ bản với nhiều hệ quả tổ hợp.

Hàm Mobius của một poset

Mọi poset hữu hạn cục bộ đều mang một hàm Mobius đảo ngược phép tổng trên thứ tự; lý thuyết của Rota biến điều này thành nguồn thống nhất của nguyên lý bao hàm-loại trừ và phép đảo ngược số học.

Clinical relevance

Poset mô hình hóa việc lập lịch tác vụ với các phụ thuộc, hệ thống phân cấp phiên bản và kế thừa, và các quan hệ ưu tiên và bao hàm, trong khi các phân tách chuỗi và đối chuỗi xuất hiện trong các thuật toán lập lịch và sắp xếp.

History

Định lý chuỗi-đối chuỗi năm 1950 của Dilworth và nền tảng hàm Mobius năm 1964 của Rota đã biến nghiên cứu tổ hợp về các tập hợp có thứ tự thành một chủ đề trung tâm của toán học rời rạc hiện đại.

Key figures

• Robert Dilworth
• Gian-Carlo Rota
• Richard P. Stanley

Seminal works

• davey2002
• stanley2011

Frequently asked questions

Biểu đồ Hasse là gì?

Đó là một biểu diễn đồ họa của một poset hữu hạn trong đó mỗi phần tử là một điểm được đặt phía trên những phần tử mà nó bao phủ, với các cạnh chỉ giữa các cặp bao phủ, do đó thứ tự được đọc từ dưới lên.

Đối chuỗi là gì?

Đối chuỗi là một tập hợp các phần tử mà không có hai phần tử nào có thể so sánh được, chẳng hạn như một tập hợp các tập con mà không có tập con nào chứa tập con khác.