Lemat Szanina
Lemat Szanina (Δ-lemat, lemat o Δ-systemie) – twierdzenie kombinatoryki nieskończonej udowodnione przez Nikołaja Szanina w 1946 roku[1]. Lemat Szanina nie jest dowodliwy wyłącznie na gruncie aksjomatyki ZF (to znaczy wymaga pewnej formy aksjomatu wyboru)[2].
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
- Aleksander Błaszczyk, Sławomir Turek: Teoria Mnogości. Warszawa: Wydawnictwo Naukowe PWN, 2007. ISBN 978-83-01-15232-1.
- Thomas Jech: Set theory. The Third Millennium Edition, revised and expanded. Berlin: Springer-Verlag, 2002. ISBN 3-540-44085-2.
- p
- d
- e
rodzaje |
| ||||||
---|---|---|---|---|---|---|---|
tezy |
| ||||||
powiązane pojęcia | |||||||
uogólnienia | |||||||
powiązane nauki | |||||||
badacze |