Type a search term to find related articles by LIMS subject matter experts gathered from the most trusted and dynamic collaboration tools in the laboratory informatics industry.
В теории множеств порядковым числом, или ординалом (лат. ordinalis — порядковый) называется порядковый тип вполне упорядоченного множества. Как правило, порядковые числа отождествляются с наследственно транзитивными множествами. Ординалы представляют собой одно из расширений натуральных чисел, отличающееся как от целых, так и от кардинальных чисел. Как и другие разновидности чисел, их можно складывать, перемножать и возводить в степень. Бесконечные порядковые числа называют трансфинитными (лат. trans — за, через + finitio — край, предел). Ординалы играют ключевую роль в доказательстве многих теорем теории множеств — в частности, благодаря связанному с ними принципу трансфинитной индукции.
Порядковые числа были введены Георгом Кантором в 1883 году как способ описания бесконечных последовательностей, а также классификации множеств, обладающих определённой упорядоченной структурой.[1] Он случайно открыл порядковые числа, работая над задачей, связанной с тригонометрическими рядами.
Множества и обладают одинаковой мощностью, если между ними можно установить биективное соответствие (то есть указать такую функцию , которая одновременно является инъективной и сюръективной: каждому из соответствует единственное из , а каждое из является образом единственного из ).
Предположим, что на множествах и заданы частичные порядки и соответственно. Тогда частично упорядоченные множества и называются изоморфными с сохранением порядка, если существует биективное отображение , при котором заданный порядок сохраняется. Иначе говоря, тогда и только тогда, когда . Любое вполне упорядоченное множество изоморфно с сохранением порядка по отношению к естественно упорядоченному множеству порядковых чисел, меньших некоторого определённого ординала (равного порядковому типу ).
Конечные порядковые (и кардинальные) числа представляют собой числа натурального ряда: 0, 1, 2, …, поскольку два любых полных упорядочения конечного множества изоморфны с сохранением порядка. Наименьшее бесконечно большое порядковое число отождествляется с кардинальным числом . Однако в случае трансфинитных чисел, больших , ординалы — по сравнению с кардинальными числами — позволяют выразить более тонкую классификацию множеств, основанную на информации об их упорядоченности. В то время как все счетные множества описываются одним кардинальным числом, равным , число счетных ординалов бесконечно велико и притом несчетно:
В данном случае сложение и умножение не обладают свойством коммутативности: так, совпадает с , но отличается от ; аналогично , но не равно . Множество всех счетных ординалов образует первое несчетное порядковое число , соответствующее кардинальному числу (следующее число после ). Вполне упорядоченные кардинальные числа отождествляются с их начальными ординалами, то есть минимальными ординалами соответствующей мощности. Мощность порядкового числа задает между классами порядковых и кардинальных чисел соответствие по типу «многие к одному».
Обычно произвольный ординал определяется как порядковый тип множества ординалов, строго меньших . Данное свойство позволяет представить любое порядковое число в виде множества ординалов, строго меньших его самого. Все порядковые числа можно разбить на три категории: нуль, следующее порядковое число и предельное порядковое число (последние различаются своей конфинальностью). Для заданного класса порядковых чисел можно указать его -й элемент — иначе говоря, элементы класса можно проиндексировать (сосчитать). Такой класс будет замкнутым и неограниченным при условии, что функция индексирования непрерывна и никогда не останавливается. Нормальная форма Кантора позволяет единственным образом представить любое порядковое число в виде конечной суммы порядковых степеней . Тем не менее, такая форма не может использоваться в качестве основы для универсальной системы обозначения порядковых чисел из-за наличия в ней автореферентных представлений: например, .
Можно определять все более крупные порядковые числа, однако по мере роста их описание усложняется. Любое порядковое число можно представить в виде топологического пространства, приписав ему порядковую топологию.
Такая топология будет дискретной, тогда и только тогда, когда соответствующий ординал не превышает счётного кардинального числа, то есть меньше или равен . Подмножество будет открытым в порядковой топологии тогда и только тогда, когда оно является кофинитным или не содержит в качестве элемента.
Натуральные числа (к которым в данном случае относится и 0) имеют два основных применения: описание размера некоторого множества и описание позиции элемента в заданной последовательности. В случае конечных множеств эти понятия совпадают; с точностью до изоморфизма существует единственный способ расположить элементы конечного множества в виде последовательности. В случае же бесконечных множеств необходимо отличать понятие размера и связанных с ним кардинальных чисел от понятия позиции, обобщением которого служат описанные в данной статье порядковые числа. Это объясняется тем, что бесконечное множество, обладая однозначно определённым размером (мощностью), может быть вполне упорядочено более чем одним неизоморфным способом.
В то время как понятие кардинального числа, связанного с множеством, не требует задания на нём какой-либо структуры, ординалы тесно связаны с особой разновидностью множеств, которые называются вполне упорядоченными (в сущности эти понятия настолько близки, что некоторые математики не делают между ними никаких различий). Данный термин обозначает линейно упорядоченное множество (то есть множество с некоторым единообразным способом выбора наименьшего и наибольшего значения для произвольной пары элементов), в котором нет бесконечно убывающих последовательностей (хотя могут существовать бесконечно возрастающие), или — в эквивалентной формулировке — множество, в котором любое непустое подмножество содержит наименьший элемент. Порядковые числа можно использовать как для обозначения элементов любого заданного вполне упорядоченного множества (наименьший элемент получает метку 0, следующий за ним — метку 1, следующий — 2, «и так далее»), так и для измерения «размера» всего множества путём указания наименьшего ординала, который не является меткой какого-либо элемента множества. Такой «размер» называется порядковым типом множества.
Любое порядковое число определяется множеством предшествующих ординалов: фактически наиболее распространенное определение порядкового числа отождествляет его со множеством предшествующих ординалов. Так, ординал 42 представляет собой порядковый тип множества предшествующих ординалов, то есть ординалов от 0 (наименьший ординал) до 41 (непосредственный предшественник 42), и обычно отождествляется со множеством . Верно и обратное: любое замкнутое вниз множество ординалов — то есть такое, что для любого ординала и произвольного ординала ординал также является элементом — само является ординалом (либо его можно отождествить с таковым).
До этого момента мы упоминали только конечные ординалы, совпадающие с натуральными числами. Помимо них существуют также и бесконечные ординалы: наименьшим среди них является порядковый тип натуральных чисел (конечных ординалов) , который даже можно отождествить с самим множеством натуральных чисел (действительно: множество натуральных чисел замкнуто вниз и, как любое множество ординалов, является вполне упорядоченным, — следовательно, его можно отождествить с соответствующим порядковым числом, что в точности соответствует определению ).
Вероятно, более интуитивное представление о порядковых числах можно получить, рассмотрев несколько их первых представителей: как уже упоминалось выше, множество ординалов начинается с натуральных чисел После всех натуральных чисел располагается первый бесконечный ординал , за которым следуют , , , и так далее.
После всех таких чисел располагаются (то есть ), , , и так далее, затем , а после него — . Далее, множество ординалов, которые можно записать в виде , где и — натуральные числа, также должно обладать соответствующим порядковым числом: таким числом будет . За ним последуют , ,…, , затем и — намного позже — («эпсилон-нуль») (перечисленные примеры дают представление о сравнительно небольших счетных ординалах). Этот процесс можно продолжать неограниченно (выражение «неограниченности» — это и есть сильная сторона порядковых чисел: собственно говоря, когда мы, перечисляя порядковые числа, употребляем выражение «и так далее», мы тем самым определяем порядковое число большего размера). Наименьший несчетный ординал представляет собой множество всех счетных ординалов и обозначается .
Для обозначения порядковых чисел обычно используются строчные греческие буквы Данная статья придерживается таких обозначений.
Каждое непустое подмножество вполне упорядоченного множества содержит наименьший элемент. При соблюдении аксиомы зависимого выбора это утверждение эквивалентно тому, что множество линейно упорядочено и не содержит бесконечно убывающих последовательностей — последняя формулировка, вероятно, проще поддается визуализации. На практике важность понятия вполне упорядоченности объясняется возможностью применения трансфинитной индукции, основная идея которой сводится к тому, что любое свойство, переходящее от предшественников элемента к нему самому, должно выполняться для всех элементов (входящих в заданное вполне упорядоченное множество). Если вычислительные состояния (компьютерной программы или игры) можно вполне упорядочить так, что каждый последующий шаг будет «меньше» предыдущего, то процесс вычислений гарантированно завершится.
Далее, мы не хотим различать два вполне упорядоченных множества, если они отличаются только «маркировкой своих элементов», или, говоря более формальным языком, если элементы первого множества можно так соотнести с элементами второго, что в произвольно взятой паре элементов одного множества первый меньше второго тогда и только тогда, когда то же соотношение имеет место между их соответствующими партнерам из второго множества. Такое взаимно однозначное соответствие называется изоморфизмом, сохраняющим порядок, а два вполне упорядоченных множества называются изоморфными с сохранением порядка, или же подобными (такое подобие очевидно является отношением эквивалентности). Если два вполне упорядоченных множества изоморфны с сохранением порядка, то соответствующий изоморфизм является единственным: это обстоятельство позволяет воспринимать упомянутые множества как практически идентичные и служит основанием для поисков «каноничного» представления типов изоморфизма (классов). Порядковые числа не только играют роль такого представления, но ещё и предоставляют нам каноническую маркировку элементов любого вполне упорядоченного множества.
Иными словами, мы хотим ввести понятие ординала как класса изоморфизмов вполне упорядоченных множеств, то есть класса эквивалентности, основанного на отношении «изоморфности с сохранением порядка». При таком подходе, однако, существует одна техническая сложность: определённый таким образом класс эквивалентности оказывается слишком большим, чтобы подходить под определением множества с точки зрения стандартной формализации теории множеств по Цермело-Френкелю. Тем не менее, эта сложность не создает серьезных проблем. Ординалом мы будем называть порядковый тип произвольного множества в таком классе.
В первоначальном определении порядкового числа, которое можно встретить, к примеру, в Principia Mathematica, под порядковым типом некоторого вполне-упорядочения понимается множество всех вполне-упорядочений, подобных ему (изоморфных с сохранением порядка): иначе говоря, порядковое число действительно представляет собой класс эквивалентности вполне упорядоченных множеств. В ZFC-теории и связанных с ней аксиоматических системах теории множеств такое определение неприемлемо, поскольку соответствующие классы эквивалентности слишком велики, чтобы их можно было считать множествами. Тем не менее, данное определение можно использовать в теории типов и аксиоматической теории множеств Куайна (Новые основания), а также других подобных системах (в которых оно позволяет сформулировать альтернативный и довольно неожиданный способ разрешения парадокса Бурали-Форти о наибольшем порядковом числе).
Вместо того, чтобы определять ординал как класс эквивалентности вполне упорядоченных множеств, мы отождествим его с конкретным множеством, которое служит каноничным представлением данного класса. Таким образом, ординал будет представлять собой некоторое вполне упорядоченное множество, а любое вполне упорядоченное множество будет подобно ровно одному порядковому числу.
Стандартное определение, предложенное фон Нейманом, звучит следующим образом: любой ординал есть вполне упорядоченное множество, состоящее из всех ординалов, меньших его. В символической записи: .[2][3] Выражаясь более формальным языком,
Заметим, что в соответствии с этим определением натуральные числа являются ординалами. Так, 2 принадлежит 4 = {0, 1, 2, 3} и в то же время равно {0, 1}, то есть является подмножеством {0, 1, 2, 3}.
С помощью трансфинитной индукции можно показать, что любое вполне упорядоченное множество подобно ровно одному ординалу — иначе говоря, между ними можно установить биективное соответствие, сохраняющее порядок.
Более того, элементы любого ординала сами являются ординалами. Если и — произвольные ординалы, то принадлежит тогда и только тогда, когда является собственным подмножеством . Далее, для любых ординалов и выполняется одно из соотношений: либо , либо , либо . Таким образом, любое множество ординалов обладает линейной упорядоченностью и, кроме того, является вполне упорядоченным. Данный результат служит обобщением вполне упорядоченности натуральных чисел.
Отсюда следует, что элементы произвольного ординала в точности совпадают с ординалами, строго меньшими . Каждое множество ординалов, к примеру, обладает супремумом, который представляет собой ординал, равный объединению всех порядковых чисел, содержащихся в данном множестве. В силу аксиомы объединения такой ординал существует всегда, независимо от размера исходного множества.
Класс всех порядковых чисел не является множеством. В противном случае можно было бы доказать, что такое множество само является порядковым числом и, следовательно, своим собственным элементом, что противоречит строгой -упорядоченности. Это утверждение называется парадоксом Бурали-Форти. Класс порядковых чисел обозначается различными способами: «Ord», «ON», или «∞».
Порядковое число конечно тогда и только тогда, когда оно вполне упорядочено не только естественным, но и противоположным порядком — это условие выполняется в том и только в том случае, когда каждое из его подмножеств содержит наибольший элемент.
В современной математике существуют и другие подходы к определению порядковых чисел. Так, при выполнении аксиомы регулярности следующие утверждения относительно множества x являются эквивалентными:
Перечисленные определения неприменимы в теориях множеств без аксиомы фундирования. В теориях с урэлементами определения необходимо уточнить, поскольку урэлементы из числа элементов порядкового числа.
Если — предельный ординал, а — некоторое множество, то -индексированной последовательностью элементов называется функция из в . Введенное таким образом определение трансфинитной последовательности или последовательности, индексированной ординалами, является обобщением понятия последовательности. Обычная последовательность соответствует случаю .
{{citation}}
: |format=
требует |url=
(справка) Архивная копия от 4 апреля 2012 на Wayback Machine — To appear.