2.5: Замовлення

Template:MathJaxZach

Багато наших порівнянь передбачають опис деяких об'єктів як «менше», «рівних» або «більших за» інших об'єктів у певному відношенні. Вони передбачають порядок відносин. Але існують різні види порядкових відносин. Наприклад, деякі вимагають, щоб будь-які два об'єкти були порівнянними, інші - ні, деякі містять ідентичність (наприклад\(\le\)), а деякі виключають її (наприклад\(<\)). Це допоможе нам мати таксономію тут.

Визначення\(\PageIndex{1}\): Preorder

Відношення, яке є як рефлексивним, так і перехідним, називається попереднім порядком.

Визначення\(\PageIndex{2}\): Partial order

Попереднє замовлення, яке також є антисиметричним, називається частковим порядком.

Визначення\(\PageIndex{3}\): Linear order

Частковий порядок, який також пов'язаний, називається загальним порядком або лінійним порядком.

Кожен лінійний порядок також є частковим порядком, і кожне часткове замовлення також є попереднім замовленням, але розмови не тримаються.

Приклад\(\PageIndex{1}\)

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

Приклад\(\PageIndex{2}\)

Розглянемо не більше, ніж відношення\(\preccurlyeq\) на\(\Bin^*\):\(x \preccurlyeq y\) iff\(\len{x} \le \len{y}\). Це передпорядок (рефлексивний і перехідний), і навіть пов'язаний, але не частковий порядок, так як він не антисиметричний. Наприклад,\(01 \preccurlyeq 10\) і\(10 \preccurlyeq 01\), але\(01 \neq 10\).

Приклад\(\PageIndex{3}\)

Важливим частковим порядком є відношення\(\subseteq\) на множині множин. Це взагалі не лінійний порядок, так як якщо\(a \neq b\) і ми вважаємо\(\Pow{\{a, b\}} = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}\), ми бачимо, що\(\{a\} \nsubseteq \{b\}\) і\(\{a\} \neq \{b\}\) і\(\{b\} \nsubseteq \{a\}\).

Приклад\(\PageIndex{4}\)

Відношення подільності без залишку дає нам частковий порядок, який не є лінійним порядком. Для цілих чисел\(n\)\(m\), ми пишемо\(n\mid m\) на середнє\(n\) (рівномірно) ділить\(m\), тобто, якщо є деяке ціле число\(k\) так, що\(m=kn\). На\(\Nat\), це частковий порядок, але не лінійний порядок: наприклад,\(2\nmid3\) і теж\(3\nmid2\). Розглядається як відношення на\(\Int\), подільність є лише попереднім порядком, оскільки вона не є антисиметричною:\(1\mid-1\) і\(-1\mid1\) але\(1\neq-1\).

Визначення\(\PageIndex{4}\): Strict order

Суворий порядок - це відношення, яке є нерефлексивним, асиметричним та перехідним.

Визначення\(\PageIndex{5}\): Strict linear order

Суворий порядок, який також пов'язаний, називається строгим лінійним порядком.

Приклад\(\PageIndex{5}\)

\(\le\)лінійний порядок, відповідний суворому лінійному порядку\(<\). \(\subseteq\)це частковий порядок, відповідний суворому порядку\(\subsetneq\).

Визначення\(\PageIndex{6}\): Total order

Суворий порядок, який також пов'язаний, називається загальним порядком. Це також іноді називають строгим лінійним порядком.

Будь-який строгий порядок\(R\) на\(A\) можна перетворити в частковий порядок, склавши діагональ\(\Id{A}\), тобто склавши всі пари\(\tuple{x, x}\). (Це називається рефлексивним закриттям\(R\).) І навпаки, починаючи з часткового замовлення, можна отримати суворий наказ шляхом зняття\(\Id{A}\). Ці наступні два результати роблять це точним.

Пропозиція\(\PageIndex{1}\)

Якщо\(R\) строгий наказ далі\(A\), то\(R^+ = R \cup \Id{A}\) це частковий порядок. Причому якщо\(R\) тотал, то\(R^+\) є лінійним порядком.

Доказ. Припустимо,\(R\) це суворий порядок, тобто\(R \subseteq A^2\) і\(R\) є безрефлексивним, асиметричним і перехідним. Нехай\(R^+ = R \cup \Id{A}\). Ми повинні показати, що\(R^+\) є рефлексивним, антисиметричним і перехідним.

\(R^+\)явно рефлексивний, так як\(\tuple{x, x} \in \Id{A} \subseteq R^+\) для всіх\(x \in A\).

Показати\(R^+\) є антисиметричним, припустимо для reductio що\(R^+xy\) і\(R^+yx\) але\(x \neq y\). Так як\(\tuple{x,y} \in R \cup \Id{X}\), але\(\tuple{x, y} \notin \Id{X}\), ми повинні мати\(\tuple{x, y} \in R\), т. Е\(Rxy\). Аналогічно,\(Ryx\). Але це суперечить припущенню, яке\(R\) є асиметричним.

Щоб встановити транзитивність, припустимо, що\(R^+xy\) і\(R^+yz\). Якщо обидва\(\tuple{x, y} \in R\) і\(\tuple{y,z} \in R\), то\(\tuple{x, z} \in R\) так як\(R\) є перехідним. Інакше або\(\tuple{x, y} \in \Id{X}\), тобто, або\(x = y\)\(\tuple{y, z} \in \Id{X}\), т\(y = z\). Е. У першому випадку ми маємо це\(R^+yz\) за припущенням\(x = y\), отже\(R^+xz\). Аналогічно і в другому випадку. У будь-якому випадку\(R^+xz\), таким чином, також\(R^+\) є перехідним.

Щодо пункту «більше того», припустимо,\(R\) це сумарний порядок,\(R\) тобто, що пов'язано. Так для всіх\(x \neq y\), або\(Rxy\) або\(Ryx\), тобто або\(\tuple{x, y} \in R\) або\(\tuple{y, x} \in R\). Так як\(R \subseteq R^+\), це залишається вірним\(R^+\), так і\(R^+\) пов'язано. ◻

Пропозиція\(\PageIndex{2}\)

Якщо\(R\) частковий наказ далі\(X\), то\(R^- = R \setminus \Id{X}\) це суворий порядок. Причому якщо\(R\) лінійний, то\(R^-\) тотальний.

Доказ. Це залишають як вправу. ◻

Проблема\(\PageIndex{1}\)

Дайте доказ Пропозиції\(\PageIndex{2}\).

Приклад\(\PageIndex{6}\)

\(\le\)лінійний порядок, відповідний загальному порядку\(<\). \(\subseteq\)це частковий порядок, відповідний суворому порядку\(\subsetneq\).

Наступний простий результат, який встановлює, що загальні замовлення задовольняють властивість, подібну розширенню:

Пропозиція\(\PageIndex{3}\)

Якщо\(<\) повністю замовляє\(A\), то:\[(\forall a, b \in A)((\forall x \in A)(x < a \leftrightarrow x < b) \rightarrow a = b)\nonumber\]

Доказ. Припустимо\((\forall x \in A)(x < a \leftrightarrow x < b)\). Якщо\(a < b\), то\(a < a\), суперечить тому, що\(<\) є нерефлексивним; так\(a \nless b\). Точно так само,\(b \nless a\). Отже\(a = b\), як\(<\) підключається. ◻