Предварительный заказ

showТранзитивные   бинарные отношения
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}}$
Y 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 Y 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.

В теории множеств предварительный порядок на множестве $X$ это предзаказ $\leq$ на $X$ ( транзитивное и рефлексивное отношение на $X$), которая сильно связна (то есть любые две точки сравнимы) и обоснована в том смысле, что индуцированное соотношение $x<y$ определяется $x\leq y{\text{ and }}y\nleq x$ это вполне обоснованное отношение .

Предварительный заказ набора

Предварительный заказ на наборе $X$ представляет собой однородное бинарное отношение $\,\leq \,$ на $X$ который удовлетворяет следующим условиям:

1. Рефлексивность : $x\leq x$ для всех $x\in X.$
2. Транзитивность : если $x<y$ и $y<z$ затем $x<z$ для всех $x,y,z\in X.$
3. Всего/Сильные связи : $x\leq y$ или $y\leq x$ для всех $x,y\in X.$
4. для каждого непустого подмножества $S\subseteq X,$ существует какой-то $m\in S$ такой, что $m\leq s$ для всех $s\in S.$
   • Это условие эквивалентно индуцированному строгому предпорядку $x<y$ определяется $x\leq y$ и $y\nleq x$ являющееся вполне обоснованным отношением .

Однородное бинарное отношение $\,\leq \,$ на $X$ является предварительным упорядочением тогда и только тогда, когда существует сюръекция $\pi :X\to Y$ в упорядоченный набор $(Y,\lesssim )$ такой, что для всех $x,y\in X,$ ${\textstyle x\leq y}$ тогда и только тогда, когда $\pi (x)\lesssim \pi (y).$

Примеры

Диаграмма Хассе предварительного упорядочения $\lfloor x/4\rfloor \leq \lfloor y/5\rfloor$ для неотрицательных целых чисел, показанных до 29. Циклы обозначены красным и $\lfloor \cdot \rfloor$ обозначает функцию пола .

Диаграмма Хассе предварительного упорядочения $\lfloor x/4\rfloor \leq \lfloor y/4\rfloor$ на неотрицательных целых числах, показанных до 18. Соответствующее отношение эквивалентности: $\lfloor x/4\rfloor =\lfloor y/4\rfloor ;$ он идентифицирует цифры в каждом светло-красном квадрате.

Учитывая набор $A,$ бинарное отношение на множестве $X:=\operatorname {Finite} (A)$ всех конечных подмножеств $A$ определяется $S\leq T$ тогда и только тогда, когда $|S|\leq |T|$ (где $|\cdot |$ набора обозначает мощность ) является предварительным упорядочением.

Свойства

Если $\leq$ это предварительный заказ на $X,$ тогда отношение $\sim$ определяется

$$x\sim y{\text{ if and only if }}x\leq y\land y\leq x$$

является отношением эквивалентности на $X,$ и $\leq$ индуцирует хорошее частного упорядочение $X/{\sim }.$ Типом порядка этого индуцированного упорядочения является порядковый номер , называемый длиной предупорядочения.

Норма наборе в $X$ это карта из $X$ в порядковые номера. Каждая норма вызывает предварительный порядок; если $\phi :X\to Ord$ является нормой, соответствующий предварительный порядок определяется выражением

$$x\leq y{\text{ if and only if }}\phi (x)\leq \phi (y)$$

И наоборот, любое предупорядочение индуцируется единственной регулярной нормой (нормой $\phi :X\to Ord$ является регулярным, если для любого $x\in X$ и любой $\alpha <\phi (x),$ есть $y\in X$ такой, что $\phi (y)=\alpha$).

Свойство предварительного заказа

