XXXVI OM - I - Zadanie 7

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 $.

Komentarze

Dodaj nową odpowiedź