Ну-квази-упорядочение

Транзитивные бинарные отношения

	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
			Total, Semiconnex					Anti- reflexive
Equivalence relation	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Partial order	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preorder	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total order	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Well-quasi-ordering	✗	✗	✗	Y	✗	✗	Y	✗	✗
Well-ordering	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Strict partial order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict weak order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict total order	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
Definitions, for all $a,b$ and $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$aRa$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by

in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$
A term's definition may require additional properties that are not listed in this table.

В математике , особенно в теории порядка , хорошо квазиупорядочение или wqo на множестве. $X$ представляет квазиупорядочение собой $X$ для которого каждая бесконечная последовательность элементов $x_{0},x_{1},x_{2},\ldots$ от $X$ содержит возрастающую пару $x_{i}\leq x_{j}$ с $i<j.$

Мотивация [ править ]

Хорошо обоснованная индукция может использоваться на любом множестве с хорошо обоснованным отношением , поэтому нас интересует, является ли квазипорядок обоснованным. (Здесь, злоупотребляя терминологией, квазипорядок $\leq$ называется обоснованным, если соответствующий строгий порядок $x\leq y\land y\nleq x$ является вполне обоснованным отношением.) Однако класс обоснованных квазипорядков не замыкается при определенных операциях, то есть когда квазипорядок используется для получения нового квазипорядка на множестве структур, полученных из нашего исходного набора , этот квазипорядок оказывается недостаточно обоснованным. Налагая более строгие ограничения на исходное хорошо обоснованное квазиупорядочение, можно надеяться на то, что наши производные квазиупорядочения по-прежнему будут хорошо обоснованы.

Примером этого является работа набора мощности . Учитывая квазиупорядочение $\leq$ для набора $X$ можно определить квазипорядок $\leq ^{+}$ на $X$ набор мощности $P(X)$ установив $A\leq ^{+}B$ тогда и только тогда, когда для каждого элемента $A$ можно найти некоторый элемент $B$ это больше, чем по отношению к $\leq$ . Можно показать, что это квазиупорядочение на $P(X)$ не обязательно быть хорошо обоснованным, но если исходный квазиупорядочение считать вполне квазиупорядоченным, то так оно и есть.

Формальное определение [ править ]

Хороший квазиупорядочение на множестве $X$ — это квазиупорядочение (т. е. рефлексивное , транзитивное бинарное отношение ), такое, что любая бесконечная последовательность элементов $x_{0},x_{1},x_{2},\ldots$ от $X$ содержит возрастающую пару $x_{i}\leq x_{j}$ с $i<j$ . Набор $X$ Говорят, что оно хорошо квазиупорядочено , или сокращенно wqo .

, Хорошо частичный порядок или wpo , — это wqo, который является правильным отношением порядка, т. е. он антисимметричен .

Среди других способов определения wqo можно сказать, что они являются квазиупорядочениями, которые не содержат бесконечных строго убывающих последовательностей (формы $x_{0}>x_{1}>x_{2}>\cdots$ ) ^[1] ни бесконечные последовательности попарно несравнимых элементов. Следовательно, квазипорядок ( X , ≤) равен wqo тогда и только тогда, когда ( X , <) обоснован и не имеет бесконечных антицепей .

Порядковый номер [ править ]

Позволять $X$ быть хорошо частично упорядоченным. (обязательно конечная) последовательность $(x_{1},x_{2},\ldots ,x_{n})$ элементов $X$ который не содержит пары $x_{i}\leq x_{j}$ с $i<j$ обычно называют плохой последовательностью . Дерево плохих последовательностей $T_{X}$ это дерево, содержащее вершину для каждой плохой последовательности и ребро, соединяющее каждую непустую плохую последовательность. $(x_{1},\ldots ,x_{n-1},x_{n})$ своему родителю $(x_{1},\ldots ,x_{n-1})$ . Корень $T_{X}$ соответствует пустой последовательности. С $X$ не содержит бесконечной плохой последовательности, дерево $T_{X}$ не содержит бесконечного пути, начинающегося с корня. ^{[ нужна ссылка ]} Следовательно, каждая вершина $v$ из $T_{X}$ имеет порядковую высоту $o(v)$ , который определяется трансфинитной индукцией как $o(v)=\lim _{w\mathrm {\ child\ of\ } v}(o(w)+1)$ . Порядковый тип $X$ , обозначенный $o(X)$ , – порядковая высота корня $T_{X}$ .

