Частично упорядоченное множество

Ч
Определение
Частично упорядоченным множеством называют непустое множество М, элементы которого находятся друг с другом в отношении частичного порядка.
Отношением частичного порядка, вообще говоря, формализуется понятие сравнения, поскольку о любых двух вещах a и b можно высказать четыре взаимоисключающих суждения:
Все эти случаи взаимоотношений элементов в частично упорядоченном множестве допускаются.
a больше b;

a меньше b;

a равно b;

a несравнимо с b.
a φ a – рефлексивность

Если a φ b и b φ a, то a = b – антисимметричность

Если a φ b и b φ c, то a φ c – транзитивность
И тогда частично упорядоченное множество – это пара (М, φ).
Рассмотрим в качестве примера множество M = {0, 1, 2, 3}, но не с «естественным» порядком (такой порядок будет полным – проверьте!), а со «специально оговоренным» – мы будем говорить, что «a меньше b, только если а делит b нацело». Ну в каком-то смысле такой порядок тоже естественный, поскольку «если делит, да еще и нацело, то уж точно меньше». Но вот в нашем новом, «искусственном» случае элемент может быть меньше в обычном смысле, но не делить нацело другой элемент. Возникает такая вот частично упорядоченная решетка (lattice):
Обратите внимание сразу на несколько существенных моментов:
Во-первых, рефлексивность требует, чтобы каждый элемент, включая ноль, делился на себя, и это требование выполняется – ноль себя делит.
Во-вторых, опять-таки ноль, который мы привыкли считать наименьшим положительным целым числом, стал наибольшим элементом в множестве М, упорядоченном частично вновь определенным отношением φ делимости нацело.
В-третьих, элементы 2 и 3 оказались несравнимы по этому отношению, так как ни 2 не делит 3 нацело, ни, тем более, наоборот.
И последнее: попробуйте самостоятельно убедиться, что любое частично упорядоченное множество образует категорию.
Таким образом, в отличие от полного порядка, частичный порядок допускает несравнимость элементов, что делает частично упорядоченные множества, как это ни покажется странным, крайне удобным инструментом современной логики.
Дело в том, что, скажем, множество всех подмножеств некоторого множества оказывается не только частично упорядоченным по включению, но и образует так называемый булеан – поскольку на этом множестве подмножеств возникает структура булевой алгебры, которая в логике является моделью для классической логики высказываний. Вот, например, как будет выглядеть булеан трехэлементного множества M = {1, 2, 3}:
Как и на предыдущей диаграмме, стрелками здесь показаны отношения между сравнимыми элементами. И, как и на предыдущей диаграмме, мы видим, что далеко не все элементы здесь оказываются сравнимы: синглетон {2}, скажем, не включен (не является его подмножеством) в множество {1,3}; множества {1,3} и {2,3} также не являются подмножествами друг друга, и т. д.
Не углубляясь в детали соответствия между теоретико-множественными и логическими операциями, отметим лишь то, что в классической логике отрицание отрицания равно утверждению, и поэтому в ней, в частности, допустимы доказательства от противного. В булевой алгебре отрицание моделируется дополнением: дополнение множества {1,3} до M – это {2}, а дополнение {2} до M – снова {1,3}. Это не всегда удобно и более того, не всегда корректно с логической точки зрения.
Существует такая притча о приговоренном к смертной казни мудреце, которому формально предоставлялось право самому выбрать свою участь, случайным образом вытянув одну из двух бумажек, на которых должно было быть написано «казнить» и «помиловать». Однако, «сатрапы-вожди» попытались лишить его даже этого и на обеих бумажках написали «казнить». Хитрый мудрец узнал об этом и быстро проглотил «выбранную» им бумажку, а посрамленным сатрапам ничего не оставалось, как «логически допустить», что мудрец выбрал бумажку с надписью «помиловать» коль скоро на уцелевшей написано «казнить». Чтобы
В качестве модели такой неклассической логики, которую стали называть интуиционистской, или шире – конструктивной, ученик Брауэра Аренд Гейтинг предложил еще одну частично упорядоченную структуру – Гейтингову алгебру.
Ее также можно построить из уже знакомого нам множества M = {1, 2, 3}, рассмотрев не все его подмножества, а только так называемые открытые. Открытые подмножества нагляднее всего изобразить как окрестности какой-нибудь фиксированной точки данного множества – например, 1:
Непосредственно из рисунка видно, что для точки 1 мы можем выделить пять таких окрестностей: Ø, {1}, {1, 2}, {1, 3} и все множество M, в зависимости от того, насколько точно мы хотим сфокусироваться вблизи места, отмеченного точкой 1.
Luitzen Egbertus Jan Brouwer
Arend Heyting
Более серьезные и состоятельные примеры вы найдете в работах самого Брауэра и его последователей.
Тогда на множестве таких окрестностей тоже, во-первых, возникает частичная упорядоченность по включению: