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

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

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

также должно быть истинным.

То есть, $(\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 \in X$ и функции $g$ на начальном сегменте ${y : y R x}$ множества $X.$ Тогда существует уникальная функция $G$ такая, что для каждого $x \in X$ , $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 \mapsto x +1$ . Тогда индукция по $S$ — это обычная математическая индукция , а рекурсия по $S$ даёт примитивную рекурсию . Если мы рассмотрим отношение порядка $(N, <)$ , то получим полную индукцию и рекурсию хода значений . Утверждение о том, что $(N, <)$ хорошо обосновано, также известно как принцип хорошего порядка .

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

Примеры

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

Положительные целые числа ${1, 2, 3, ...}$ , порядок которых определяется соотношением $a < b$ , тогда и только тогда, когда $a$ делит $b$ и $a \neq b$ .
Множество всех конечных строк над фиксированным алфавитом, порядок которых определяется соотношением $s < t$ тогда и только тогда, когда $s$ является собственной подстрокой $t$ .
Множество $N \times N$ пар натуральных чисел , упорядоченных по соотношению $($ $n$ $1$ $,$ $n$ $2$ $) < ($ $m$ $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, \in)$ .

Рефлексивность

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

Ссылки

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

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