Dowody „just-do-it” w zadaniach o przeliczalności

W zeszłym roku (już po raz drugi!) miałem przyjemność pełnić funkcję tutora podczas obozu Maths Beyond Limits. Poprowadziłem dwie serie zajęć, z których jedna dotyczyła teorii mnogości. Starając się dać uczestnikom podstawy arytmetyki zbiorów nieskończonych w zajmujący i bezbolesny, mam nadzieję, sposób, pokazałem ciekawe zadania, wykorzystujące różne metody i pomysły. Jeden z nich jest szczególnie warty uwagi...

Zadając proste pytanie "Czy istnieje zbiór […] spełniający warunki […]?", można wygenerować wiele zadań. Niektórzy nawet zaznaczą, że przeliczalnie wiele. Struktura zbiorów jest na tyle prosta, że jeśli rozwiązanie istnieje (i przypadkiem nie jest równoważne hipotezie continuum), prawdopodobnie znajdziemy je, korzystając z podstawowych własności funkcji działających na zbiorach. Dodatkowo, czasem warto przeformułować problem, powiązać go z czymś dobrze znanym, pozwalającym lepiej go zwizualizować (np. myśleć o podzbiorach płaszczyzny zamiast o całej płaszczyźnie). Dobrym planem ataku może być więc nie próba znalezienia abstrakcyjnego dowodu, a konstrukcja przykładu metodą just-do-it! Jeżeli zbiór rzeczywiście istnieje, być może nie będzie trudno go znaleźć. Jeżeli zaś pomysły (bądź nerwy) wyczerpią się, można spróbować dowieść jego nieistnienia.

Metodę just-do-it dobrze promuje na swoim blogu Medalista Fieldsa, Tim Gowers, poprzez następujące zadanie:

Zadanie. Czy istnieje gęsty podzbiór płaszczyzny, który nie zawiera trzech współliniowych punktów?

Istnienie takiego zbioru byłoby raczej zaskakujące, mając na uwadze, że zbiory gęste są w pewnym sensie duże (w odniesieniu do zbioru, w którym są gęste), natomiast brak trzech współliniowych punktów sugeruje, że zbiór powinien być mały. Wszelkie wątpliwości znikną jednak, gdy zastosujemy podejście just-do-it. Oczywiście zachęcam Czytelnika do próby samodzielnego rozwiązania przed przejściem do dalszej części tekstu.

Spróbujmy zatem ów zbiór skonstruować. Oznaczmy go przez $. |A$ Wiemy, że zbiór punktów o współrzędnych $|Q × Q$ jest gęsty na płaszczyźnie. Zauważmy, że wystarczy pokazać gęstość zbioru $A$ względem zbioru $|Q × Q.$ Zamiast analizować całą płaszczyznę na raz, rozważmy jej mniejsze kawałki: kule otwarte $|{B((p,q), 1) (p,q) ∈ Q × Q,n ∈ N} n$ o środkach w punktach $Q ×Q$ i promieniach $1 |n.$ Czyli dla każdego punktu z $|Q × Q$ rozważmy przeliczalnie wiele kul (mogą mieć dowolnie mały promień). Przeformułujmy zadanie następująco:

Zadanie. Dany jest przeliczalny zbiór kul otwartych $1,D2,... D$ Czy istnieje zbiór $A$ (podzbiór $Q × Q$ ) taki, że $∩Dn A$ jest niepusty dla każdego $|n$ i żadne trzy punkty z $A$ nie leżą na jednej prostej?

Zbiór $|A$ skonstruujemy indukcyjnie. Niech $|a1$ będzie dowolnym punktem z $, D 1$ natomiast $a 2$ dowolnym punktem z $. D 2$ Dalej, wybierzmy $3a3∈ D$ takie, że nie leży ono na prostej zawierającej $|a1$ i $|a2.$ Kuli otwartej nie da się pokryć skończoną liczbą prostych, zatem na pewno istnieje odpowiednie $a3.$ Tę konstrukcję można kontynuować, co daje finalne rozwiązanie.

Okazuje się zatem, że nasza konstrukcja sprowadza się do kilku pomysłów, które można uogólnić do całej klasy zadań tego typu. Po pierwsze, skorzystaliśmy z faktu, że zbiór $R × R$ ma przeliczalny podzbiór gęsty (jest ośrodkowy). Pozwoliło nam to sprowadzić problem do podobnego, prawie że skończonego i umożliwiło konstrukcję krok po kroku. Jedyne, co pozostało, to zacisnąć zęby i dokończyć rozumowanie.

Podczas moich zajęć wiele zadań można było rozwiązać, korzystając z podobnego rozumowania. Na przykład:

Zadanie. Czy istnieje nieprzeliczalny zbiór parami rozłącznych bałwanków na płaszczyźnie?

Nie można zapomnieć, że funkcje w pewnym sensie są także zbiorami, czyli że o $B f A$ można myśleć jako o podzbiorze $×B. A$ Możemy zatem mieć nadzieję, że pytania o istnienie funkcji o określonych własnościach można rozwiązywać podobnie. Warto przyjrzeć się następującemu zadaniu:

Zadanie. Wykazać, że dla każdej funkcji $g Q × Q R$ istnieje funkcja $| f Q × Q R$ taka, że $f(x, λx +µ ) g(λ,µ)$ przy $x ∞ .$

W przypadku problemów, wystarczy przypomnieć sobie przytoczone rozumowanie i... Just do it!

Tłumaczyli Anna ŁEŃ (MISMaP UW) oraz Paweł PIWEK (Uniwersytet Cambridge)