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

16.12.2020

Фундированное множество — частично упорядоченное множество ⟨ M , R ⟩ {displaystyle langle M,R angle } , у которого любое непустое подмножество S ⊆ M {displaystyle Ssubseteq M} имеет минимальный элемент. Под минимальным элементом в S {displaystyle S} здесь понимается m ∈ S {displaystyle min S} , такой, что для любого x ∈ S {displaystyle xin S} из x R m {displaystyle x,R,m} следует x = m {displaystyle x=m} . В математике фундированное множество также известно как полная полурешётка.

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

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

Примеры

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

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

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

Пусть ⟨ M , R ⟩ {displaystyle langle M,R angle } — фундированное множество и S ⊆ M {displaystyle Ssubseteq M} . Тогда если для любого m ∈ M {displaystyle min M} из включения { s ∈ M : s R m , s ≠ m } ⊆ S {displaystyle {sin M:s,R,m,s ot =m}subseteq S} следует m ∈ S {displaystyle min S} , то M {displaystyle M} совпадает с S {displaystyle S} .

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

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

Пусть ⟨ X , R ⟩ {displaystyle langle X,R angle } — фундированное множество, P ( x ) {displaystyle P(x)} — некоторое утверждение об элементах множества X {displaystyle X} , и пусть мы хотим показать, что P ( x ) {displaystyle P(x)} верно для всех x ∈ X {displaystyle xin X} . Для этого достаточно показать, что если x ∈ X {displaystyle xin X} , и P ( y ) {displaystyle P(y)} верно для всех таких y ∈ X {displaystyle yin X} , что y R x {displaystyle y,R,x} , то P ( x ) {displaystyle P(x)} также верно. Другими словами ∀ x ∈ X ( ( ∀ y ∈ X ( y R x → P ( y ) ) ) → P ( x ) ) → ∀ x ∈ X ( P ( x ) ) . {displaystyle forall xin X,((forall yin X,(y,R,x o P(y))) o P(x)) o forall xin X,(P(x)).}


Имя:*
E-Mail:
Комментарий: