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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Примеры[править | править исходный текст]

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

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

Принцип трансфинитной индукции[править | править исходный текст]

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

Нётерова индукция[править | править исходный текст]

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

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