- Фундированное множество
-
Фундированное множество — частично упорядоченное множество , для которого у любого непустого подмножества частично упорядоченное множество имеет минимальный элемент[1]. Под минимальным элементом в здесь понимается , такой, что для любого из следует [2].
(Некоторые авторы[какие?] дополнительно требуют, чтобы отношение R было связным.)
Эквивалентное определение при условии использования аксиомы выбора, состоит в том, что множество M с отношением R фундированное тогда и только тогда, когда оно не содержит бесконечно убывающих последовательностей, то есть не существует бесконечной последовательности x0, x1, x2, … элементов из M такой, что xn+1 R xn для любого индекса n.
Примеры
Примеры фундированных множеств без полного порядка.
- Множество целых чисел с частичным порядком a < b тогда и только тогда, когда a делится на b и a ≠ b
- Множество всех конечных строк на конечном алфавите, с частичным порядком s < t тогда и только тогда, когда s строго включается как подстрока в t
Принцип трансфинитной индукции
Пусть — фундированное множество и . Тогда если для любого из включения следует , то совпадает с [3].
Нётерова индукция
Нётерова индукция — это обобщение трансфинитной индукции, которое заключается в следующем.
Пусть — фундированное множество, — некоторое утверждение об элементах множества , и пусть мы хотим показать, что верно для всех . Для этого достаточно показать, что если , и верно для всех таких , что , то также верно. Другими словами
Примечания
- ↑ Ершов, Палютин, 1987, с. 73
- ↑ Ершов, Палютин, 1987, с. 70
- ↑ Ершов, Палютин, 1987, с. 74
Литература
- Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, 1987. — 336 с.
Для улучшения этой статьи желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Категории:- Теория множеств
- Упорядоченные множества
Wikimedia Foundation. 2010.