Линеаризация $X$ является продолжением частичного порядка в тотальный порядок. Легко убедиться в том, что $o(X)$ является верхней границей порядкового типа каждой линеаризации $X$ , Де Йонг и Парих ^[1] доказал, что на самом деле всегда существует линеаризация $X$ который достигает максимального порядкового типа $o(X)$ .

Примеры [ править ]

Рис.1: Целые числа обычного порядка

$(\mathbb {N} ,\leq )$ , набор натуральных чисел со стандартным порядком, является вполне частичным порядком (фактически, хорошим порядком ). Однако, $(\mathbb {Z} ,\leq )$ , набор положительных и отрицательных целых чисел, не является вполне квазипорядком, поскольку он необоснован (см. Рис. 1).
$(\mathbb {N} ,|)$ , множество натуральных чисел, упорядоченное по делимости, не является вполне квазипорядком: простые числа представляют собой бесконечную антицепь (см. Рис.2).
$(\mathbb {N} ^{k},\leq )$ , набор векторов $k$ натуральные числа (где $k$ конечен) с покомпонентным упорядочением , является вполне частичным порядком ( лемма Диксона ; см. рис.3). В более общем смысле, если $(X,\leq )$ вполне квазипорядок, то $(X^{k},\leq ^{k})$ также является квазипорядком для всех $k$ .
Позволять $X$ — произвольное конечное множество, содержащее не менее двух элементов. Набор $X^{*}$ слов более $X$ упорядоченный лексикографически (как в словаре), не является хорошо квазипорядком, поскольку содержит бесконечную убывающую последовательность $b,ab,aab,aaab,\ldots$ . Сходным образом, $X^{*}$ упорядоченная префиксным является отношением, не вполне квазипорядком, поскольку предыдущая последовательность представляет собой бесконечную антицепь этого частичного порядка. Однако, $X^{*}$ упорядоченный по отношению подпоследовательности , является вполне частичным порядком. ^[2] (Если $X$ имеет только один элемент, эти три частичных порядка идентичны.)
В более общем смысле, $(X^{*},\leq )$ , множество конечных $X$ -последовательности, упорядоченные путем встраивания, являются хорошо-квазипорядком тогда и только тогда, когда $(X,\leq )$ является хорошо-квазипорядком ( лемма Хигмана ). Напомним, что встраивают последовательность $u$ в последовательность $v$ найдя подпоследовательность $v$ который имеет ту же длину, что и $u$ и это доминирует в нем срок за сроком. Когда $(X,=)$ представляет собой неупорядоченное множество, $u\leq v$ тогда и только тогда, когда $u$ является подпоследовательностью $v$ .
$(X^{\omega },\leq )$ , множество бесконечных последовательностей над хорошо квазипорядком $(X,\leq )$ , упорядоченный путем встраивания, вообще не является хорошо-квазипорядком. То есть лемма Хигмана не переносится на бесконечные последовательности. Улучшенный квазиупорядочение было введено для обобщения леммы Хигмана на последовательности произвольной длины.
Вложение между конечными деревьями с узлами, помеченными элементами wqo $(X,\leq )$ является wqo ( теорема Краскала о дереве ).
Вложение между бесконечными деревьями с узлами, помеченными элементами wqo $(X,\leq )$ является wqo ( теорема Нэша-Вильямса ).
Вложение между счетными разбросанными типами линейного порядка представляет собой вполне квазипорядок ( теорема Лавера ).
Вложение между счетными булевыми алгебрами является вполне квазипорядком. Это следует из теоремы Лавера и теоремы Кетонена.
Конечные графы, упорядоченные с помощью понятия вложения, называемого « минорным графом », представляют собой хороший квазипорядок ( теорема Робертсона – Сеймура ).
Графы конечной глубины дерева, упорядоченные по индуцированному отношению подграфов, образуют хороший квазипорядок, ^[3] как и кографы, упорядоченные по индуцированным подграфам. ^[4]

