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

Фундированное множество — частично упорядоченное множество ${\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)).}$

Примечания[править | править код]

Литература[править | править код]

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

Это заготовка статьи по математике. Помогите Википедии, дополнив её.

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