7.4: Часткове та повне замовлення

Дві особливі відносини часто зустрічаються в математиці. Обидва мають відношення до якогось упорядкування елементів у наборі. Їх вивченню присвячена галузь математики. Як можна сказати з короткого обговорення в цьому розділі, вони охоплюють багато знайомих понять.

Відношення на непорожній множині\(A\) називається частковим впорядкуванням або частковим порядком, якщо воно є рефлексивним, антисиметричним і перехідним. Ми часто використовуємо\(\preceq\) для позначення часткового впорядкування, і називається частково\((A,\preceq)\) впорядкованим набором або poset.

Приклад\(\PageIndex{1}\label{eg:ordering-01}\)

Звичайне відношення «менше або дорівнює» на\(R\), позначається\(\leq\), є прекрасним прикладом часткового впорядкування. Насправді це причина, чому ми приймаємо позначення\(\preceq\), оскільки воно відображає подібність між двома символами.

Приклад\(\PageIndex{2}\label{eg:ordering-02}\)

Ще одним класичним прикладом часткового впорядкування є відношення підмножини\(\subseteq\), позначається\(\wp(S)\), on, де\(S\) знаходиться будь-яка сукупність елементів. Зверніть увагу, що\(S\) може бути порожнім, в цьому випадку\(\wp(\emptyset) = \{\emptyset\}\), і, очевидно,\((\wp(\emptyset),\subseteq)\) є частково впорядкованим набором.

Приклад\(\PageIndex{3}\label{eg:ordering-03}\)

Ще одним стандартним прикладом poset є\((\mathbb{N},\mid)\). Легко перевірити, що відношення «ділить» над натуральними числами є частковим впорядкуванням. Чи можете ви пояснити\((\mathbb{Z}^*,\mid)\), чому це не поета?

Вправа\(\PageIndex{1}\label{he:ordering-01}\)

Знайдіть зустрічний приклад, щоб проілюструвати, чому відношення «ділить», позначається\(\mid\), над не\(\mathbb{Z}^*\) є антисиметричним. Чи є відношення «ділить» рефлексивним над\(\mathbb{Z}\)? Як щодо транзитивності?

Вправа\(\PageIndex{2}\label{he:ordering-02}\)

