Lemat Szanina (Δ-lemat, lemat o Δ-systemie) – twierdzenie kombinatoryki nieskończonej udowodnione przez Nikołaja Szanina w 1946 rokuN. A. Shanin: A theorem from the general theory of sets. „Доклады Академии Наук СССР” (новая серия), 53 (1946), 399–400.. Lemat Szanina nie jest dowodliwy wyłącznie na gruncie aksjomatyki ZF (to znaczy wymaga pewnej formy aksjomatu wyboru)P. Howard, J. Solski: The strength of the Δ-system lemma. „Notre Dame Journal of Formal Logic”, 34 (1, 1992), 100–106..
Twierdzenie Niech κ będzie nieprzeliczalną regularną liczbą kardynalną, X będzie zbiorem mocy κ oraz niech ℬ będzie rodziną skończonych podzbiorów X, która sama ma moc κ. Istnieje wówczas taka podrodzina ℬ0 ⊆ ℬ – również mocy κ – oraz taki zbiór skończony Δ ⊆ X, że A ∩ B = Δ dla wszelkich A, B ∈ ℬ0, A ≠ B.
Zbiór Δ nazywany bywa czasami korzeniem rodziny ℬ0.
Dowód Bez straty ogólności można przyjąć, że A = κ, tj. w szczególności, rodzina ℬ składa się ze skończonych podzbiorów liczby kardynalnej κ (rozpatrywanej jako początkowa liczba porządkowa). Ponieważ κ ma nieprzeliczalną kofinalność, istnieje taka liczba naturalna n, że rodzina ℬ1 := ℬ ∩ [κ]n jest mocy κ, przy czym symbol [κ]n oznacza rodzinę wszystkich n-elementowych podzbiorów κ. Wystarczy więc udowodnić następujące stwierdzenie: Niech κ będzie nieskończoną regularną liczbą kardynalną. Wówczas dla każdej liczby naturalnej n oraz każdej rodziny ℬ ⊆ [κ]n mocy κ istnieje taka podrodzina ℬ0 ⊆ ℬ również mocy κ oraz taka liczba porządkowa δ < κ, że dla dowolnych zbiorów A, B ∈ ℬ0, A ≠ B spełniony jest warunek A ∩ δ = A ∩ B = B ∩ δ. Istotnie, w takim przypadku wystarczy przyjąć Δ = A ∩ δ, gdzie A jest dowolnym elementem rodziny ℬ. Dowód można przeprowadzić indukcyjnie ze względu na n. Gdy n = 1, wystarczy wziąć ℬ0 = ℬ oraz δ = 0 (korzeń rodziny ℬ0 jest pusty). Załóżmy, że stwierdzenie to jest prawdziwe dla pewnego n ≥ 1 i ustalmy ℬ ⊆ [κ]n + 1. Jeżeli istnieje takie τ < κ, że rodzina ℬκ = { A ∈ ℬ: min A = τ } jest mocy κ, to z założenia indukcyjnego istnieje taka rodzina ℬ'0 ⊆ { A \ {τ}: A ∈ ℬ'κ } oraz liczba porządkowa δτ < κ, że A ∩ δτ = A ∩ B = B ∩ δτ dla wszelkich A, B ∈ ℬ0, A ≠ B. Wystarczy więc przyjąć ℬ0 = {A ∪ {τ}: A ∈ ℬκ} oraz δ = max{δτ, τ}. Gdyby taka rodzina nie istniała, tj. |{ A ∈ ℬ: min A = τ }| < κ dla każdej liczby τ < κ, to można wówczas zbudować rekursywnie funkcję f: κ → ℬ o tej własności, że ∪ f[α] ⊆ min f(α) dla każdego α < κ. Wystarczy wówczas rozważyć ℬ0 := f[κ] oraz δ = 0. Konstrukcja przykładowej funkcji f o powyższych własnościach. Z założenia, dla każdego τ < κ rodzina ℛτ := { A ∈ ℬ: min A = τ } jest mocy (ściśle) mniejszej od κ. Pozwala to zdefiniować rekurencyjnie funkcję g: κ → κ warunkiem: g(α) = min [{ τ < κ: ℛτ ≠ ∅ } \ sup ∪ ∪ { ℛσ: σ < sup g[α] }]. dla α < κ. Funkcję f można zdefiniować wybierając za f(α) dowolny element rodziny ℛg(α).
Dowód w oparciu o lemat Fodora Niech ℬ = {Fα: α < κ} będzie rodziną skończonych podzbiorów κ. Podobnie jak powyższym dowodzie, bez straty ogólności można założyć, że każdy zbiór Fα ma dokładnie n elementów dla pewnego n ≥ 1. Gdy n = 1, twierdzenie zachodzi (korzeń Δ jest pusty). Ustalmy ℬ ⊆ [κ]n + 1 mocy κ i załóżmy indukcyjnie, że twierdzenie to zachodzi dla n ≥ 1. Niech f: κ → κ ∪ {∞} będzie funkcją określoną w następujący sposób: f(α) = min Fα ∩ [0, α), gdy zbiór Fα ∩ [0, α) jest niepusty oraz f(α) = ∞ w przeciwnym przypadku. Gdy f przyjmuje wartość ∞ dla α z pewnego podzbioru κ mocy κ, to możemy wybrać spośród zbiorów {Fα: α < κ} κ zbiorów parami rozłącznych, co dowodzi twierdzenia w tym przypadku. Gdy nie jest to możliwe, bez straty ogólności możemy przyjąć, że funkcja f przyjmuje wartości wyłącznie w κ. Oznacza to, że f spełnia założenia lematu Fodora, ponieważ f(α) < α dla każdego α < κ. Istnieje zatem zbiór stacjonarny S ⊆ κ (a więc |S| = κ), na którym funkcja f jest stała, tj. dla pewnego β < κ mamy f(α) = β (α ∈ S). W szczególności, β ∈ Fα dla κ wielu α. Można więc zastosować założenie indukcyjne do rodziny {Fα \ {β}: α ∈ S} by otrzymać korzeń Δ' dla pewnej podrodziny ℬ' mocy κ rodziny {Fα \ {β}: α ∈ S}. Ostatecznie, wystarczy przyjąć Δ = Δ' ∪ {β} oraz ℬ0 = {A ∪ {β}: A ∈ ℬ'}.
Przypisy
Bibliografia
S Kategoria:Twierdzenia o nieskończonych liczbach kardynalnych Kategoria:Kombinatoryka