Построение новых WPO из имеющихся [ править ]

Позволять $X_{1}$ и $X_{2}$ быть двумя непересекающимися наборами WPO. Позволять $Y=X_{1}\cup X_{2}$ и определим частичный порядок на $Y$ позволяя $y_{1}\leq _{Y}y_{2}$ тогда и только тогда, когда $y_{1},y_{2}\in X_{i}$ для того же самого $i\in \{1,2\}$ и $y_{1}\leq _{X_{i}}y_{2}$ . Затем $Y$ это WPO, и $o(Y)=o(X_{1})\oplus o(X_{2})$ , где $\oplus$ обозначает натуральную сумму ординалов. ^[1]

Данные наборы WPO $X_{1}$ и $X_{2}$ , определите частичный порядок декартова произведения $Y=X_{1}\times X_{2}$ , позволяя $(a_{1},a_{2})\leq _{Y}(b_{1},b_{2})$ тогда и только тогда, когда $a_{1}\leq _{X_{1}}b_{1}$ и $a_{2}\leq _{X_{2}}b_{2}$ . Затем $Y$ — это wpo (это обобщение леммы Диксона ), а $o(Y)=o(X_{1})\otimes o(X_{2})$ , где $\otimes$ обозначает натуральный продукт ординалов. ^[1]

Учитывая набор WPO $X$ , позволять $X^{*}$ — множество конечных последовательностей элементов $X$ , частично упорядоченный отношением подпоследовательности. В смысле, пусть $(x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})$ тогда и только тогда, когда существуют индексы $1\leq i_{1}<\cdots <i_{n}\leq m$ такой, что $x_{j}\leq _{X}y_{i_{j}}$ для каждого $1\leq j\leq n$ . По Хигмана лемме $X^{*}$ это ВПО. Порядковый тип $X^{*}$ является ^[1]^[5]

o(X^{*})={\begin{cases}\omega ^{\omega ^{o(X)-1}},&o(X){\text{ finite}};\\\omega ^{\omega ^{o(X)+1}},&o(X)=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(X)}},&{\text{otherwise}}.\end{cases}}

Учитывая набор WPO $X$ , позволять $T(X)$ — множество всех конечных корневых деревьев, вершины которых помечены элементами $X$ . Частично заказать $T(X)$ по отношению вложения дерева . По теореме Краскала о дереве , $T(X)$ это ВПО. Этот результат нетривиален даже для случая $|X|=1$ (что соответствует немаркированным деревьям), в этом случае $o(T(X))$ равен малому ординалу Веблена . В общем, для $o(X)$ счетно, мы имеем верхнюю оценку $o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))$ с точки зрения $\vartheta$ порядковая схлопывающая функция . (Маленький ординал Веблена равен $\vartheta (\Omega ^{\omega })$ в этом порядковом обозначении.) ^[6]

WQO против частичных заказов скважин [ править ]

На практике манипулирование WQO зачастую не является упорядочением (см. примеры выше), и теория технически более гладкая. ^{[ нужна ссылка ]} если нам не нужна антисимметрия, то она строится на основе wqo в качестве основного понятия. С другой стороны, согласно Милнеру (1985), никакого реального выигрыша в общности не получится, рассматривая квазипорядки, а не частичные порядки... это просто удобнее делать.

Заметим, что wpo является wqo и что wqo порождает wpo между классами эквивалентности, индуцированными ядром wqo. Например, если мы закажем $\mathbb {Z}$ в результате делимости мы получаем $n\equiv m$ тогда и только тогда, когда $n=\pm m$ , так что $(\mathbb {Z} ,|)\approx (\mathbb {N} ,|)$ .

Бесконечные возрастающие подпоследовательности [ править ]

