Хорошо обоснованное отношение

Тип бинарного отношения

В математике бинарное отношение R называется обоснованным (или обоснованным или основополагающим ^[1] ) на множестве или , в более общем смысле, классе X , если каждое непустое подмножество S ⊆ X имеет минимальный элемент относительно R ; то есть существует m ∈ S такой, что для любого s ∈ S не существует s R m . Другими словами, отношения являются обоснованными, если:

$${\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$$

Rмножеством

Аналогичным образом, предполагая аксиому зависимого выбора , отношение является обоснованным, если оно не содержит бесконечных нисходящих цепочек , что можно доказать, когда не существует бесконечной последовательности 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 ) для y R x .

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

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

1. См. определение 6.21 в книге Zaring WM, G. Takeuti (1971). Введение в аксиоматическую теорию множеств (2-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0387900241.
2. «Свойство бесконечной последовательности строго обоснованного отношения» . ДоказательствоВики . Проверено 10 мая 2021 г.
3. Фрайсс, Р. (15 декабря 2000 г.). Теория отношений, том 145 - 1-е издание (1-е изд.). Эльзевир. п. 46. ​​ИСБН 9780444505422. Проверено 20 февраля 2019 г.
4. Бурбаки, Н. (1972) Элементы математики. Коммутативная алгебра , Аддисон-Уэсли.

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