Упорядоченная последовательность¶

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

¶Определение и свойства

Пусть $M$ — множество, а $\leq$ — отношение на $M$. Отношение $\leq$ называется порядком, если выполняются три условия:

1. Рефлексивность: $a \leq a$ для любого $a \in M$.
2. Антисимметричность: из $a \leq b$ и $b \leq a$ следует $a = b$.
3. Транзитивность: из $a \leq b$ и $b \leq c$ следует $a \leq c$.

Пара $(M, \leq)$ называется частично упорядоченным множеством (частично упорядоченной системой, ЧУМ). Если дополнительно выполняется свойство линейности (сравнимости): для любых $a, b \in M$ либо $a \leq b$, либо $b \leq a$, то порядок называется полным (линейным, тотальным), а множество — линейно упорядоченным.

Строгое отношение $<$ определяется из $\leq$ как: $a < b \iff a \leq b$ и $a \neq b$. Оно удовлетворяет свойствам асимметричности и транзитивности.

¶Виды упорядоченных последовательностей

¶Линейно упорядоченные

Наиболее распространённый тип. Примеры:

• Множество натуральных чисел $\mathbb{N}$ с обычным порядком.
• Множество целых чисел $\mathbb{Z}$.
• Множество рациональных $\mathbb{Q}$ и действительных $\math�{R}$ чисел.
• Слова над алфавитом с лексикографическим порядком.

¶Частично упорядоченные

Не все элементы попарно сравнимы. Типичные примеры:

• Множество подмножеств $M$ с отношением включения $\subseteq$.
• Множество делителей натурального числа с отношением делимости.
• Множество натуральных чисел с отношением «делит» ($a \mid b$).
• Множество подпространств векторного пространства.

¶Всего упорядоченные (well-ordered)

Линейно упорядоченное множество, в котором каждое непустое подмножество имеет наименьший элемент. Пример: натуральные числа. Свойство хорошо упорядоченных множеств лежит в основе трансфинитной индукции и трансфинитной рекурсии.

¶Порядковые числа

Каждому хорошо упорядоченному множеству сопоставляется порядковое число — класс эквивалентности таких множеств относительно изоморфизма. Порядковые числа образуют линейно упорядоченное множество. Первые порядковые числа:

Порядковая арифметика отличается от кардинальной: например, $1 + \omega = \omega$, но $\omega + 1 \neq \omega$.

¶Свойства и теоремы

¶Лемма о сравнении

Для любых двух линейно упорядоченных множеств $A$ и $B$ либо $A$ изоморфно начальному отрезку $B$, либо $B$ изоморфно начальному отрезку $A$.

¶Теорема Кантора — Бернштейна

Для любых двух множеств $A$ и $B$ с $|A| \leq |B|$ и $|B| \leq |A|$ следует $|A| = |B|$.

¶Теорема о хорошо упорядочных множествах

Каждое множество можно хорошо упорядочить (при аксиоме выбора).

¶Лемма Цорна

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

¶Применение

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

¶История

Понятие порядка было формализовано в конце XIX — начале XX века в работах Георга Кантора, Эрнста Цорна, Феликса Хаусдорфа и других математиков, создавших аксиоматическую теорию множеств. Порядковые числа были введены Кантором в 1897 году.

¶Источники

• Куратовский К., Мостовский А. Теория множеств.
• Бурбурский А. А. Введение в теорию упорядоченных множеств.
• Хаусдорф Ф. Теория множеств.
• Шанин Н. А. Введение в теорию множеств.