Если ${\boldsymbol {\Gamma }}$ это точечный класс подмножеств некоторой коллекции ${\mathcal {F}}$ польских просторов , ${\mathcal {F}}$ замкнуто по декартову произведению , и если $\leq$ является предварительным упорядочением некоторого подмножества $P$ какого-то элемента $X$ из ${\mathcal {F}},$ затем $\leq$ Говорят, что это ${\boldsymbol {\Gamma }}$- приказ шепотом или $P$ если отношения $<^{*}$ и $\leq ^{*}$ являются элементами ${\boldsymbol {\Gamma }},$ где для $x,y\in X,$

1. $x<^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor (x\leq y\land y\not \leq x))$
2. $x\leq ^{*}y{\text{ if and only if }}x\in P\land (y\notin P\lor x\leq y)$

${\boldsymbol {\Gamma }}$ Говорят, что оно обладает свойством предварительного упорядочения, если каждое множество в ${\boldsymbol {\Gamma }}$ признает ${\boldsymbol {\Gamma }}$- пробормотал приказ.

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

Примеры

${\boldsymbol {\Pi }}_{1}^{1}$ и ${\boldsymbol {\Sigma }}_{2}^{1}$ оба обладают свойством prewellordering; это доказуемо только в ZFC . Предполагая достаточно большие кардиналы , для каждого $n\in \omega ,$ ${\boldsymbol {\Pi }}_{2n+1}^{1}$ и ${\boldsymbol {\Sigma }}_{2n+2}^{1}$имеют свойство prewellordering.

Последствия

Сокращение

Если ${\boldsymbol {\Gamma }}$ является адекватным классом точек со свойством prewellordering, то он также обладает свойством сокращения : для любого пространства $X\in {\mathcal {F}}$ и любые наборы $A,B\subseteq X,$ $A$ и $B$ оба в ${\boldsymbol {\Gamma }},$ союз $A\cup B$ можно разделить на наборы $A^{*},B^{*},$ оба в ${\boldsymbol {\Gamma }},$ такой, что $A^{*}\subseteq A$ и $B^{*}\subseteq B.$

Разделение

Если ${\boldsymbol {\Gamma }}$ является адекватным классом точек, которого двойственный класс точек обладает свойством предварительного упорядочения, тогда ${\boldsymbol {\Gamma }}$ имеет свойство разделения : для любого пространства $X\in {\mathcal {F}}$ и любые наборы $A,B\subseteq X,$ $A$ и $B$ непересекающиеся множества как в ${\boldsymbol {\Gamma }},$ есть набор $C\subseteq X$ такой, что оба $C$ и его дополнение $X\setminus C$ находятся в ${\boldsymbol {\Gamma }},$ с $A\subseteq C$ и $B\cap C=\varnothing .$

Например, ${\boldsymbol {\Pi }}_{1}^{1}$ имеет свойство предварительного порядка, поэтому ${\boldsymbol {\Sigma }}_{1}^{1}$ обладает свойством разделения. Это означает, что если $A$ и $B$ являются непересекающимися аналитическими подмножествами некоторого польского пространства. $X,$ тогда существует Бореля подмножество $C$ из $X$ такой, что $C$ включает в себя $A$ и не пересекается с $B.$

См. также

• Описательная теория множеств - раздел математической логики
• Градуированный частично упорядоченный набор — частично упорядоченный набор, оснащенный функцией ранга, иногда называемый ранжированным частично упорядоченным набором. Страницы, отображающие описания викиданных в качестве запасного варианта — градуированный частично упорядоченный набор аналогичен предварительному упорядочению с нормой, заменяя карту порядковых номеров картой натуральных чисел.
• Свойство Scale — вид объекта в описательной теории множеств. Страницы, отображающие описания викиданных в качестве запасного варианта.

Ссылки

• Мошовакис, Яннис Н. (1980). Описательная теория множеств . Амстердам: Северная Голландия. ISBN  978-0-08-096319-8 . OCLC   499778252 .
• Мошовакис, Яннис Н. (2006). Заметки по теории множеств . Нью-Йорк: Спрингер. ISBN  978-0-387-31609-3 . OCLC   209913560 .