порядок

В математике хороший порядок (или отношение хорошего порядка или хорошего порядка ) на множестве S $—$ это полный порядок на $S$ , обладающий тем свойством, что каждое непустое подмножество S имеет наименьший элемент в этом порядке $.$ Множество $S$ вместе с упорядочением тогда называется вполне упорядоченным множеством . В некоторых академических статьях и учебниках эти термины вместо этого пишутся как wellorder , wellordered и wellordering или wellorder , wellordered и wellordering .

В каждом непустом хорошо упорядоченном множестве есть наименьший элемент. Каждый элемент $s$ хорошо упорядоченного множества, за исключением возможного наибольшего элемента , имеет уникального преемника (следующий элемент), а именно наименьший элемент подмножества всех элементов, больших $s$ . Помимо наименьшего элемента, могут быть элементы, у которых нет предшественника (пример см. в § Натуральные числа ниже). Хорошо упорядоченное множество $S$ содержит для каждого подмножества $T$ с верхней границей наименьшую верхнюю границу , а именно наименьший элемент подмножества всех верхних границ $T$ в $S.$

Если ≤ — нестрогий колодезный порядок, то < — строгий колодезный порядок. Отношение является строго упорядоченным тогда и только тогда, когда оно является обоснованным строгим тотальным порядком . Различие между строгим и нестрогим порядком скважин часто игнорируется, поскольку они легко взаимоконвертируются.

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

Наблюдение того, что натуральные числа хорошо упорядочены с помощью обычного отношения «меньше», обычно называют принципом хорошего порядка (для натуральных чисел).

Порядковые номера

Каждое хорошо упорядоченное множество однозначно порядково изоморфно уникальному порядковому числу , называемому порядковым типом хорошо упорядоченного множества. Положение каждого элемента в упорядоченном наборе также задается порядковым номером. В случае конечного множества основная операция подсчета — найти порядковый номер конкретного объекта или найти объект с определенным порядковым номером — соответствует присвоению объектам порядковых номеров один за другим. Размер (количество элементов, кардинальное число ) конечного множества равен типу порядка. ^{[ нужна цитация ]} Счет в повседневном смысле обычно начинается с единицы, поэтому каждому объекту присваивается размер начального сегмента с этим объектом в качестве последнего элемента. Обратите внимание, что эти числа на единицу больше, чем формальные порядковые номера в изоморфном порядке, поскольку они равны количеству более ранних объектов (что соответствует счету с нуля). Таким образом, для конечного $n$ выражение « $n$ -й элемент» хорошо упорядоченного набора требует контекста, чтобы знать, считается ли он с нуля или с единицы. В обозначении « $β$ -й элемент», где $β$ также может быть бесконечным порядковым номером, он обычно отсчитывается от нуля.

Для бесконечного набора тип порядка определяет мощность , но не наоборот: хорошо упорядоченные множества определенной мощности могут иметь много разных типов порядка (пример см. § Натуральные числа ниже). Для счетного множества множество возможных типов ордеров несчетно.

Примеры и контрпримеры

Натуральные числа

Стандартный порядок натуральных чисел ≤ является хорошим порядком и обладает дополнительным свойством: каждое ненулевое натуральное число имеет уникального предшественника.

Другой хороший порядок натуральных чисел определяется определением того, что все четные числа меньше всех нечетных чисел, и обычный порядок применяется к четным и нечетным числам:

{\begin{matrix}0&2&4&6&8&\dots &1&3&5&7&9&\dots \end{matrix}}

Это вполне упорядоченное множество порядка типа $ω + ω$ . У каждого элемента есть преемник (самого большого элемента нет). У двух элементов отсутствует предшественник: 0 и 1.

Целые числа

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

Следующее бинарное отношение $R$ является примером правильного упорядочения целых чисел: $x R y$ тогда и только тогда, когда выполняется одно из следующих условий:

$х = 0$
$x$ положительный, а $y$ отрицательный
$x$ и $y$ оба положительны, и $x \leq y$
$x$ и $y$ оба отрицательны, и $| х | \leq | й |$

Это отношение $R$ можно представить следующим образом:

{\begin{matrix}0&1&2&3&4&\dots &-1&-2&-3&\dots \end{matrix}}

$R$ изоморфен порядковому числу $ω + ω$ .

Еще одним соотношением для правильного упорядочения целых чисел является следующее определение: тогда и только тогда, когда $x\leq _ {z}y$

|x|<|y|\qquad {\text{or}}\qquad |x|=|y|{\text{ и }}x\leq y.

Этот порядок скважин можно визуализировать следующим образом:

{\begin{matrix}0&-1&1&-2&2&-3&3&-4&4&\dots \end{matrix}}