Если $(X,\leq )$ это wqo, то каждая бесконечная последовательность $x_{0},x_{1},x_{2},\ldots ,$ содержит бесконечную возрастающую подпоследовательность $x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots$ (с $n_{0}<n_{1}<n_{2}<\cdots$ ). Такую подпоследовательность иногда называют идеальной .Это можно доказать с помощью аргумента Рамсея : если задана некоторая последовательность $(x_{i})_{i}$ , рассмотрим множество $I$ индексов $i$ такой, что $x_{i}$ не имеет большего или равного $x_{j}$ справа от него, т. е. с $i<j$ . Если $I$ бесконечно, то $I$ -выделенная подпоследовательность противоречит предположению, что $X$ это WQO. Так $I$ конечно, и любое $x_{n}$ с $n$ больше, чем любой индекс в $I$ может использоваться как отправная точка бесконечной возрастающей подпоследовательности.

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

Свойства wqos [ править ]

Учитывая квазиупорядочение $(X,\leq )$ квазиупорядочение $(P(X),\leq ^{+})$ определяется $A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b$ является обоснованным тогда и только тогда, когда $(X,\leq )$ это WQO. ^[7]
Квазиупорядочение является wqo тогда и только тогда, когда соответствующий частичный порядок (полученный факторизацией по $x\sim y\iff x\leq y\land y\leq x$ ) не имеет бесконечных убывающих последовательностей или антицепей . (Это можно доказать, используя аргумент Рэмси , как указано выше.)
Учитывая хорошо квазиупорядоченный $(X,\leq )$ , любая последовательность закрытых вверх подмножеств $S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X$ в конечном итоге стабилизируется (это означает, что существует $n\in \mathbb {N}$ такой, что $S_{n}=S_{n+1}=\cdots$ ; подмножество $S\subseteq X$ называется вверх, закрытым если $\forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S$ ): если предположить обратное $\forall i\in \mathbb {N} ,\exists j\in \mathbb {N} ,j>i,\exists x\in S_{j}\setminus S_{i}$ противоречие достигается путем выделения бесконечной невозрастающей подпоследовательности.
Учитывая хорошо квазиупорядоченный $(X,\leq )$ , любое подмножество $S$ из $X$ имеет конечное число минимальных элементов относительно $\leq$ , иначе минимальные элементы $S$ будет представлять собой бесконечную антицепь.

См. также [ править ]

Улучшенный квазиупорядочение – математические отношения.
Предварительный порядок - концепция теории множеств
Ну-порядок - класс математических порядков.

Примечания [ править ]

^ Здесь x < y означает: $x\leq y$ и $x\neq y.$

Ссылки [ править ]

^ Перейти обратно: ^а ^б ^с ^д де Йонг, Дик Х.Г.; Парих, Рохит (1977). «Ну-частичные порядки и иерархии» . Indagationes Mathematicae (Труды) . 80 (3): 195–207. дои : 10.1016/1385-7258(77)90067-1 .
^ Гасарч, В. (1998), «Обзор рекурсивной комбинаторики», Справочник по рекурсивной математике, Vol. 2 , Студ. Логика найдена. Матем., вып. 139, Амстердам: Северная Голландия, стр. 1041–1176, doi : 10.1016/S0049-237X(98)80049-9 , MR 1673598 . См., в частности, стр. 1160.
^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Лемма 6.13», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, с. 137, номер домена : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7 , МР 2920058 .
^ Дамашке, Питер (1990), «Индуцированные подграфы и хороший квазиупорядочение», Journal of Graph Theory , 14 (4): 427–435, doi : 10.1002/jgt.3190140406 , MR 1067237 .
^ Шмидт, Диана (1979). Хорошо частичные упорядочения и их максимальные типы порядка (Habilitationsschrift). Гейдельберг. Переиздано в: Шмидт, Диана (2020). «Вполне частичные порядки и их максимальные типы порядков». В Шустере, Питер М.; Зайзенбергер, Моника; Вейерманн, Андреас (ред.). Хорошо-квазипорядки в вычислениях, логике, языке и рассуждениях . Тенденции в логике. Том. 53. Спрингер. стр. 351–391. дои : 10.1007/978-3-030-30229-0_13 .
^ Ратьен, Майкл; Вейерманн, Андреас (1993). «Теоретико-доказательные исследования по теореме Краскала» . Анналы чистой и прикладной логики . 60 : 49–88. дои : 10.1016/0168-0072(93)90192-G .
^ Форстер, Томас (2003). «Лучшие квазиупорядочения и коиндукция». Теоретическая информатика . 309 (1–3): 111–123. дои : 10.1016/S0304-3975(03)00131-2 .

