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

Фундированное множество — частично упорядоченное множество $⟨M,R⟩$, у которого любое непустое подмножество $S\subseteq M$ имеет минимальный элемент. Под минимальным элементом в $S$ здесь понимается $m\in S$, такой, что для любого $x\in S$ из $xRm$ следует $x=m$Шаблон:Sfn. В математике фундированное множество также известно как полная полурешётка.

(Некоторые авторыШаблон:Какие дополнительно требуют, чтобы отношение R было связным.)

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

Примеры

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

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

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

Шаблон:Main Пусть $⟨M,R⟩$ — фундированное множество и $S\subseteq M$. Тогда если для любого $m\in M$ из включения $\{s\in M:sRm,s=m\}\subseteq S$ следует $m\in S$, то $M$ совпадает с $S$Шаблон:Sfn.

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

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

Пусть $⟨X,R⟩$ — фундированное множество, $P(x)$ — некоторое утверждение об элементах множества $X$, и пусть мы хотим показать, что $P(x)$ верно для всех $x\in X$. Для этого достаточно показать, что если $x\in X$, и $P(y)$ верно для всех таких $y\in X$, что $yRx$, то $P(x)$ также верно. Другими словами $\mathrm{\forall }x\in X((\mathrm{\forall }y\in X(yRx\to P(y)))\to P(x))\to \mathrm{\forall }x\in X(P(x)).$

Литература

• Шаблон:Книга

Шаблон:Math-stub Шаблон:Нет источников