Он имеет тип порядка $ω$ .

Реалы

Стандартное упорядочение любого действительного интервала не является хорошим упорядочением, поскольку, например, открытый интервал не содержит ни одного наименьшего элемента. Из аксиом ZFC теории множеств (включая аксиому выбора ) можно показать, что существует хороший порядок вещественных чисел. Также Вацлав Серпинский доказал, что ZF + GCH ( гипотеза обобщенного континуума ) подразумевает аксиому выбора и, следовательно, хороший порядок действительных чисел. Тем не менее, можно показать, что одних аксиом ZFC+GCH недостаточно для доказательства существования определимого (формулой) колодного порядка действительных чисел. ^[1] Однако с ZFC согласуется то, что существует определимый хороший порядок действительных чисел — например, с ZFC согласуется то, что V=L , а из ZFC+V=L следует, что конкретная формула хорошо упорядочивает действительные числа, или вообще любой набор. $(0,1)\subseteq [0,1]$

Несчетное подмножество действительных чисел со стандартным порядком ≤ не может быть хорошим порядком: предположим, что $X$ является подмножеством хорошо упорядоченных по ≤ . Для каждого $x$ в $X$ пусть $s$ $($ $x$ $)$ будет преемником $x$ в порядке ≤ на $X$ (если $x не$ является последним элементом $X$ ). Пусть элементами которого являются непустые и непересекающиеся интервалы. Каждый такой интервал содержит по крайней мере одно рациональное число, поэтому существует инъективная функция от $A$ до. Существует инъекция от $X$ к $A$ (за исключением, возможно, последнего элемента $X$ , который позже может быть отображен в ноль). И хорошо известно, что существует инъекция из натуральных чисел (которые можно выбрать, чтобы избежать попадания в ноль). Таким образом, происходит инъекция $X$ в натуральные числа, а это означает, что $X$ счетно. С другой стороны, счетное бесконечное подмножество действительных чисел может быть или не быть хорошим порядком со стандартом ≤ . Например, $\mathbb {R}$ $A=\{(x,s(x))\,|\,x\in X\}$ $\mathbb {Q} .$ $\mathbb {Q}$

Натуральные числа имеют хороший порядок при стандартном порядке ≤ .
В наборе нет наименьшего элемента, и поэтому он не является хорошо упорядоченным при стандартном порядке ≤ . $\{1/n\,|\,n=1,2,3,\dots \}$

Примеры заказов на скважины:

Множество чисел имеет тип порядка $ω$ . $\{-2^{-n}\,|\,0\leq n<\omega \}$
Множество чисел имеет тип порядка $ω$ $2$ . Предыдущий набор представляет собой набор предельных точек внутри набора. Внутри множества действительных чисел, как с обычной, так и с порядковой топологией, 0 также является предельной точкой набора. Это также предельная точка множества предельных точек. $\{-2^{-n}-2^{-m-n}\,|\,0\leq m,n<\omega \}$
Набор чисел имеет тип порядка $ω$ $+ 1$ . Учитывая порядковую топологию этого набора, 1 является предельной точкой набора. В случае с обычной топологией (или, что то же самое, порядковой топологией ^[^{необходимы пояснения}^] ) действительных чисел это не так. $\{-2^{-n}\,|\,0\leq n<\omega \}\cup \{1\}$

Эквивалентные составы

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

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

Заказать топологию

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

По отношению к этой топологии может быть два типа элементов:

изолированные точки — это минимум и элементы с предшественником.
предельные точки — этот тип не встречается в конечных множествах и может встречаться или не встречаться в бесконечном множестве; бесконечные множества без предельной точки — это множества порядка типа $ω$ , например натуральные числа $\mathbb {N} .$

Среди подмножеств можно выделить:

Подмножества с максимумом (то есть подмножества, ограниченные сами собой); это может быть изолированная точка или предельная точка всего множества; в последнем случае это может быть, а может и не быть, предельной точкой подмножества.
Подмножества, которые не ограничены сами по себе, но ограничены во всем множестве; у них нет максимума, а есть верхняя граница вне подмножества; если подмножество непусто, эта верхняя грань является предельной точкой подмножества, а значит, и всего множества; если подмножество пусто, эта верхняя грань является минимумом всего набора.
Подмножества, неограниченные во всем множестве.

Подмножество является конфинальным во всем множестве тогда и только тогда, когда оно неограничено во всем множестве или имеет максимум, который также является максимальным для всего множества.

Хорошо упорядоченное множество как топологическое пространство является пространством с первой счетностью тогда и только тогда, когда оно имеет тип порядка, меньший или равный ω ₁ ( омега-единица ), то есть тогда и только тогда, когда множество счетно или имеет наименьший неисчисляемый тип заказа.