WikiSort.ru - Не сортированное

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

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