Порядковый тип

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Порядковый типизоморфный тип частично упорядоченного множества. Неформально говоря порядковый тип — это характеристика, определяющее упорядоченное множество с точностью до изоморфизма, то есть два упорядоченных множества изоморфны тогда и только тогда, когда у них один и тот же порядковый тип.[1]

Некоторые авторы определяют порядковый тип только для линейно-упорядоченных множеств.[2]

Определение

[править | править код]

При формальном определении порядкового типа возникают те же трудности, что и при определении мощности множества.

Наивный подход

[править | править код]

Простейшим подходом является определение порядкового типа множества как класс изоморфности частично упорядоченных множеств. Назовём порядковым типом частично упорядоченного множества совокупность всех множеств, изоморфных данному. Однако такое определение недопустимо в ZF, поскольку такая совокупность множеств не является множеством в смысле ZF. Для определения порядкового типа в ZF требуется иной подход.[3]

Вполне упорядоченные множества

[править | править код]

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

Порядковый тип вполне упорядоченного множества называется ординалом; наряду с кардиналами ординалы образуют одно из возможных расширений множества натуральных чисел.[3]

Трюк Даны Скотта

[править | править код]

Определение порядкового типа в ZF для общего случая произвольного частично упорядоченного множества использует ту же самую конструкцию, что и определение мощности множества в ZFтрюк Даны Скотта. Порядковый тип множества определяется не как класс всех изоморфных ему упорядоченных множеств, а как подмножество данного класса, состоящее из всех множеств минимального ранга.[4]

  • Порядковый тип конечного линейно упорядоченного множества отождествляется с количеством его элементов и, таким образом, является натуральным числом. Поэтому класс всех порядковых типов образует расширение натуральных чисел.[5]
  • Порядковый тип множества натуральных чисел обозначается .[6]
  • Порядковый тип множества рациональных чисел обозначается .[6]
  • Порядковый тип множества действительных чисел обозначается .[6]

На классе порядковых типов можно определить операции сложения и умножения подобно стандартным арифметическим операциям:

  • Сложение. Пусть не пересекающиеся частично упорядоченные множества. Упорядоченной суммой множеств и называется их объединение , упорядоченное следующим отношением порядка:
.

Упорядоченная сумма обозначается [7] или [6]. Порядковый тип упорядоченной суммы зависит только от порядковых типов её слагаемых и не зависит от конкретных упорядоченных множеств, что позволяет определить эту операцию на порядковых типах. Сумма произвольных порядковых типов и определяется как порядковый тип упорядоченной суммы и , где имеют порядковые типы соответственно. Более кратко:

Как можно видеть, сумма порядковых типов не является коммутативной операцией. Простейший пример: — порядковый тип , однако — порядковый тип .

.

Упорядоченное произведение обозначается [8] или [9]. Порядковый тип упорядоченного произведения зависит только от порядковых типов его множителей и не зависит от конкретных упорядоченных множеств, что позволяет определить эту операцию на порядковых типах. Произведение произвольных порядковых типов и определяется как порядковый тип упорядоченного произведения и , где имеют порядковые типы соответственно. Более кратко:

Как можно видеть, произведение порядковых типов не является коммутативной операцией. Простейший пример: , однако .

Также часто рассматривают двойственный порядковый тип. Двойственным упорядоченным множеством к называется упорядоченное множество и обозначается как .[10] Порядковый тип зависит только от порядкового типа , поэтому для порядкового типа можно также определить понятие двойственного порядкового типа:

Двойственный порядковый тип к натуральному числу равен тому же натуральному числу . Двойственный порядковый тип к есть порядковый тип множества отрицательных чисел . Сумма равна порядковому типу множества целых чисел. При этом сумма не равна порядковому типу целых чисел.[6] Двойственный порядковый тип к двойственному даёт тот же порядковый тип: .[10]

Примечания

[править | править код]
  1. Колмогоров, 1976, с. 33.
  2. Laver, 1971, с. 89.
  3. 1 2 Just, 1996, с. 156.
  4. Jech, 2002, с. 65.
  5. Колмогоров, 1976, с. 33-34.
  6. 1 2 3 4 5 Just, 1996, с. 24.
  7. Колмогоров, 1976, с. 34.
  8. Колмогоров, 1976, с. 36.
  9. Just, 1996, с. 25.
  10. 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.