Фундированное множество

Фундированное множество — частично упорядоченное множество $\langle M, R \rangle$, для которого у любого непустого подмножества $S \subseteq M$ частично упорядоченное множество $\langle S, R \cap S^2 \rangle$ имеет минимальный элемент^[1]. Под минимальным элементом в $\langle S, Q\rangle$ здесь понимается $m \in S$, такой, что для любого $x \in S$ из $x\, Q\, m$ следует $x=m$^[2].

(Некоторые авторы^{[какие?]} дополнительно требуют, чтобы отношение R было связным.)

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

Примеры

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

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

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

Основная статья: Трансфинитная индукция

Пусть $\langle M, R \rangle$ — фундированное множество и $S \subseteq M$. Тогда если для любого $m \in M$ из включения $\{s \in M: s\, R\, m, s \not= m\} \subseteq S$ следует $m \in S$, то $M$ совпадает с $S$^[3].

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

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

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

Примечания

1. ↑ Ершов, Палютин, 1987, с. 73
2. ↑ Ершов, Палютин, 1987, с. 70
3. ↑ Ершов, Палютин, 1987, с. 74

Литература

• Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, 1987. — 336 с.

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.