Фундированное множество — частично упорядоченное множество ${\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}$ . В математике фундированное множество также известно как полурешётка .

(Некоторые авторы ^{[ какие? ]} дополнительно требуют, чтобы отношение 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}$ .

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

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

Пусть ${\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)).}$

Примечания

Литература

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

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