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

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

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

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

Примеры

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

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

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

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

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

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

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

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