\(\sqsubseteq\)Визначте відношення\(\wp(\{a,b,c,d\})\) відповідно до\[S\sqsubseteq T \,\Leftrightarrow\, S\subseteq T\cup\{a\}. \nonumber\] Чи\((\wp(\{a,b,c,d\},\sqsubseteq)\) є poset? Якими властивостями вона не володіє? Поясніть.

Очевидно, якщо\(a\preceq b\) але\(a\neq b\), то ми можемо написати\(a \prec b\). Ми іноді говоримо, що\(a\) передує\(b\), або\(b\) досягає успіху\(a\). Ми також говоримо\(b\), що\(a\) є попередником або\(b\) є наступником\(a\).

Диграф для поета може бути спрощений. Оскільки завжди\(a\) пов'язаний із\(a\) самим собою, надмірно намалювати петлю навколо кожної вершини. Оскільки\(a\preceq b\) і\(b\preceq c\) завжди мають на увазі це\(a\preceq c\), немає необхідності включати дугу (спрямований край) від\(a\) до\(c\). Таким чином, ми дотримуємося конвенції, що ми тільки малювати дугу від\(a\) до\(b\) якщо\(a\prec b\) і там не існує інший елемент\(t\) такий, що\(a\prec t\) і\(t\prec b\). Нарешті, якщо\(a\prec b\), ми можемо розмістити\(b\) вище\(a\) так, щоб всі дуги були спрямовані вгору. Це говорить про те, що ми можемо використовувати неорієнтовані лінії, щоб полегшити читання графіка. Всі ці модифікації призводять до набагато простішого графічного представлення під назвою діаграма Хассе.

Приклад\(\PageIndex{4}\label{eg:ordering-04}\)

Зрозуміло, що\((\{1,2,3,4,6,12\},\mid)\) це поета. Його діаграма Хассе відображається нижче.

У цій угоді про використання неорієнтованої лінії\(\preceq\) відношення (отже, впорядкування елементів) зчитується знизу вгору.

Вправа\(\PageIndex{3}\label{he:ordering-03}\)

Намалюйте діаграму Хассе для поета\((\{1,2,3,4,6,9,12,18,36\},\mid)\).

Визначення посади не вимагає, щоб кожна пара різних елементів була порівнянною. Це означає, що можуть існувати\(a\neq b\) такі, що\(a\not\preceq b\) і\(b\not\preceq a\). Приклад можна знайти в цифрах 2 і 3 в прикладі 7.4.4. Якщо часткове впорядкування має додаткову властивість, що для будь-яких двох різних елементів\(a\) і\(b\),\(a\prec b\) або або\(b\prec a\) (отже, будь-яка пара різних елементів порівнянна), ми називаємо відношення загальним порядком.

Приклад\(\PageIndex{5}\label{eg:ordering-05}\)

Посет\((\mathbb{N},\leq)\) - це повністю впорядкований набір. Посет також\((\{1,5,25,125\},\mid)\) є повністю впорядкованим набором. Його діаграма Хассе показана нижче.

Зрозуміло, що діаграма Хассе будь-якого повністю впорядкованого набору буде виглядати так, як показано вище. Отже, загальне впорядкування також називається лінійним упорядкуванням. Повністю впорядкований набір також називається ланцюгом.

Вправа\(\PageIndex{4}\label{he:ordering-04}\)

Побудувати діаграму Хассе для поета\((\{1,2,4,18,16\},\mid)\). Це повністю впорядкований набір?

Вправа\(\PageIndex{5}\label{he:ordering-05}\)

Побудувати діаграму Хассе для поета\((\wp(\{a,b,c\}),\subseteq)\).

Резюме та огляд

• Відношення, яке є рефлексивним, антисиметричним і перехідним називається частковим впорядкуванням.
• Набір з частковим упорядкуванням називається частково впорядкованим набором або позетом.
• Посет з кожною парою різних елементів, порівнянних, називається повністю впорядкованим набором.
• Загальне впорядкування також називається лінійним упорядкуванням, а повністю впорядкований набір також називається ланцюгом.

Вправа\(\PageIndex{1}\label{ex:ordering-01}\)

\(A\)Дозволяти множина натуральних чисел, які є дільниками 30. Побудувати діаграму Хассе\((A,\mid)\).

Вправа\(\PageIndex{2}\label{ex:ordering-02}\)

Нехай\(S = \big\{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\big\}\). Побудувати діаграму Хассе для\((S,\subseteq)\).

Вправа\(\PageIndex{3}\label{ex:ordering-03}\)

\((A,\preceq)\)Дозволяти бути poset, і\(B\) непорожній підмножина\(A\). Покажіть, що\((B,\preceq)\) це також поета. Природно, ми\((B,\preceq)\) називаємо підмножиною\((A,\preceq)\).

Вправа\(\PageIndex{4}\label{ex:ordering-04}\)

Визначте відношення\(\preceq\) на\(\mathbb{Z}\) відповідно до\[a\preceq b \,\Leftrightarrow\, a=b \mbox{ or } a\bmod3 < b\bmod3. \nonumber\]

• Покажіть, що\((\mathbb{Z},\preceq)\) це допис.
• Нехай\(B=\{-3,-2,-1,0,1,2,-3\}\). Побудувати діаграму Хассе для підмножини\((B,\preceq)\).

Вправа\(\PageIndex{5}\label{ex:ordering-05}\)

Визначте відношення\(\preceq\) на\(\mathbb{Z}\) відповідно до\[a\preceq b \,\Leftrightarrow\, a=b \mbox{ or } |a|<|b|. \nonumber\]

• Покажіть, що\((\mathbb{Z},\preceq)\) це допис.
• Побудувати діаграму Хассе для підмножини\((B,\preceq)\), де\(B=\{-2,-1,0,1,2\}\).

Вправа\(\PageIndex{6}\label{ex:ordering-06}\)

Визначте відношення\(\preceq\) на\(\mathbb{Z}\times\mathbb{Z}\) відповідно до\[(a,b)\preceq(c,d) \,\Leftrightarrow\, (a,b)=(c,d) \mbox{ or } a^2+b^2<c^2+d^2. \nonumber\]

• Покажіть, що\((\mathbb{Z}\times\mathbb{Z},\preceq)\) це допис.
• Побудувати діаграму Хассе для підмножини\((B,\preceq)\), де\(B=\{0,1,2\}\times\{0,1,2\}\).

Вправа\(\PageIndex{7}\label{ex:ordering-07}\)

Побудувати приклад підмножини\(B\)\(\wp(\{a,b,c,d\})\) такого, що\((B,\subseteq)\) є повністю впорядкованою множиною.

Вправа\(\PageIndex{8}\label{ex:ordering-08}\)

Дозвольте\[A = \{(m,n)\mid m,n\in\mathbb{N} \mbox{ and } \gcd(m,n)=1\}, \nonumber\] і визначити відношення\(\preceq\) на\(A\) відповідно до\[(a,b)\preceq(c,d) \,\Leftrightarrow\, ad\leq bc. \nonumber\] Доведіть, що\((A,\preceq)\) є повністю впорядкованим набором.