XXXVI OM - I - Zadanie 7

Zawody matematyczne:

XXXVI OM, 1984-1985

Etap:

Dana jest rodzina $A$ dwuelementowych podzbiorów zbioru liczb naturalnych. Udowodnić, że istnieje taki podzbiór nieskończony $M$ zbioru liczb naturalnych, że albo wszystkie dwuelementowe podzbiory zbioru $M$ należą do $A$ , albo żaden dwuelementowy podzbiór $M$ nie należy do $A$ .

Rozwiązanie

Określimy indukcyjnie ciąg zstępujący $X_0 \subset X_1 \subset X_2 \subset X_3 \subset \ldots$ podzbiorów nieskończonych zbioru liczb naturalnych $\mathbb{N}$ oraz jeszcze dwa podzbiory zbioru $\mathbb{N}$ , które oznaczymy przez $M'$ i $M''$ .

Przyjmijmy $X_0 =\mathbb{N}$ . Ustalmy $n \in \mathbb{N}$ i przypuśćmy, że zbiór $X_{n-1}$ jest już określony. Niech $x_n$ będzie najmniejszą liczbą w tym zbiorze i niech

$<br /> X'_n = \{x\in X_{n-1}:x> x_n, \, \{x_n, x\} \in A\},<br />$

$<br /> X'_n = \{x \in X_{n-1}: x_n> x, \, \{x, x_n\} \in A\},<br />$

Jeśli zbiór $X'_n$ jest nieskończony, to przyjmujemy $X_n = X'_n$ , a liczbę $x_n$ zaliczamy do zbioru $M'$ . Jeśli zbiór $X'_n$ jest skończony, to $X''_n$ jest nieskończony; przyjmujemy wówczas $X_n = X''_n$ , a liczbę $x_n$ zaliczamy do zbioru $M''$ . Powstałe w ten sposób zbiory $M$ i $M''$ mają własność następującą: jeśli
$x_n,\ x_p \in M'$ , $n < p$ , to para $\{x_n, x_p\}$ należy do $A$ (bo $x_p \in X_{p-1} \subset X_n=X_n'$ ), jeśli zaś $x_n,\ x,_p \in M''$ , $n < p$ , to para $\{x_n, x_p\}$ nie należy do $A$ (bo $x_p \in X_{p-1} \subset X_n=X_n''$ ). Co najmniej jeden ze zbiorów $M'$ i $M''$ jest nieskończony. Jest to szukany zbiór $M$ .
Uwaga. Twierdzenie sformułowane w treści zadania jest szczególnym przypadkiem następującego twierdzenia Ramseya:

Przypuśćmy, że zbiór $D$ wszystkich dwuelementowych podzbiorów zbioru liczb naturalnych został podzielony w dowolny sposób na skończenie wiele rozłącznych części: $D = A_1 \cup \ldots \cup Am$ , $A_i \cap A_j = \emptyset$ dla $i \neq j$ . Wówczas istnieje numer $k\in \{1,\ldots ,m\}$ oraz podzbiór nieskończony $M$ zbioru liczb naturalnych taki, że wszystkie dwuelementowe podzbiory zbioru $M$ należą do $A_k$ .

W naszym zadaniu $m = 2$ , $A_1 = A$ , $A_2 = D \setminus A$ .