Порядковый тип
Порядковый тип — изоморфный тип частично упорядоченного множества. Неформально говоря порядковый тип — это характеристика, определяющее упорядоченное множество с точностью до изоморфизма, то есть два упорядоченных множества изоморфны тогда и только тогда, когда у них один и тот же порядковый тип.[1]
Некоторые авторы определяют порядковый тип только для линейно-упорядоченных множеств.[2]
Определение
[править | править код]При формальном определении порядкового типа возникают те же трудности, что и при определении мощности множества.
Наивный подход
[править | править код]Простейшим подходом является определение порядкового типа множества как класс изоморфности частично упорядоченных множеств. Назовём порядковым типом частично упорядоченного множества совокупность всех множеств, изоморфных данному. Однако такое определение недопустимо в ZF, поскольку такая совокупность множеств не является множеством в смысле ZF. Для определения порядкового типа в ZF требуется иной подход.[3]
Вполне упорядоченные множества
[править | править код]Для вполне упорядоченного множества порядковый тип обычно определяется как транзитивное множество, вполне упорядоченное отношением принадлежности и с этим порядком изоморфное заданному. Известным фактом является то, что для любого вполне упорядоченного множества существует одно и только одно множество такого вида.
Порядковый тип вполне упорядоченного множества называется ординалом; наряду с кардиналами ординалы образуют одно из возможных расширений множества натуральных чисел.[3]
Трюк Даны Скотта
[править | править код]Определение порядкового типа в ZF для общего случая произвольного частично упорядоченного множества использует ту же самую конструкцию, что и определение мощности множества в ZF — трюк Даны Скотта. Порядковый тип множества определяется не как класс всех изоморфных ему упорядоченных множеств, а как подмножество данного класса, состоящее из всех множеств минимального ранга.[4]
Примеры
[править | править код]- Порядковый тип конечного линейно упорядоченного множества отождествляется с количеством его элементов и, таким образом, является натуральным числом. Поэтому класс всех порядковых типов образует расширение натуральных чисел.[5]
- Порядковый тип множества натуральных чисел обозначается .[6]
- Порядковый тип множества рациональных чисел обозначается .[6]
- Порядковый тип множества действительных чисел обозначается .[6]
Операции
[править | править код]На классе порядковых типов можно определить операции сложения и умножения подобно стандартным арифметическим операциям:
- Сложение. Пусть не пересекающиеся частично упорядоченные множества. Упорядоченной суммой множеств и называется их объединение , упорядоченное следующим отношением порядка:
- .
Упорядоченная сумма обозначается [7] или [6]. Порядковый тип упорядоченной суммы зависит только от порядковых типов её слагаемых и не зависит от конкретных упорядоченных множеств, что позволяет определить эту операцию на порядковых типах. Сумма произвольных порядковых типов и определяется как порядковый тип упорядоченной суммы и , где имеют порядковые типы соответственно. Более кратко:
Как можно видеть, сумма порядковых типов не является коммутативной операцией. Простейший пример: — порядковый тип , однако — порядковый тип .
- Умножение. Пусть некоторые частично упорядоченные множества. Упорядоченным (антилексикографическим) произведением множеств и называется их декартово произведение , упорядоченное следующим отношением порядка:
- .
Упорядоченное произведение обозначается [8] или [9]. Порядковый тип упорядоченного произведения зависит только от порядковых типов его множителей и не зависит от конкретных упорядоченных множеств, что позволяет определить эту операцию на порядковых типах. Произведение произвольных порядковых типов и определяется как порядковый тип упорядоченного произведения и , где имеют порядковые типы соответственно. Более кратко:
Как можно видеть, произведение порядковых типов не является коммутативной операцией. Простейший пример: , однако .
Также часто рассматривают двойственный порядковый тип. Двойственным упорядоченным множеством к называется упорядоченное множество и обозначается как .[10] Порядковый тип зависит только от порядкового типа , поэтому для порядкового типа можно также определить понятие двойственного порядкового типа:
Двойственный порядковый тип к натуральному числу равен тому же натуральному числу . Двойственный порядковый тип к есть порядковый тип множества отрицательных чисел . Сумма равна порядковому типу множества целых чисел. При этом сумма не равна порядковому типу целых чисел.[6] Двойственный порядковый тип к двойственному даёт тот же порядковый тип: .[10]
См. также
[править | править код]Примечания
[править | править код]- ↑ Колмогоров, 1976, с. 33.
- ↑ Laver, 1971, с. 89.
- ↑ 1 2 Just, 1996, с. 156.
- ↑ Jech, 2002, с. 65.
- ↑ Колмогоров, 1976, с. 33-34.
- ↑ 1 2 3 4 5 Just, 1996, с. 24.
- ↑ Колмогоров, 1976, с. 34.
- ↑ Колмогоров, 1976, с. 36.
- ↑ Just, 1996, с. 25.
- ↑ 1 2 Faigle, 1980, с. 48.
Литература
[править | править код]- Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа . — Москва: Наука, 1976. — 543 с.
- Just W., Weese M. Discovering Modern Set Theory. I: The Basics (англ.). — American Mathematical Societ, 1996. — 210 p.
- Jech T. Set theory (англ.). — Springer, 2002. — 769 p.
- Laver R. On Fraisse's Order Type Conjecture (англ.) // Annals of Mathematics : журнал. — 1971. — January (vol. 93, iss. 1). — P. 89–111.
- Faigle U. Geometries on Partially Ordered Sets (англ.) // Journal of Combinatorial Theory : журнал. — 1980. — Vol. 28. — P. 26–51.