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