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

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

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

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

Примеры

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

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

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

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

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

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

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

Пусть [math]\displaystyle{ \langle X, R \rangle }[/math] — фундированное множество, [math]\displaystyle{ P(x) }[/math] — некоторое утверждение об элементах множества [math]\displaystyle{ X }[/math], и пусть мы хотим показать, что [math]\displaystyle{ P(x) }[/math] верно для всех [math]\displaystyle{ x \in X }[/math]. Для этого достаточно показать, что если [math]\displaystyle{ x \in X }[/math], и [math]\displaystyle{ P(y) }[/math] верно для всех таких [math]\displaystyle{ y \in X }[/math], что [math]\displaystyle{ y\, R\, x }[/math], то [math]\displaystyle{ P(x) }[/math] также верно. Другими словами [math]\displaystyle{ \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]

Литература

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