Что такое частичный порядок?

Question

Я читаю теорию категорий для программистов из Bartosz Milewski, и мне не пришла идея частичного порядка .

Я не получил контекст следующих предложений:

Вы также можете иметь более сильное отношение, которое удовлетворяет дополнительному условию, которое, если a <= b и b <=a тогда a должно быть таким же, как b.Это называется частичным порядком. </p>

Почему a должен совпадать с b?Например, a = 4 и b = 5, так что это совсем не одно и то же.Если бы он упомянул

.... если a = b и b = a ....

Тогда да, я бы согласился.

Вторая часть, которую я тоже не понимаю:

Наконец, вы можете наложить условие, что любые два объекта находятся в связи друг с другом, так или иначе;и это дает вам линейный или общий порядок.

Что он имеет в виду?

Answer 1

, если a <= b ... </p>

поэтому a = 4 и b = 5 удовлетворяют первому неравенству

и b <= a </p>

но они не удовлетворяют второму неравенству. Итак, ваш контрпример недействителен.

Давайте забудем <=, потому что я подозреваю, что это заставляет вас задуматься о целых числах или некотором другом наборе чисел, с которым вы знакомы. Итак, мы перепишем его с произвольным отношением, скажем, ¤

, если a ¤ b верно

и b ¤ верно

и это всегда означает, что a - это та же сущность, что и b

, затем мы называем отношение ¤ "частичным порядком" (для любого набора a, b взятого из)

Все, что говорит автор, это то, что для некоторого отношения , если данное правило истинно, , то мы называем это отношение частичным порядком. Это авторское определение частичного заказа. Если вы обнаружите ситуацию, когда правило не выполняется, это означает, что вы нашли тип отношения, который не частичный порядок.

В любом случае, причина определения порядка частичного заключается в том, что иногда у нас есть коллекции объектов, и мы не можем сравнивать их все друг с другом.

Например, набор оценок по разным предметам: возможно, я могу решить, лучше ли один студент по английскому языку, чем другой, и я могу решить, лучше ли один ученик в музыке, чем другой, но это не имеет смысла обсудите, лучше ли английский у одного ученика, чем у другого.

Последняя цитата просто означает, что если у нас есть отношение, которое составляет , по крайней мере, частичный порядок (оно удовлетворяет данному правилу) и , оно может быть применено ко всему вашему набору ( скажем, мы обсуждаем только оценки по английскому языку), , затем мы можем назвать это общим заказом за этот набор.

---

PS. Как это случается, правило действительно для обычного <= с целыми числами: следовательно, мы можем назвать отношение <= частичным порядком над ℤ. Так как также определено для каждой пары целых чисел, мы можем также вызвать <= общий заказ на ℤ.

PPS. Да, частичный порядок также требует транзитивности: мой ответ на самом деле касается только неформального определения, приведенного в вопросе. Вы можете найти более полные определения в Wolfram MathWorld , Википедии или где угодно.

Answer 2

Делимость положительного натурального числа на другое положительное натуральное число является примером частичного порядка, который не является полным порядком (x делит y, если y / x является натуральным числом).

1) Еслиx делит y, а если y делит z, то x делит z (транзитивность).

2) Если x делит y, а y делит x, то x = y (антисимметрия).

3)x делит x (рефлексивность).

Это три свойства частичного порядка.

Но это не полный порядок, потому что вы можете найти два натуральных числа x и y, таких что xне делит y, а y не делит x.

Answer 3

Чтобы понять различие, вам нужно взглянуть на наборы, отличные от целых чисел. Рассмотрим комплексные числа. Действительный предзаказ на комплексных числах может сказать z1 <= z2 тогда и только тогда, когда real(z1) <= real(z2). Таким образом, (3, 5) <= (3, 6) и (3, 6) <= (3, 5). Однако это не частичный заказ, потому что (3, 5) != (3, 6).

Добавление условия, что для z1 <= z2 также требуется imag(z1) <= imag(z2), делает это предварительным заказом, поскольку теперь (3, 5) <= (3, 6), но не наоборот. Это все еще не всего ордер, потому что ни (2, 3) <= (3, 2), ни (3, 2) <=(2, 3) не верны.

Вместо этого можно сказать z1 <= z2 тогда и только тогда, когда real(z1) <= real(z2) и abs(z1) <= abs(z2). Теперь (3, 5) <= (3, 6) все еще верно, но (3, 6) <= (3, 5) не потому, что sqrt(3**2 + 6**2) > sqrt(3**2 + 5**2). Но мы можем сказать, что (2, 3) <= (3, 2), потому что 2 <= 3 и sqrt(13) <= sqrt(13). Это делает оператор <= полным заказом. (Обновление: проверка, является ли лексикографическое упорядочение для abs и arg - с arg ограниченным (-pi,pi], в то время как специальный регистр 0 - является надлежащим общим порядком, оставляется как упражнение для читателя.)

(Обычно мы говорим, что комплексные числа не упорядочены, поскольку существует несколько способов определения общего порядка, но нет единственного "естественного" порядка.)

Answer 4

Учитывайте это Направленный ациклический граф :

Если мы говорим, что стрелка на этом графике обозначает <= Отношение затем мы можем видеть, что a <= c и c<=d.Но это не тот случай, когда b<=c и c<=b не имеют места.Следовательно, у нас есть порядок, но он только частичный, поскольку он существует только для некоторых пар элементов в домене.

В общем, DAG определяет частичный порядок для своих членов.Даже если стрелка от a до e не была включена, мы все равно могли бы сказать, что a<=c и c<=e, поэтому поэтому a<=e.

Имейте в виду, что мы не интерпретируем "x<= y "означает что-либо кроме« Я могу получить от x до y, следуя стрелкам на диаграмме ».Теперь предположим, что у нас есть две буквы x и y, и мы знаем, что x <= y и y <= x.Если x и y различны, и вы можете перейти от x к y, то вы не сможете перейти от y к x.Следовательно, x и y не могут быть разными предметами, поэтому они оба должны быть одним и тем же предметом. </p>

С другой стороны, общий порядок существует для всех пар предметов.Например, целые числа имеют общий порядок.