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

(перенаправлено с «Фундированность»)

Фундированное множество — частично упорядоченное множество , у которого любое непустое подмножество имеет минимальный элемент. Под минимальным элементом в здесь понимается , такой, что для любого из следует [1]. В математике фундированное множество также известно как полная полурешётка.

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

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

Примеры править

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

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

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

Пусть   — фундированное множество и  . Тогда если для любого   из включения   следует  , то   совпадает с  [2].

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

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

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

Примечания править

Литература править

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