Лексикографический порядок

Лексикографи́ческий поря́док, порядок на прямом произведении

${\displaystyle X=\prod _{\alpha \in L}X_{\alpha }}$

частично упорядоченных множеств ${\displaystyle X_{\alpha }}$, где множество индексов ${\displaystyle L}$ вполне упорядочено, определяемый следующим образом: если ${\displaystyle \left\{x_{\alpha }\right\}}$, ${\displaystyle \left\{y_{\alpha }\right\}\in X}$, то ${\displaystyle \left\{x_{\alpha }\right\}\leqslant \left\{y_{\alpha }\right\}}$ тогда и только тогда, когда либо ${\displaystyle x_{\alpha }=y_{\alpha }}$ для всех ${\displaystyle \alpha \in L}$, либо существует такое ${\displaystyle \alpha \in L}$, что ${\displaystyle x_{\alpha }<y_{\alpha }}$ и ${\displaystyle x_{\beta }=y_{\beta }}$ для всех ${\displaystyle \beta <\alpha }$. Множество ${\displaystyle X}$, упорядоченное лексикографическим порядком, называется лексикографическим, или ординальным, произведением множеств ${\displaystyle X_{\alpha }}$. Если все множества ${\displaystyle X_{\alpha }}$ совпадают между собой (${\displaystyle X_{\alpha }=Y}$ для всех ${\displaystyle \alpha \in L}$), то их лексикографическое произведение называется ординальной степенью множества ${\displaystyle Y}$ и обозначается ${\displaystyle {}^{L}Y}$. Говорят также, что ${\displaystyle X}$ упорядочено по принципу первого различия (как слова упорядочены в словаре). Таким образом, если ${\displaystyle L}$ – натуральный ряд, то

${\displaystyle \left\{x_{1},\ldots ,x_{n},\ldots \right\}<\left\{y_{1},\ldots ,y_{n},\ldots \right\}}$

означает, что для некоторого ${\displaystyle k}$

{{center|${\displaystyle x_{k}<y_{k}}$ для всех ${\displaystyle i<k}$, ${\displaystyle x_{i}=y_{i}}$ (см. Биркгофф. 1952^[1]), однако в этом случае отношение на множестве ${\displaystyle \prod _{\alpha \in L}X_{\alpha }}$ не обязано быть порядком в обычном смысле.</y_k\quad></math></y_\alpha<></math>

Лексикографическое произведение конечного числа вполне упорядоченных множеств вполне упорядочено. Лексикографическое произведение цепей есть цепь.

Для конечного ${\displaystyle L}$ лексикографический порядок рассматривался фактически ещё Г. Кантором (Cantor. 1895^[2]) при определении произведения порядковых типов линейно упорядоченных множеств.

Лексикографический порядок широко используется вне математики, например при упорядочении слов в словарях, справочниках и т. п.