Twierdzenie Erdősa-Rado

Nie mylić z: Twierdzenie Erdősa-Ko-Rado.

Twierdzenie Erdősa-Rado – twierdzenie udowodnione przez Paula Erdősa i Richarda Rado^[1] będące rozszerzeniem twierdzenia Ramseya na zbiory odpowiednio dużej mocy.

Notacja

Niech ${\displaystyle \kappa }$ będzie liczbą kardynalną.

• Indukcyjnie definiuje się

${\displaystyle \exp _{0}(\kappa )=\kappa ,}$

${\displaystyle \exp _{r}(\kappa )=2^{\exp _{r-1}(\kappa )}\;\;\;(r=1,2,3,\dots ).}$

• Symbol ${\displaystyle \kappa ^{+}}$ oznacza następnik liczby kardynalnej ${\displaystyle \kappa .}$

Twierdzenie

Niech ${\displaystyle r}$ będzie liczą naturalną oraz niech ${\displaystyle \kappa }$ będzie nieskończoną liczbą kardynalną. Wówczas zachodzi relacja podziałowa

${\displaystyle \exp _{r}(\kappa )^{+}\longrightarrow (\kappa ^{+})_{\kappa }^{r+1},}$

tzn. dla każdego kolorowania ${\displaystyle f}$ rodziny ${\displaystyle (r+1)}$-elementowych podzbiorów zbioru mocy ${\displaystyle \exp _{r}(\kappa )^{+}}$ na ${\displaystyle \kappa }$ kolorów istnieje zbiór monochromatyczny mocy ${\displaystyle \kappa ^{+},}$ tj. taka podrodzina rodziny ${\displaystyle (r+1)}$-elementowych podzbiorów zbioru mocy ${\displaystyle \exp _{r}(\kappa )^{+},}$ na której funkcja ${\displaystyle f}$ jest stała.

Przypisy