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

В математике , А бинарное отношение R называется wellfounded (или wellfounded ) на класс X , если каждое непустое подмножество S ⊆ X имеет минимальный элемент по отношению к R , то есть, элемент м , не связанному с SRM (для Например, « ы не меньше , чем м ») для любого s ∈ S . Другими словами, связь считается обоснованной, если

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

Некоторые авторы включают в себя дополнительное условие , что R будет установлен, как , например, что элементы меньше любого заданного элемента образуют множество.

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

Это,

${\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[yRx\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).}$

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

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

${\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,yRx\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, ...}, с порядком , определенные в < Ь тогда и только тогда , когда а делит Ь и ≠ б .
• множество всех конечных строк в фиксированном алфавите с порядком, определяемым s < t, тогда и только тогда, когда s является правильной подстрокой t .
• множество N × N из пар из натуральных чисел , упорядочены по ( п ₁ , п ₂ ) <( м ₁ , м ₂ ) тогда и только тогда , когда п ₁ < м ₁ и п ₂ < м ₂ .
• набор всех регулярных выражений в фиксированном алфавите с порядком, определяемым s < t, тогда и только тогда, когда s является правильным подвыражением t .
• любой класс, элементы которого являются множествами, с отношением ("является элементом"). Это аксиома регулярности .${\displaystyle \in }$
• узлы любого конечного ориентированного ациклического графа с отношением 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 ≠ b${\displaystyle 1\geq 1\geq 1\geq \cdots .}$. В более общем смысле, при работе с предварительным порядком ≤ обычно используется отношение <, определенное таким образом, что a < b тогда и только тогда, когда a ≤ b и b ≰ a . В контексте натуральных чисел это означает, что отношение <, которое является хорошо обоснованным, используется вместо отношения ≤, которого нет. В некоторых текстах определение хорошо обоснованного отношения изменено с определения выше, чтобы включить эти соглашения.

Ссылки [ править ]

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