Хороший порядок - Well-order

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

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

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

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

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

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

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

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

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

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

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

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

0 2 4 6 8 ... 1 3 5 7 9 ...

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

Целые числа

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

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

  1. х = 0
  2. x положительный, а y отрицательный
  3. x и y положительны, а x y
  4. x и y отрицательны, и | х | ≤ | y |

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

0 1 2 3 4 ... −1 −2 −3 ...

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

Еще одно соотношение для правильного упорядочивания целых чисел - это следующее определение: x  ≤ z   y тогда и только тогда, когда (| x | <| y | или (| x | = | y | и x  ≤  y )). Этот порядок скважин можно визуализировать следующим образом:

0 −1 1 −2 2 −3 3 −4 4 ...

Он имеет порядковый тип ω.

Реалы

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

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

  • Натуральные числа являются хорошим порядком при стандартном порядке ≤.
  • Множество {1 / n: n = 1,2,3, ...} не имеет наименьшего элемента и, следовательно, не является хорошим порядком при стандартном порядке ≤.

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

  • Набор чисел {- 2 - n | 0 ≤ n <ω} имеет порядковый тип ω.
  • Набор чисел {- 2 - n - 2 - m - n | 0 ≤ m , n <ω} имеет порядковый тип ω 2 . Предыдущий набор - это набор предельных точек в наборе. В наборе действительных чисел, либо с обычной топологией, либо с топологией порядка, 0 также является предельной точкой набора. Это также предельная точка множества предельных точек.
  • Набор чисел {- 2 - n | 0 ≤ n <ω} ∪ {1} имеет порядковый тип ω + 1. С порядковой топологией этого множества, 1 является его предельной точкой. С обычной топологией (или, что эквивалентно, топологией порядка) вещественных чисел это не так.

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

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

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

Топология заказа

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

В этой топологии могут быть два типа элементов:

  • изолированные точки - это минимум и элементы с предшественником.
  • предельные точки - этот тип не встречается в конечных множествах и может встречаться или не встречаться в бесконечном множестве; бесконечные множества без предельной точки являются множеством типа того , со, например N .

По подмножествам можно выделить:

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

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

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

Смотрите также

Рекомендации

  1. ^ Феферман, С. (1964). «Некоторые приложения понятий принуждения и родовых множеств» . Fundamenta Mathematicae . 56 (3): 325–345. DOI : 10,4064 / фм-56-3-325-345 .