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 ℬ₀ ⊆ ℬ – również mocy κ – oraz taki zbiór skończony Δ ⊆ X, że

A ∩ B = Δ

dla wszelkich A, B ∈ ℬ₀, A ≠ B.

Zbiór Δ nazywany bywa czasami korzeniem rodziny ℬ₀.

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 ℬ₁ := ℬ ∩ [κ]ⁿ jest mocy κ, przy czym symbol [κ]ⁿ 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 ℬ ⊆ [κ]ⁿ mocy κ istnieje taka podrodzina ℬ₀ ⊆ ℬ również mocy κ oraz taka liczba porządkowa δ < κ, że dla dowolnych zbiorów A, B ∈ ℬ₀, 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ąć ℬ₀ = ℬ oraz δ = 0 (korzeń rodziny ℬ₀ 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 ℬ'₀ ⊆ { A \ {τ}: A ∈ ℬ'_κ } oraz liczba porządkowa δ_τ < κ, że A ∩ δ_τ = A ∩ B = B ∩ δ_τ dla wszelkich A, B ∈ ℬ₀, A ≠ B. Wystarczy więc przyjąć ℬ₀ = {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ć ℬ₀ := 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 ℬ₀ = {A ∪ {β}: A ∈ ℬ'}.

Przypisy

↑ N. A. Shanin: A theorem from the general theory of sets. „Доклады Академии Наук СССР” (новая серия), 53 (1946), 399–400.
↑ P. Howard, J. Solski: The strength of the Δ-system lemma. „Notre Dame Journal of Formal Logic”, 34 (1, 1992), 100–106.

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.

[1] N. A. Shanin: A theorem from the general theory of sets. „Доклады Академии Наук СССР” (новая серия), 53 (1946), 399–400.

[2] P. Howard, J. Solski: The strength of the Δ-system lemma. „Notre Dame Journal of Formal Logic”, 34 (1, 1992), 100–106.

[1]

[2]