Русская Википедия:Фундированное множество

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Фундированное множество — частично упорядоченное множество <math>\langle M, R \rangle</math>, у которого любое непустое подмножество <math>S \subseteq M</math> имеет минимальный элемент. Под минимальным элементом в <math>S</math> здесь понимается <math>m \in S</math>, такой, что для любого <math>x \in S</math> из <math>x\, R\, m</math> следует <math>x=m</math>Шаблон:Sfn. В математике фундированное множество также известно как полная полурешётка.

(Некоторые авторыШаблон:Какие дополнительно требуют, чтобы отношение R было связным.)

Эквивалентное определение при условии использования аксиомы выбора состоит в том, что множество M с отношением R является фундированным тогда и только тогда, когда оно удовлетворяет условию обрыва убывающих цепей, то есть не существует бесконечной последовательности x₀, x₁, x₂, … элементов из M такой, что x_n+1 R x_n для любого индекса n.

Примеры

Примеры фундированных множеств без полного порядка.

• Множество целых чисел с частичным порядком a < b тогда и только тогда, когда a делит b и a ≠ b
• Множество всех конечных строк на конечном алфавите с частичным порядком s < t тогда и только тогда, когда s строго включается как подстрока в t

Принцип трансфинитной индукции

Шаблон:Main Пусть <math>\langle M, R \rangle</math> — фундированное множество и <math>S \subseteq M</math>. Тогда если для любого <math>m \in M</math> из включения <math>\{s \in M: s\, R\, m, s \not= m\} \subseteq S</math> следует <math>m \in S</math>, то <math>M</math> совпадает с <math>S</math>Шаблон:Sfn.

Нётерова индукция

Нётерова индукция — это обобщение трансфинитной индукции, которое заключается в следующем.

Пусть <math>\langle X, R \rangle</math> — фундированное множество, <math>P(x)</math> — некоторое утверждение об элементах множества <math>X</math>, и пусть мы хотим показать, что <math>P(x)</math> верно для всех <math>x \in X</math>. Для этого достаточно показать, что если <math>x \in X</math>, и <math>P(y)</math> верно для всех таких <math>y \in X</math>, что <math>y\, R\, x</math>, то <math>P(x)</math> также верно. Другими словами <math>\forall x \in X\,((\forall y\in X\,(y\,R\,x \to P(y))) \to P(x))\to\forall x\in X\,(P(x)).</math>

Литература

• Шаблон:Книга

Шаблон:Math-stub Шаблон:Rq