порядок

Транзитивные бинарные отношения

	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
			Total, Semiconnex					Anti- reflexive
Equivalence relation	Y	✗	✗	✗	✗	✗	Y	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Partial order	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total preorder	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total order	✗	Y	Y	✗	✗	✗	Y	✗	✗
Prewellordering	✗	✗	Y	Y	✗	✗	Y	✗	✗
Well-quasi-ordering	✗	✗	✗	Y	✗	✗	Y	✗	✗
Well-ordering	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Strict partial order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict weak order	✗	Y	✗	✗	✗	✗	✗	Y	Y
Strict total order	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Connected	Well-founded	Has joins	Has meets	Reflexive	Irreflexive	Asymmetric
Definitions, for all $a,b$ and $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$aRa$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by

in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$
A term's definition may require additional properties that are not listed in this table.

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

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

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

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

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

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

Каждое хорошо упорядоченное множество однозначно порядково изоморфно уникальному порядковому числу , называемому порядковым типом хорошо упорядоченного множества. Положение каждого элемента в упорядоченном наборе также задается порядковым номером. В случае конечного множества основная операция подсчета — найти порядковый номер конкретного объекта или найти объект с определенным порядковым номером — соответствует присвоению объектам порядковых номеров один за другим. Размер (количество элементов, кардинальное число ) конечного множества равен типу порядка. ^[1] Счет в обычном смысле обычно начинается с единицы, поэтому каждому объекту присваивается размер начального сегмента с этим объектом в качестве последнего элемента. Обратите внимание, что эти числа на единицу больше, чем формальные порядковые номера в изоморфном порядке, поскольку они равны количеству более ранних объектов (что соответствует счету с нуля). Таким образом, для конечного $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{ and }}x\leq y.

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

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

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

Настоящий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Бонне, Реми; Финкель, Ален; Хаддад, Серж; Роза-Велардо, Фернандо (2013). «Порядковая теория выразительности хорошо структурированных переходных систем». Информация и вычисления . 224 : 1–22. дои : 10.1016/j.ic.2012.11.003 . МР 3016456 .
^ Феферман, С. (1964). «Некоторые применения понятий принуждения и родовых множеств» . Фундамента Математика . 56 (3): 325–345. дои : 10.4064/fm-56-3-325-345 .

Фолланд, Джеральд Б. (1999). Реальный анализ: современные методы и их применение . Чистая и прикладная математика (2-е изд.). Уайли . стр. 4–6, 9. ISBN. 978-0-471-31716-6 .

[1] Бонне, Реми; Финкель, Ален; Хаддад, Серж; Роза-Велардо, Фернандо (2013). «Порядковая теория выразительности хорошо структурированных переходных систем». Информация и вычисления . 224 : 1–22. дои : 10.1016/j.ic.2012.11.003 . МР 3016456 .

[2] Феферман, С. (1964). «Некоторые применения понятий принуждения и родовых множеств» . Фундамента Математика . 56 (3): 325–345. дои : 10.4064/fm-56-3-325-345 .

[1]

[2]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice