Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивности и рефлексивности . |
В математике , А также порядка (или хорошо заказывающий или отношение хорошо заказ ) на множестве 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 тогда и только тогда, когда выполняется одно из следующих условий:
- х = 0
- x положительный, а y отрицательный
- x и y положительны, и x ≤ y
- 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 недостаточно для доказательства существования определяемого (с помощью формулы) правильного порядка вещественных чисел. [1] Однако 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 является его предельной точкой. С обычной топологией (или, что эквивалентно, топологией порядка) вещественных чисел это не так.
Эквивалентные составы
Если набор полностью заказан , то следующие элементы эквивалентны друг другу:
- Набор хорошо заказан. То есть каждое непустое подмножество имеет наименьший элемент.
- Трансфинитная индукция работает для всего упорядоченного множества.
- Каждая строго убывающая последовательность элементов множества должна завершаться только после конечного числа шагов (в предположении аксиомы зависимого выбора ).
- Каждый подзаказ изоморфен начальному отрезку.
Топология заказа
Каждое упорядоченное множество можно превратить в топологическое пространство , наделив его топологией порядка .
В этой топологии могут быть два типа элементов:
- изолированные точки - это минимум и элементы с предшественником.
- предельные точки - этот тип не встречается в конечных множествах и может встречаться или не встречаться в бесконечном множестве; бесконечные множества без предельной точки являются множеством типа того , со, например N .
По подмножествам мы можем выделить:
- Подмножества с максимумом (то есть подмножества, которые ограничены сами по себе); это может быть отдельная точка или предельная точка всего множества; в последнем случае это может быть или не быть также предельной точкой подмножества.
- Подмножества, которые не ограничены сами по себе, но ограничены во всем наборе; у них нет максимума, но есть супремум вне подмножества; если подмножество не пусто, эта верхняя грань является предельной точкой подмножества, а следовательно, и всего набора; если подмножество пусто, этот супремум является минимумом всего набора.
- Подмножества, неограниченные во всем наборе.
Подмножество является конфинальным во всем наборе тогда и только тогда, когда оно неограничено во всем наборе или имеет максимум, который также является максимумом всего множества.
Хорошо упорядоченное множество как топологическое пространство является первым счетным пространством тогда и только тогда, когда оно имеет тип порядка меньше или равен ω 1 ( омега-один ), то есть тогда и только тогда, когда множество является счетным или имеет наименьшее бесчисленный тип ордера.
Смотрите также
- Дерево (теория множеств) , обобщение
- Порядковый номер
- Обоснованный набор
- Ну частичный порядок
- Предварительный заказ
- Режиссерский набор
Рекомендации
- ^ Феферман, С. (1964). «Некоторые приложения понятий принуждения и родовых множеств» . Fundamenta Mathematicae . 56 (3): 325–345. DOI : 10,4064 / фм-56-3-325-345 .
- Фолланд, Джеральд Б. (1999). Реальный анализ: современные методы и их приложения . Чистая и прикладная математика (2-е изд.). Вайли . С. 4–6, 9. ISBN 978-0-471-31716-6.