Logicko - kombinatorické metódy

Logicko - kombinatorické metódy.

1. Princíp vypojenia a zapojenia.

Veta 1.1.

Nech M₁ .. M_n sú konečné množiny. Pre 'kI1..n : S_k=. Potom =.

Dôkaz.

Nech xIpatrí do m množín. Koľko krát je x zarátaný do ? Do S₁ m-krát, do S_i -krát, do 2^m-krát a teda do = 1-krát. Tým je tvrdenie dokázané.

Veta 1.2.

Nech je množina surjekcií z A do B, |A|=m a B = . Potom =

Dôkaz.

Od všetkých odpočítame nesurjekcie. Označme M(k) množinu funkcií z A do B, ktoré žiaden prvok A nezobrazia na b_k. Je zrejmé, že |M(i₁, .. , i_k)| = (n - k)^m. Potom S_k = .(n - k)^m a použitím formule vypojenia a zapojenia dostávam presne to, čo potrebujem.

Označenie.

Pre systém množín M₁ .. M_n budeme M(r) označovať počet prvkov, ktoré patria práve do r množín a M´(r) počet prvkov, ktoré patria aspoň do r množín.

Veta 1.3.

Nech M₁ .. M_n sú konečné množiny. Potom M(r) =, kde S_k=.

Dôkaz.

Prvok z r množín dáva vklad 1 podľa vety 1.1. Prvky z menej množín nedávajú vklad, lebo kombinačné číslo v sume je pre ne nula. Potrebujeme ešte dokázať, že prvky z viac množín tiež nedávajú vklad. nech x patrí do s > r množín. Potom x dáva vklad , pričom = ==, takže == = (j = k-r) == 0 podľa vety 3.1.3.1 odsek 7.

Veta 1.4.

Nech M₁ .. M_n sú konečné množiny. Potom M´(r) =, kde S_k=.

Dôkaz.

M´(r) ==== (j=k-i) = ===.

2. Spernerova veta.

Veta 2.1.

Nech A₁ .. A_n sú podmnožiny A, z ktorých žiadna nie je podmnožinou inej. Potom Ł 1.

Dôkaz.

Uvažujme reťazec Ć=C₀ĚC₁Ě .. ĚC_m=A, kde |A| = m. Takýchto reťazcov existuje m! (každý reťazec určuje permutáciu A). Ak $iI1..m $jI1..n : C_i=A_j, hovoríme, že reťazec prechádza množinou A_j. Zároveň keďže A₁ .. A_n sú do seba nezapadajúce, žiadny reťazec neprechádza viac ako jednou z nich. Ak |A_j| = r_j, tak množinou A_j prechádza r_j!(n-r_j)! reťazcov (r_j! vchádza a (n-r_j)! vychádza). Ale suma reťazcov, prechádzajúcich cez množiny A₁ .. A_n musí byť menšia ako m!, takže Ł m!, čo tvrdenie dokazuje.

Veta 2.2 (Sperner).

Nech |A| = n a A₁ .. A_m sú konečné neprázdne podmnožiny A, z ktorých žiadna nie je podmnožinou inej. Potom m Ł.

Dôkaz.

Stačí pre iI1..n odhadnúť |A_i|»a použiť predchádzajúcu vetu. =Ł 1 Ű m Ł.

3. Dirichletov princíp.

Veta 3.1.

Nech A,B sú množiny a f : A®B zobrazenie. Ak |A| > |B|, tak $x,yIA : f(x) = f(y).

Dôkaz.

Triviálne.

Dôsledok 3.1.

Nech A,B sú množiny a f : A®B zobrazenie. Ak |A| > k.|B|, tak $x₁..x_k+1IA 'i,jI1..k+1 : f(x_i) = f(x_j).

Dôkaz.

Triviálne.

Dôsledok

Nech A,B sú množiny a f : A®B zobrazenie. Ak A je nekonečná a B je konečná, tak $yIB : f^-1(y) = je nekonečná.

Dôkaz.

Triviálne.