Хорошо обоснованное отношение
В математике бинарное отношение R называется хорошо обоснованным (или хорошо обоснованным , или фундаментальным) . [1] ) на множестве или, в более общем смысле, классе X , если каждое непустое подмножество S ⊆ X имеет минимальный элемент относительно R ; то есть существует m ∈ S такой, что для любого s ∈ S не существует s R m . Другими словами, отношения являются обоснованными, если: Некоторые авторы включают дополнительное условие, согласно которому R является множеством , т. е. элементы, меньшие, чем любой заданный элемент, образуют множество.
Аналогичным образом, предполагая аксиому зависимого выбора , отношение является обоснованным, если оно не содержит бесконечных нисходящих цепей , что можно доказать, когда не существует бесконечной последовательности x 0 , x 1 , x 2 , ... элементов X , таких что x n +1 R x n для каждого натурального числа n . [2] [3]
В теории порядка частичный порядок называется обоснованным, если соответствующий строгий порядок является вполне обоснованным отношением. Если порядок является полным порядком , то его называют « хорошим порядком» .
В теории множеств набор x называется хорошо обоснованным множеством если отношение принадлежности к множеству обосновано на транзитивном замыкании x , . Аксиома регулярности , которая является одной из аксиом теории множеств Цермело–Френкеля , утверждает, что все множества хорошо обоснованы.
Отношение R называется обратно обоснованным , обоснованным снизу вверх или нётеровым на X , если обратное отношение R −1 хорошо обоснован на X . В этом случае R также говорят, что удовлетворяет условию возрастающей цепи . В контексте переписывания систем нётерово отношение также называют завершающим .
Индукция и рекурсия
[ редактировать ]версию трансфинитной индукции Важная причина, по которой хорошо обоснованные отношения интересны, заключается в том, что к ним можно использовать : если ( X , R ) — хорошо обоснованное отношение, P ( x ) — некоторое свойство элементов X , и мы хочу показать это
- P ( x ) выполняется для всех элементов x из X ,
достаточно показать, что:
- Если x является элементом X и P ( y ) истинно для всех y таких, что y R x , то P ( x ) также должно быть истинным.
То есть,
Хорошо обоснованную индукцию иногда называют нётеровской индукцией. [4] после Эмми Нётер .
Наряду с индукцией, хорошо обоснованные отношения также поддерживают построение объектов с помощью трансфинитной рекурсии . Пусть ( X , R ) — множественное обоснованное отношение, а F — функция, которая ставит в соответствие объект F ( x , g ) каждой паре элемента x ∈ X и функции g на начальном отрезке { y : y R x } из X . Тогда существует единственная функция G что для любого x ∈ X такая ,
То есть, если мы хотим построить функцию 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 пар 1 натуральных чисел , упорядоченных по формуле ( n m , n 2 ) < ( 1 , m 2 ) тогда и только тогда, когда n 1 < m 1 и n 2 < m 2 .
- Каждый класс, элементы которого являются множествами с отношением ∈ («является элементом»). Это аксиома регулярности .
- Узлы любого конечного ориентированного ациклического графа с определенным отношением 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 . В контексте натуральных чисел это означает, что отношение <, которое является обоснованным, используется вместо отношения ≤, которое не является таковым. В некоторых текстах определение обоснованного отношения изменено по сравнению с приведенным выше определением, чтобы включить эти соглашения.
Ссылки
[ редактировать ]- ^ См. определение 6.21 в Заринг В.М., Г. Такеути (1971). Введение в аксиоматическую теорию множеств (2-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0387900241 .
- ^ «Свойство бесконечной последовательности строго обоснованного отношения» . ДоказательствоВики . Проверено 10 мая 2021 г.
- ^ Фрайсс, Р. (15 декабря 2000 г.). Теория отношений, том 145 - 1-е издание (1-е изд.). Эльзевир. п. 46. ИСБН 9780444505422 . Проверено 20 февраля 2019 г.
- ^ Бурбаки, Н. (1972) Элементы математики. Коммутативная алгебра , Аддисон-Уэсли.
- Джаст, Винфрид и Виз, Мартин (1998) Открытие современной теории множеств. Я , Американское математическое общество ISBN 0-8218-0266-6 .
- Карел Хрбачек и Томас Йех (1999) Введение в теорию множеств , 3-е издание, «Обоснованные отношения», страницы 251–5, Марсель Деккер ISBN 0-8247-7915-0