Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивности и рефлексивности . |
В математике , особенно в теории порядка , частично упорядоченное множество (также poset ) формализует и обобщает интуитивную концепцию упорядочения, последовательности или расположения элементов набора . Poset состоит из набора вместе с бинарным отношением, указывающим, что для определенных пар элементов в наборе один из элементов предшествует другому в упорядочении. Само отношение называется «частичным порядком». Слово частичноев именах «частичный порядок» и «частично упорядоченный набор» используется как указание на то, что не каждая пара элементов должна быть сопоставимой. То есть могут быть пары элементов, для которых ни один элемент не предшествует другому в poset. Таким образом, частичные заказы обобщают общие заказы , в которых каждая пара сопоставима.
Формально частичный порядок - это любое бинарное отношение, которое является рефлексивным (каждый элемент сопоставим сам с собой), антисимметричным (два разных элемента не предшествуют друг другу) и транзитивным (начало цепочки отношений предшествования должно предшествовать концу цепочки. ).
Один знакомый пример частично упорядоченного множества - это собрание людей, упорядоченное по генеалогическому происхождению. Некоторые пары людей связаны отношениями потомков и предков, но другие пары людей несравнимы, и ни одна из них не является потомком другой.
Позиционирование может быть визуализировано через его диаграмму Хассе , которая изображает отношение упорядочения. [1]
Формальное определение
(Нестрогий) частичный порядок [2] - это однородное бинарное отношение ≤ над множеством P, удовлетворяющее конкретным аксиомам, которые обсуждаются ниже. Когда ≤ Ь , мы говорим , что это связано с б . (Это не означает, что b также связано с a , потому что отношение не обязательно должно быть симметричным .)
Аксиомы для нестрогого частичного порядка утверждают, что отношение ≤ рефлексивно , антисимметрично и транзитивно . То есть для всех a , b и c в P он должен удовлетворять:
- a ≤ a ( рефлексивность : каждый элемент связан сам с собой).
- если a ≤ b и b ≤ a , то a = b ( антисимметрия : два различных элемента не могут быть связаны в обоих направлениях).
- если a ≤ b и b ≤ c , то a ≤ c ( транзитивность : если первый элемент связан со вторым элементом, и, в свою очередь, этот элемент связан с третьим элементом, то первый элемент связан с третьим элементом. элемент).
Другими словами, частичный порядок - это антисимметричный предпорядок .
Набор с частичным порядком называется частично упорядоченным набором (также называемым poset ). Иногда также используется термин упорядоченный набор , если из контекста ясно, что никакой другой вид порядка не подразумевается. В частности, полностью упорядоченные множества также могут называться «упорядоченные множества», особенно в областях, где эти структуры более распространены, чем посеты.
Для получения более , б , элементы частично упорядоченного множества Р , если ≤ б или б ≤ , то и б являются сопоставимыми . В остальном они несравнимы . На рисунке вверху справа, например, { x } и { x , y , z } сопоставимы, а { x } и { y } - нет. Частичный порядок, при котором каждая пара элементов сопоставима, называется полным порядком или линейным порядком ; полностью упорядоченное множество также называется цепочкой (например, натуральные числа с их стандартным порядком). Подмножество чугуна, в котором никакие два различных элемента не сопоставимы, называется антицепью (например, набор одиночных элементов {{ x }, { y }, { z }} на верхнем правом рисунке). Элемент a называется строго меньшим, чем элемент b , если a ≤ b и a ≠ b . Элемент a называется покрытым другим элементом b , записываемым как a b (или a <: b ), если a строго меньше, чем b, и между ними не помещается третий элемент c ; формально: если и a ≤ b, и a ≠ b истинны, и a ≤ c ≤ b ложно для каждого c с a ≠ c ≠ b . Более определение краткого будет дано ниже с использованием строгого порядка , соответствующий «≤». Например, { x } покрывается { x , z } на верхнем правом рисунке, но не { x , y , z }.
Примеры
Стандартные примеры позы, возникающие в математике, включают:
- В действительных числах упорядочены по стандарту менее чем или равные отношению ≤ (полностью упорядоченное множество, а).
- Набор подмножеств данного набора (его набор мощности ), упорядоченный по включению (см. Рисунок вверху справа). Точно так же набор последовательностей, упорядоченных по подпоследовательности , и набор строк, упорядоченных по подстроке .
- Множество натуральных чисел с отношением делимости .
- Множество вершин ориентированного ациклического графа, упорядоченное по достижимости .
- Множество подпространств одного векторного пространства упорядочены по включению.
- Для частично упорядоченного множества Р , то пространство последовательностей , содержащее все последовательности элементов из Р , где последовательность последовательности предшествует Ь , если каждый элемент в течение предшествует соответствующий пункт в б . Формально ( a n ) n ∈ℕ ≤ ( b n ) n ∈ℕ тогда и только тогда, когда a n ≤ b n для всех n в, то есть покомпонентный порядок .
- Для множества X и частично упорядоченного множества Р , тем функциональное пространство , содержащее все функции из X в Р , где Р ≤ г тогда и только тогда , когда F ( х ) ≤ г ( х ) для всех х в X .
- Забор , частично упорядоченное множество , определенное с помощью переменной последовательности порядковых отношений < Ь > с < д ...
- Множество событий в специальной теории относительности и, в большинстве случаев [3] общая теория относительности , где в течение двух событий X и Y , X ≤ Y тогда и только тогда , когда Y в будущем светового конуса в X . Событие Y может быть каузально зависит только от X , если X ≤ Y .
Extrema
Есть несколько понятий «наибольшего» и «наименьшего» элемента в позиционном множестве P , а именно:
- Наибольший элемент и наименьший элемент: элемент г в Р является наибольшим элементом , если для каждого элемента а в P , ≤ г . Элемент т в P является наименьшим элементом , если для каждого элемента а в P , в ≥ м . У посета может быть только один наибольший или наименьший элемент.
- Максимальные элементы и минимальные элементы: элемент g в P является максимальным элементом, если нет такого элемента a в P , что a > g . Аналогично, элемент m в P является минимальным элементом, если в P нет такого элемента a , что a < m . Если ЧУМ имеет наибольший элемент, он должен быть единственным максимальным элементом, но в противном случае может быть более одного максимального элемента, и то же самое для наименьших элементов и минимальных элементов.
- Верхние и нижние границы : Для подмножества А из Р , элемент х в Р есть верхняя граница А , если ≤ х , для каждого элемента а в A . В частности, й не должен быть в A , чтобы быть верхней границей A . Аналогичным образом , элемент х в Р является нижней гранью А , если ≥ х , для каждого элемента а в A . Наибольший элемент из Р представляет собой верхнюю грань Р самого, и наименьший элемент является нижняя граница Р .
Например, рассмотрим положительные целые числа , упорядоченные по делимости: 1 - наименьший элемент, так как он делит все остальные элементы; с другой стороны, этот poset не имеет наибольшего элемента (хотя, если бы один включил в poset 0, кратное любому целому числу, это было бы наибольшим элементом; см. рисунок). В этом частично упорядоченном множестве нет даже максимальных элементов, так как любой g делит, например, 2 g , отличных от него, поэтому g не является максимальным. Если число 1 исключено, сохраняя при этом делимость упорядочением по элементам больше 1, то результирующий poset не имеет минимального элемента, но любое простое число является минимальным элементом для него. В этом наборе 60 - это верхняя граница (хотя и не наименьшая верхняя граница) подмножества {2, 3, 5, 10}, которое не имеет никакой нижней границы (поскольку 1 не входит в набор); с другой стороны, 2 - это нижняя граница подмножества степеней двойки, которая не имеет никакой верхней границы.
Заказы на декартово произведение частично упорядоченных множеств
В порядке увеличения силы, т. Е. Уменьшения наборов пар, три возможных частичных порядка на декартовом произведении двух частично упорядоченных наборов следующие (см. Рисунки):
- Лексикографическое порядок : ( , б ) ≤ ( с , d ) , если < с или ( = с и б ≤ d );
- заказ продукции : ( , б ) ≤ ( с , d ) , если ≤ C и B ≤ d ;
- рефлексивное замыкание на прямом произведении соответствующих строгих порядков: ( , б ) ≤ ( с , d ) , если ( < с и б < д ) или ( = с и Ь = д ).
Все три аналогично можно определить для декартова произведения более двух наборов.
Применительно к упорядоченным векторным пространствам над тем же полем результат в каждом случае также является упорядоченным векторным пространством.
См. Также заказы на декартово произведение полностью упорядоченных наборов .
Суммы частично упорядоченных наборов
Другой способ объединения двух множеств - это порядковая сумма [4] (или линейная сумма [5] ), Z = X ⊕ Y , определенная на объединении базовых множеств X и Y в порядке a ≤ Z b тогда и только тогда, когда :
- a , b ∈ X с a ≤ X b , или
- a , b ∈ Y с a ≤ Y b , или
- ∈ X и B ∈ Y .
Если два посета хорошо упорядочены , то их порядковая сумма тоже . [6] Операция порядкового суммирования - одна из двух операций, используемых для формирования последовательно-параллельных частичных порядков , и в этом контексте называется составлением серий. Другая операция, используемая для формирования этих порядков, несвязное объединение двух частично упорядоченных наборов (без отношения порядка между элементами одного набора и элементами другого набора), называется в этом контексте параллельной композицией.
Строгие и нестрогие частичные заказы
Частичный порядок может называться нестрогим (или рефлексивным ) частичным порядком для выделения или контраста строгим частичным порядкам . Строгий (или иррефлексивный ) частичный порядок- также известный как строгий предварительный заказ - наявляется однородным бинарное отношение на это иррефлексивный , переходный и асимметричный ; то есть удовлетворяет следующим условиям для всех:
- Безрезультатность : не а < а ,
- Транзитивность : если a < b и b < c, то a < c , и
- Асимметрия : если a < b, то не b < a .
Вместе иррефлексивность и транзитивность подразумевают асимметрию [7], поэтому однородное отношение является строгим частичным порядком тогда и только тогда, когда оно транзитивно и иррефлексивно. Кроме того, асимметрия подразумевает иррефлексивность [7], поэтому однородное отношение является строгим частичным порядком тогда и только тогда, когда оно транзитивно и асимметрично. Другими словами, транзитивное отношение асимметрично тогда и только тогда, когда оно иррефлексивно.
По определению каждый строгий слабый порядок является строгим частичным порядком. О реальных числах обычное меньшее отношениеявляется строгим частичным порядком, и то же самое верно и для обычного отношения больше, чем на
Эквивалентность
Строгие и нестрогие частичные заказы на множестве тесно связаны. Нестрогий частичный порядок может быть преобразован в строгий частичный порядок, удалив все связи в форме то есть строгий частичный порядок - это множество где диагональ а также обозначает вычитание множества . Наоборот, строгий частичный порядок на может быть преобразован в нестрогий частичный порядок путем присоединения всех отношений этой формы; это,является нестрогим частичным порядком. Таким образом, если является нестрогим частичным порядком, то соответствующий строгий частичный порядок это иррефлексивное ядро задается
- если а также
Наоборот, если является строгим частичным порядком, то соответствующий нестрогий частичный порядок является рефлексивным замыканием, определяемым:
- если или же
Это причина использования обозначений
Используя строгий порядок Соотношение "будет покрыт путем"можно эквивалентно перефразировать как" но нет для любой ".
Направленные ациклические графы
Строгие частичные порядки более точно соответствуют ориентированным ациклическим графам (DAG). Если граф построен, взяв каждый элемент быть узлом, и каждый элемент чтобы быть ребром, то каждый строгий частичный порядок является DAG, а транзитивное замыкание DAG является одновременно строгим частичным порядком, а также самим DAG. Напротив, нестрогий частичный порядок будет иметь петли на каждом узле и, следовательно, не будет DAG.
Обратные и двойственные по порядку
Обратное (или обратное) отношение частичного порядка ≤ является обратным к ≤. Обычно обозначается ≥, это отношение, которое удовлетворяет x ≥ y тогда и только тогда, когда y ≤ x . Обратное отношение частичного порядка является рефлексивным, транзитивным и антисимметричным и, следовательно, само является отношением частичного порядка. Порядок двойного частично упорядоченного множества является тот же набор с отношением частичного порядка заменена на обратную. Иррефлексивное отношение> к ≥, как <к ≤.
Любое из четырех отношений ≤, <, ≥ и> на данном множестве однозначно определяет остальные три.
В общем случае два элемента х и у частичного порядка может стоять в любом из четырех взаимоисключающих отношений друг к другу: либо х < у или х = у , или х > у или х и у не несравнимы (ни один из другога в-третьих, определение несравнимости здесь отличается от определения в слабом порядке ). Вполне упорядоченное множество один , что исключает эту четвертую возможность: все пары элементов сравнимы и мы тогда сказать , что трихотомия держит. В натуральных числах , то целые числа , то рациональные , и вещественные числа все полностью упорядочены по их алгебраической (подписи) величине , тогда как комплексные числа не являются. Это не означает, что комплексные числа не могут быть полностью упорядочены; мы могли бы, например, упорядочить их лексикографически через x + i y < u + i v тогда и только тогда, когда x < u или ( x = u и y < v ), но это не упорядочение по величине в любом разумном смысле, поскольку оно дает 1 больше 100 i . Упорядочивание их по абсолютной величине дает предварительный порядок, в котором все пары сопоставимы, но это не частичный порядок, поскольку 1 и i имеют одинаковую абсолютную величину, но не равны, что нарушает антисимметрию.
Отображения между частично упорядоченными наборами
Для двух частично упорядоченных множеств ( S , ≤) и ( T , ≼), [8] функция f : S → T называется сохраняющей порядок , или монотонной , или изотонной , если для всех x и y в S , x ≤ y влечет f ( x ) ≼ f ( y ). Если ( U , ≲) также является частично упорядоченным множеством, и оба f : S → T и g : T → U сохраняют порядок, их композиция g ∘ f : S → U также сохраняет порядок. Функция F : S → T называется порядком-отражающим , если для всех х и у в S , F ( х ) ≼ е ( у ) влечет е ≤ у . Если f одновременно сохраняет и отражает порядок, то это называется упорядоченным вложением ( S , ≤) в ( T , ≼). В последнем случае f обязательно инъективно , поскольку f ( x ) = f ( y ) влечет x ≤ y и y ≤ x и, в свою очередь, x = y в соответствии с антисимметрией ≤. Если заказ-вложение между двумя Posets S и T существует, то говорят , что S может быть встроен в T . Если заказ-вложение F : S → T является биективен , это называется порядковым изоморфизмом , а частичные порядки ( S , ≤) и ( Т , ≼) называются изоморфными . Изоморфные порядки имеют структурно похожие диаграммы Хассе (см. Рисунок справа). Можно показать, что если сохраняющие порядок отображения f : S → T и g : T → S существуют такие, что g ∘ f и f ∘ g порождают тождественную функцию на S и T соответственно, то S и T изоморфны по порядку. . [9]
Например, отображение f : ℕ → ℙ (ℕ) из набора натуральных чисел (упорядоченных по делимости) в набор степеней натуральных чисел (упорядоченных по включению множества) может быть определено путем преобразования каждого числа в набор его простых чисел. делители . Это сохраняет порядок: если x делит y , то каждый простой делитель x также является простым делителем y . Однако он не является ни инъективным (поскольку он отображает как 12, так и 6 в {2, 3}), ни отражением порядка (поскольку 12 не делит 6). Вместо этого взятие каждого числа в набор его простых делителей степени определяет отображение g : ℕ → ℙ (ℕ), которое сохраняет порядок, отражает порядок и, следовательно, является вложением порядка. Это не изоморфизм порядка (так как он, например, не отображает какое-либо число в набор {4}), но его можно сделать так, ограничив его область значений до g (ℕ). На правом рисунке показано подмножество и его изоморфный образ при g . Построение такого изоморфизма порядка в набор степеней может быть обобщено на широкий класс частичных порядков, называемых дистрибутивными решетками , см. « Теорема Биркгофа о представлении ».
Количество частичных заказов
Последовательность A001035 в OEIS дает количество частичных порядков для набора из n помеченных элементов:
Элементы | Любой | Переходный | Рефлексивный | Предзаказ | Частичный заказ | Всего предзаказ | Общий заказ | Отношение эквивалентности |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65 536 | 3,994 | 4096 | 355 | 219 | 75 | 24 | 15 |
п | 2 п 2 | 2 п 2 - п | ∑п к = 0 к ! S ( п , к ) | п ! | ∑п к = 0 S ( п , к ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Количество строгих частичных заказов такое же, как и количество частичных заказов.
Если подсчет производится только до изоморфизма, получается последовательность 1, 1, 2, 5, 16, 63, 318,… (последовательность A000112 в OEIS ).
Линейное расширение
Частичный порядок ≤ * на множестве X является расширением другого частичного порядка ≤ на X при условии, что для всех элементов x и y из X , всякий раз, когда x ≤ y , также верно, что x ≤ * y . Линейное расширение является расширением , что также является линейной (т.е. всего) порядка. Классический пример: лексикографический порядок полностью упорядоченных множеств является линейным продолжением порядка их продуктов. Каждый частичный заказ может быть расширен до полного заказа ( принцип расширения заказа ). [10]
В информатике алгоритмы поиска линейных расширений частичных порядков (представленных как порядки достижимости ориентированных ациклических графов ) называются топологической сортировкой .
В теории категорий
Каждый упорядоченный набор (и каждый предварительно упорядоченный набор ) можно рассматривать как категорию, в которой для объектов x и y существует не более одного морфизма от x к y . Более явно, пусть hom ( x , y ) = {( x , y )}, если x ≤ y (в противном случае - пустое множество) и ( y , z ) ∘ ( x , y ) = ( x , z ). Такие категории иногда называют позетальными .
Посеты эквивалентны друг другу тогда и только тогда, когда они изоморфны . В poset наименьший элемент, если он существует, является начальным объектом , а самый большой элемент, если он существует, является конечным объектом . Кроме того, каждый предварительно упорядоченный набор эквивалентен poset. Наконец, каждая подкатегория чугуна изоморфизм-замкнута .
Частичные порядки в топологических пространствах
Если P - частично упорядоченное множество, которому также была задана структура топологического пространства , то принято считать, чтоэто замкнутое подмножество топологического пространства продукта . При этом предположении отношения частичного порядка хорошо себя ведут в пределах в том смысле, что если, а также , и для всех , тогда . [11]
Интервалы
Интервал в посете P является подмножеством я из P со свойством , что для любых х и у в I и любой г в Р , если X ≤ Z ≤ у , то г также находится в I . (Это определение обобщает определение интервала для действительных чисел.)
Для получения более ≤ б , то отрезок [ , Ь ] есть множество элементов х , удовлетворяющих а ≤ х ≤ B (т.е. ≤ х и х ≤ б ). Он содержит как минимум элементы a и b .
Используя соответствующее строгое отношение «<», открытый интервал ( a , b ) - это набор элементов x, удовлетворяющих a < x < b (то есть a < x и x < b ). Открытый интервал может быть пустым, даже если a < b . Например, открытый интервал (1, 2) для целых чисел пуст, поскольку нет таких целых I , что 1 < I <2 .
В полуинтервалах [ , б ) и ( , Ь ] определяются аналогично.
Иногда определения расширяются, чтобы разрешить a > b , и в этом случае интервал пуст.
Интервал I ограничен, если существуют такие элементы a и b из P , что I ⊆ [ a , b ] . Каждый интервал, который может быть представлен в обозначении интервалов, очевидно, ограничен, но обратное неверно. Например, пусть P = (0, 1) ∪ (1, 2) ∪ (2, 3) как подмножество действительных чисел . Подмножество (1, 2) является ограниченным интервалом, но это не имеет никакого инфимуму или супремума в P , поэтому он не может быть записан в интервале обозначений с использованием элементов P .
ЧУМ называется локально конечным, если конечен любой ограниченный интервал. Например, целые числа локально конечны при их естественном порядке. Лексикографический порядок на декартовом произведении ℕ × ℕ не является локально конечным, поскольку (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Используя обозначение интервалов, свойство « a покрывается b » можно эквивалентно перефразировать как [ a , b ] = { a , b }.
Эту концепцию интервала в частичном порядке не следует путать с конкретным классом частичных порядков, известным как интервальные порядки .
Смотрите также
- Антиматроид , формализация порядков на множестве, которая позволяет использовать более общие семейства порядков, чем посеты.
- Причинная совокупность , подход к квантовой гравитации на основе позета
- График сопоставимости
- Полный частичный заказ
- Режиссерский набор
- Градуированный посет
- Алгебра инцидентности
- решетка
- Локально конечный ЧУМ
- Функция Мёбиуса на позах
- Вложенная коллекция наборов
- Многогранник порядка
- Заказанная группа
- Топология Poset , своего рода топологическое пространство, которое может быть определено из любого poset
- Непрерывность Скотта - непрерывность функции между двумя частичными порядками.
- Полурешетка
- Полупорядок
- Стохастическое доминирование
- Строгий слабый порядок - строгий частичный порядок «<», в котором отношение «ни a < b, ни b < a » не является транзитивным.
- Общий заказ
- Дерево (структура данных включения множества)
- Лемма Цорна
Заметки
- ^ Меррифилд, Ричард Э .; Симмонс, Ховард Э. (1989). Топологические методы в химии . Нью-Йорк: Джон Вили и сыновья. С. 28 . ISBN 0-471-83817-9. Проверено 27 июля 2012 года .
Частично упорядоченное множество удобно представить диаграммой Хассе ...
- ^ Симовичи, Дэн А. и Джераба, Чабане (2008). «Частично заказанные наборы» . Математические инструменты для интеллектуального анализа данных: теория множеств, частичные порядки, комбинаторика . Springer. ISBN 9781848002012.
- ^ См. General_relativity # Time_travel.
- ^ Neggers, J .; Ким, Хи Сик (1998), «4.2 Порядок продуктов и лексикографический порядок», Basic Posets , World Scientific, стр. 62–63, ISBN 9789810235895
- ^ Дэйви, BA; Пристли, HA (2002). Введение в решетки и порядок (второе изд.). Нью-Йорк: Издательство Кембриджского университета. С. 17–18 . ISBN 0-521-78451-4.
- ^ PR Halmos (1974). Наивная теория множеств . Springer. п. 82 . ISBN 978-1-4757-1645-0.
- ^ а б Флашка, В .; Ježek, J .; Кепка, Т .; Кортелайнен, Дж. (2007). Транзитивные Затворы бинарных отношений I . Прага: Школа математики - Карлов университет физики. п. 1.Лемма 1.1 (iv). В этом источнике асимметричные отношения называются «строго антисимметричными».
- ^ частичные порядки ≤ и ≼ могут быть разными, но не обязательно
- ↑ Дэйви и Пристли (2002 , стр. 23–24)
- ^ Jech, Thomas (2008) [1973]. Аксиома выбора . Dover Publications . ISBN 978-0-486-46624-8.
- ^ Уорд, Л. Е. Младший (1954). «Частично упорядоченные топологические пространства» . Труды Американского математического общества . 5 (1): 144–161. DOI : 10.1090 / S0002-9939-1954-0063016-5 . hdl : 10338.dmlcz / 101379 .
Рекомендации
- Дешпанде, Джаянт В. (1968). «О непрерывности частичного порядка» . Труды Американского математического общества . 19 (2): 383–386. DOI : 10.1090 / S0002-9939-1968-0236071-7 .
- Шмидт, Гюнтер (2010). Реляционная математика . Энциклопедия математики и ее приложений. 132 . Издательство Кембриджского университета. ISBN 978-0-521-76268-7.
- Бернд Шредер (11 мая 2016 г.). Упорядоченные множества: введение со связями от комбинаторики к топологии . Birkhäuser. ISBN 978-3-319-29788-0.
- Стэнли, Ричард П. (1997). Перечислительная комбинаторика 1 . Кембриджские исследования в области высшей математики. 49 . Издательство Кембриджского университета. ISBN 0-521-66351-2.
Внешние ссылки
- Последовательность OEIS A001035 (количество позиций с n помеченными элементами)
- Последовательность OEIS A000112 (количество частично упорядоченных наборов («наборов») с n непомеченными элементами.)