Диксон, Л.Е. (1913). «Конечность нечетных совершенных и примитивных обильных чисел с r различными простыми делителями». Американский журнал математики . 35 (4): 413–422. дои : 10.2307/2370405 . JSTOR 2370405 .
Хигман, Г. (1952). «Упорядочение по делимости в абстрактных алгебрах». Труды Лондонского математического общества . 2 : 326–336. дои : 10.1112/plms/s3-2.1.326 .
Краскал, Дж. Б. (1972). «Теория хорошего квазиупорядочения: часто обнаруживаемая концепция» . Журнал комбинаторной теории . Серия А. 13 (3): 297–305. дои : 10.1016/0097-3165(72)90063-5 .
Кетонен, Юсси (1978). «Строение счетных булевых алгебр». Анналы математики . 108 (1): 41–89. дои : 10.2307/1970929 . JSTOR 1970929 .
Милнер, ЕС (1985). «Основы WQO- и BQO-теории». В «Сопернике», И. (ред.). Графики и порядок. Роль графов в теории упорядоченных множеств и ее приложениях . D. Reidel Publishing Co., стр. 487–502. ISBN 90-277-1943-8 .
Галье, Жан Х. (1991). «Что такого особенного в теореме Краскала и ординале Γo? Обзор некоторых результатов теории доказательств». Анналы чистой и прикладной логики . 53 (3): 199–260. дои : 10.1016/0168-0072(91)90022-E .

[dejongh_parikh-1] Перейти обратно: ^а ^б ^с ^д де Йонг, Дик Х.Г.; Парих, Рохит (1977). «Ну-частичные порядки и иерархии» . Indagationes Mathematicae (Труды) . 80 (3): 195–207. дои : 10.1016/1385-7258(77)90067-1 .

[2] Гасарч, В. (1998), «Обзор рекурсивной комбинаторики», Справочник по рекурсивной математике, Vol. 2 , Студ. Логика найдена. Матем., вып. 139, Амстердам: Северная Голландия, стр. 1041–1176, doi : 10.1016/S0049-237X(98)80049-9 , MR 1673598 . См., в частности, стр. 1160.

[3] Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Лемма 6.13», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, с. 137, номер домена : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7 , МР 2920058 .

[4] Дамашке, Питер (1990), «Индуцированные подграфы и хороший квазиупорядочение», Journal of Graph Theory , 14 (4): 427–435, doi : 10.1002/jgt.3190140406 , MR 1067237 .

[schmidt-5] Шмидт, Диана (1979). Хорошо частичные упорядочения и их максимальные типы порядка (Habilitationsschrift). Гейдельберг. Переиздано в: Шмидт, Диана (2020). «Вполне частичные порядки и их максимальные типы порядков». В Шустере, Питер М.; Зайзенбергер, Моника; Вейерманн, Андреас (ред.). Хорошо-квазипорядки в вычислениях, логике, языке и рассуждениях . Тенденции в логике. Том. 53. Спрингер. стр. 351–391. дои : 10.1007/978-3-030-30229-0_13 .

[6] Ратьен, Майкл; Вейерманн, Андреас (1993). «Теоретико-доказательные исследования по теореме Краскала» . Анналы чистой и прикладной логики . 60 : 49–88. дои : 10.1016/0168-0072(93)90192-G .

[forster-7] Форстер, Томас (2003). «Лучшие квазиупорядочения и коиндукция». Теоретическая информатика . 309 (1–3): 111–123. дои : 10.1016/S0304-3975(03)00131-2 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice