Antyłańcuch
Antyłańcuch to termin stosowany w różnych dziedzinach matematyki, odnoszący się do obiektów o specyficznych właściwościach związanych z praporządkami.
Antyłańcuchy w teorii porządków częściowych
Definicja
Zbiór ( A subseteq P ) nazywamy antyłańcuchem w porządku częściowym ( (P, sqsubseteq) ), jeśli dla dowolnych dwóch różnych elementów ( x, y in A ) zachodzi:
[
x neq y Rightarrow neg (x sqsubseteq y vee y sqsubseteq x.
]
Oznacza to, że żadne dwa różne elementy zbioru nie mogą być porównywane.
Własności
- Każdy zbiór jednoelementowy jest antyłańcuchem.
- Porządek częściowy jest liniowy, gdy każdy antyłańcuch jest jednoelementowy.
- Twierdzenie Dilwortha: częściowy porządek nie zawiera ( n+1 ) elementowych antyłańcuchów wtedy i tylko wtedy, gdy jest sumą ( n ) łańcuchów.
- Twierdzenie Spernera: dla rodziny wszystkich podzbiorów ( n )-elementowego zbioru, każdy antyłańcuch ma co najwyżej ( {n choose lfloor{n/2}rfloor} ) elementów.
Antyłańcuchy w teorii forsingu
Definicja
Zbiór ( A subseteq mathbb{P} ) jest antyłańcuchem w forsingu ( (mathbb{P}, leqslant) ), jeśli każde dwa różne warunki ( p, q in A ) są sprzeczne:
[
p neq q Rightarrow neg (exists r in mathbb{P})(r leqslant p wedge r leqslant q).
]
Pojęcie sprzeczności różni się od nieporównywalności w teorii posetów.
(kappa)-cc
Forsing spełnia (kappa)-cc, jeśli każdy antyłańcuch w ( mathbb{P} ) ma moc mniejszą niż ( kappa ). Jeśli ( mathbb{P} ) spełnia (aleph_1)-cc, nazywa się to również warunkiem przeliczalnych antyłańcuchów (ccc).
Własności
- Forsing Cohena spełnia ccc.
- Forsing Solovaya spełnia ccc.
- Forsing Sacksa nie spełnia ccc, gdyż można skonstruować antyłańcuch o mocy continuum.
Antyłańcuchy w algebrach Boole’a
Definicja
W algebrze Boole’a ( (mathbb{B}, vee, wedge, neg, 0, 1) ) zbiór ( A subseteq mathbb{B} setminus {0} ) jest antyłańcuchem, jeśli:
[
a neq b Rightarrow a wedge b = 0.
]
Celularność
Celularność ( c(mathbb{B}) ) algebry Boole’a to supremum mocy antyłańcuchów w ( mathbb{B} ). Algebra spełnia ccc, jeśli ( c(mathbb{B}) leq aleph_0 ). Twierdzenie Erdősa-Tarskiego mówi, że jeśli ( c(mathbb{B}) ) jest liczbą singularną, to istnieje antyłańcuch ( A subseteq mathbb{B} setminus {0} ) o mocy ( c(mathbb{B}) ).
