Обоснованное отношение

Транзитивные  бинарные отношения в т е
Симметричный Антисимметричный Подключен Обоснованный Имеет соединения Имеет встречает Рефлексивный Нерефлексивный Асимметричный Всего, Полуконнекc Антирефлексивный ​ Отношение эквивалентности И ✗ ✗ ✗ ✗ ✗ И ✗ ✗ Предварительный заказ (квазизаказ) ✗ ✗ ✗ ✗ ✗ ✗ И ✗ ✗ Частичный заказ ✗ И ✗ ✗ ✗ ✗ И ✗ ✗ Всего предзаказов ✗ ✗ И ✗ ✗ ✗ И ✗ ✗ Общий заказ ✗ И И ✗ ✗ ✗ И ✗ ✗ Предварительный заказ ✗ ✗ И И ✗ ✗ И ✗ ✗ Хорошо-квази-упорядочение ✗ ✗ ✗ И ✗ ✗ И ✗ ✗ Хорошо упорядоченный ✗ И И И ✗ ✗ И ✗ ✗ Решетка ✗ И ✗ ✗ И И И ✗ ✗ Join-полурешетка ✗ И ✗ ✗ И ✗ И ✗ ✗ Встреча-полурешетка ✗ И ✗ ✗ ✗ И И ✗ ✗ Строгий частичный порядок ✗ И ✗ ✗ ✗ ✗ ✗ И И Строгий слабый порядок ✗ И ✗ ✗ ✗ ✗ ✗ И И Строгий общий порядок ✗ И И ✗ ✗ ✗ ✗ И И Симметричный Антисимметричный Подключен Обоснованный Имеет соединения Имеет встречает Рефлексивный Нерефлексивный Асимметричный Определения, для всех и${\displaystyle а,б}$${\displaystyle S\neq \varnothing:}$ ${\displaystyle {\begin{align}&aRb\\\Стрелка вправо {}&bRa\end{align}}}$ ${\displaystyle {\begin{align}aRb{\text{ и }}&bRa\\\Стрелка вправо a={}&b\end{align}}}$ ${\displaystyle {\begin{align}a\neq {}&b\Rightarrow \\aRb{\text{ или }}&bRa\end{align}}}$ ${\displaystyle {\begin{align}\min S\\{\text{exists}}\end{align}}}$ ${\displaystyle {\begin{align}a\vee b\\{\text{существует}}\end{align}}}$ ${\displaystyle {\begin{align}a\wedge b\\{\text{существует}}\end{align}}}$ ${\displaystyle аРа}$ ${\displaystyle {\text{не}}aRa}$ ${\displaystyle {\begin{align}aRb\Rightarrow \\{\text{not}}bRa\end{align}}}$
Иуказывает, что свойство столбца всегда верно для термина строки (слева), в то время как ✗ указывает, что свойство не гарантируется в общем случае (оно может выполняться, а может и не выполняться). Например, то, что каждое отношение эквивалентности симметрично, но не обязательно антисимметрично, обозначается в столбце «Симметрично» и ✗ в столбце «Антисимметрично» соответственно.И Все определения неявно требуют, чтобы однородное отношение было транзитивным : для всех, если и то Определение термина может требовать дополнительных свойств, которые не перечислены в этой таблице.${\displaystyle R}$${\displaystyle а,б,в,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

В математике бинарное отношение R называется хорошо обоснованным (или хорошо обоснованным или фундаментальным ^[1] ) на множестве или, в более общем смысле, на классе X , если каждое непустое подмножество S ⊆ X имеет минимальный элемент относительно R ; то есть существует m ∈ S такое, что для любого s ∈ S не существует s R m . Другими словами, отношение является хорошо обоснованным, если: Некоторые авторы включают дополнительное условие, что R подобно множеству , то есть что элементы, меньшие любого заданного элемента, образуют множество.$${\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$$

Эквивалентно, предполагая аксиому зависимого выбора , отношение является обоснованным, когда оно не содержит бесконечных нисходящих цепочек , что может быть доказано, когда не существует бесконечной последовательности x ₀ , x ₁ , x ₂ , ... элементов X такой, что x _{n +1} R x _n для каждого натурального числа n . ^{[2] [3]}

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

В теории множеств множество x называется хорошо обоснованным множеством , если отношение принадлежности множеству хорошо обосновано на транзитивном замыкании x . Аксиома регулярности , которая является одной из аксиом теории множеств Цермело–Френкеля , утверждает, что все множества хорошо обоснованы.

Отношение R является обратно обоснованным , восходящим обоснованным или нётеровым на X , если обратное отношение R ⁻¹ обосновано на X. В этом случае также говорят, что R удовлетворяет условию восходящей цепи . В контексте переписывающих систем нётерово отношение также называется завершающим .

Важной причиной того, что обоснованные отношения интересны, является то, что к ним можно применить версию трансфинитной индукции : если ( X , R ) — обоснованное отношение, P ( x ) — некоторое свойство элементов X , и мы хотим показать, что

P ( x ) справедливо для всех элементов x из X ,

достаточно показать, что:

Если x является элементом X и P ( y ) истинно для всех y таких, что y R x , то P ( x ) также должно быть истинным.

То есть,$${\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).}$$

Обоснованную индукцию иногда называют нётеровской индукцией ^[4] в честь Эмми Нётер .

Наравне с индукцией, хорошо обоснованные отношения также поддерживают построение объектов с помощью трансфинитной рекурсии . Пусть ( X , R ) будет хорошо обоснованным отношением типа множества , а F — функцией, которая назначает объект F ( x , g ) каждой паре элемента x ∈ X и функции g на начальном сегменте { y : y R x } множества X. Тогда существует уникальная функция G такая, что для каждого x ∈ X ,$${\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).}$$

То есть, если мы хотим построить функцию G на X , мы можем определить G ( x ), используя значения G ( y ) для yRx .

В качестве примера рассмотрим хорошо обоснованное отношение ( N , S ) , где N — множество всех натуральных чисел , а S — график функции следования x ↦ x +1 . Тогда индукция по S — это обычная математическая индукция , а рекурсия по S даёт примитивную рекурсию . Если мы рассмотрим отношение порядка ( N , <) , то получим полную индукцию и рекурсию хода значений . Утверждение о том, что ( N , <) хорошо обосновано, также известно как принцип хорошего порядка .

Существуют и другие интересные особые случаи хорошо обоснованной индукции. Когда хорошо обоснованное отношение является обычным упорядочением на классе всех порядковых чисел , метод называется трансфинитной индукцией . Когда хорошо обоснованное множество является множеством рекурсивно определенных структур данных, метод называется структурной индукцией . Когда хорошо обоснованное отношение является набором членства на универсальном классе, метод известен как ∈-индукция . Подробнее см. в этих статьях.

К обоснованным отношениям, которые не являются полностью упорядоченными, относятся:

• Положительные целые числа {1, 2, 3, ...} , порядок которых определяется соотношением a < b , тогда и только тогда, когда a делит b и a ≠ b .
• Множество всех конечных строк над фиксированным алфавитом, порядок которых определяется соотношением s < t тогда и только тогда, когда s является собственной подстрокой t .
• Множество N × N пар натуральных чисел , упорядоченных по соотношению ( n ₁ , n ₂ ) < ( m ₁ , m ₂ ) тогда и только тогда, когда n ₁ < m ₁ и n ₂ < m ₂ .
• Каждый класс, элементы которого являются множествами, с отношением ∈ («является элементом»). Это аксиома регулярности .
• Узлы любого конечного направленного ациклического графа , в котором отношение R определено таким образом, что a R b тогда и только тогда, когда существует ребро из a в b .

Примерами необоснованных отношений являются:

• Отрицательные целые числа {−1, −2, −3, ...} в обычном порядке, поскольку любое неограниченное подмножество не имеет наименьшего элемента.
• Множество строк в конечном алфавите с более чем одним элементом в обычном ( лексикографическом ) порядке, поскольку последовательность "B" > "AB" > "AAB" > "AAAB" > ... является бесконечной нисходящей цепочкой. Это отношение не может быть обосновано, даже если весь набор имеет минимальный элемент, а именно пустую строку.
• Множество неотрицательных рациональных чисел (или действительных чисел ) в стандартном порядке, поскольку, например, подмножество положительных рациональных чисел (или действительных чисел) не имеет минимума.

Если ( X , <) — хорошо обоснованное отношение, а x — элемент X , то все нисходящие цепочки, начинающиеся с x, конечны, но это не означает, что их длины обязательно ограничены. Рассмотрим следующий пример: пусть X — объединение положительных целых чисел с новым элементом ω, который больше любого целого числа. Тогда X — хорошо обоснованное множество, но существуют нисходящие цепочки, начинающиеся с ω произвольно большой (конечной) длины; цепочка ω, n − 1, n − 2, ..., 2, 1 имеет длину n для любого n .

Из леммы Мостовского о коллапсе следует, что принадлежность к множеству является универсальным свойством среди экстенсиональных хорошо обоснованных отношений: для любого хорошо обоснованного отношения R, подобного множеству, на классе X , который является экстенсиональным, существует класс C, такой что ( X , R ) изоморфен ( C , ∈) .

Отношение R называется рефлексивным, если a R a выполняется для каждого a в области отношения. Каждое рефлексивное отношение на непустой области имеет бесконечные нисходящие цепи, потому что любая постоянная последовательность является нисходящей цепью. Например, в натуральных числах с их обычным порядком ≤ мы имеем 1 ≥ 1 ≥ 1 ≥ ... . Чтобы избежать этих тривиальных нисходящих последовательностей, при работе с частичным порядком ≤ обычно применяют определение обоснованности (возможно, неявно) к альтернативному отношению < , определенному таким образом, что a < b тогда и только тогда, когда a ≤ b и a ≠ b . В более общем смысле, при работе с предпорядком ≤ обычно используют отношение < , определенное таким образом, что a < b тогда и только тогда, когда a ≤ b и b ≰ a . В контексте натуральных чисел это означает, что отношение <, которое является обоснованным, используется вместо отношения ≤, которое не является таковым. В некоторых текстах определение обоснованного отношения изменено по сравнению с приведенным выше определением, чтобы включить эти соглашения.

• Джаст, Уинфрид и Визе, Мартин (1998) Открытие современной теории множеств. I , Американское математическое общество ISBN 0-8218-0266-6 . 
• Карел Хрбачек и Томас Йех (1999) Введение в теорию множеств , 3-е издание, «Хорошо обоснованные отношения», страницы 251–255, Марсель Деккер ISBN 0-8247-7915-0