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

«Нётерова индукция» перенаправляется сюда. Для использования в топологии см. Нётерово топологическое пространство .

showТранзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

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

$$(\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 .

В теории порядка частичный порядок называется обоснованным, если соответствующий строгий порядок является вполне обоснованным отношением. Если порядок является полным порядком , то его называют « хорошим порядком» .

В теории множеств набор 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 ) также должно быть истинным.

То есть,

$$(\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).$$

Хорошо обоснованную индукцию иногда называют нётеровой индукцией. после Эмми Нётер .

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

$$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 пар 1 натуральных чисел , упорядоченных по формуле ( n _m , n ₂ ) < ( 1 _, m 2 ₎ тогда и только тогда, когда 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 . В контексте натуральных чисел это означает, что отношение <, которое является обоснованным, используется вместо отношения ≤, которое не является таковым. В некоторых текстах определение обоснованного отношения изменено по сравнению с приведенным выше определением, чтобы включить эти соглашения.

Ссылки

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