„nikt nie wypędzi nas z raju, który dla nas stworzył Cantor” – David Hilbert
czy jest lepszy sposób na spędzenie w izolacji niż rozważanie nieskończoności? Udowodnijmy prawdopodobnie najprostszy i najbardziej elegancki dowód w matematyce: twierdzenie Cantora.
powiedziałem proste i eleganckie, ale nie łatwe!
Część I: Stwierdzenie problemu
twierdzenie Cantora odpowiada na pytanie, czy elementy zbioru można umieścić w korespondencji jeden do jednego („parowanie”) z jego podzbiorami. (Technicznie rzecz biorąc, „bijection”). Ten rodzaj problemu ma związek z pojęciem matematycznym zwanym „cardinality”. Możemy postrzegać korespondencję jeden do jednego jako pewnego rodzaju matematyczne datowanie zbiorów: chcemy, aby każdy element w zbiorze znalazł swoje romantyczne dopasowanie w innym zbiorze, ale chcemy uniknąć poligamii i chcemy uniknąć pojedynczych obiektów matematycznych.
na przykład zestaw {1,2,3} składa się z 3 elementów: 1, 2, 3.
ma 8 podzbiorów: {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {}, {1,2,3}
gdzie {} jest znany jako „pusty zbiór”. Możesz na razie z radością to zignorować, jeśli sprawi, że poczujesz się niekomfortowo: to nie będzie ważne. Alternatywnie, zobacz powyższe jako trzy kulki ponumerowane 1,2,3 i podzbiory jako różne sposoby można umieścić kulki w małym worku. Jedno, co można zrobić, to nic nie wkładać do worka: pusty zestaw.
na razie tak*łatwo*. Wszakże dla skończonych zbiorów okazuje się to dosyć oczywiste. Jeżeli zbiór ma N elementów, to zbiór podzbiorów ma 2 * * N elementów. W powyższym zbiorze {1,2,3} znajdują się 3 elementy, a zbiór podzbiorów (jest to kęs i mylące do czytania, ale spójrz na przykład, aby nie wykorzystać siebie!) posiada 8 elementów. 8 = 2*2*2 = 2**3 tak jak obiecałem.
***polecenie 'zbiór podzbiorów’ może być nieco zniechęcające. Aby poczuć się trochę bardziej komfortowo, najpierw upewnij się, że podzbiór jest sensownym obiektem matematycznym. Jeśli mam jakieś obiekty matematyczne, mogę grupować niektóre z nich, a inne pomijać. Możesz zobaczyć oryginalny zestaw jako wszystkich swoich piłkarzy, a zestaw podzbiorów jako wszystkie potencjalne drużyny, które możesz stworzyć z tych graczy, o dowolnej wielkości. Kiedy dochodzimy do „nieskończonej” liczby graczy, rzeczy mogą być nieco trudniejsze do konceptualizacji, ale podstawowa idea jest taka sama.**
ale Cantor postawił na większe cele. A co z zestawami o nieskończonej liczbie elementów? Czy możemy porównać wielkość dwóch zbiorów z nieskończoną liczbą elementów? (Spoiler: tak.)
krok II: dowód
zakłada, że znalazłeś parowanie, które działa.
czyli masz funkcję, którą wstawiasz do elementu zbioru, A wyjście jest podzbiorem. Nie tylko to, ale dla każdego podzbioru można wskazać element, który zostanie „zmapowany” lub „wysłany” przez funkcję do tego podzbioru. Ponadto, żadne dwa elementy nie są wysyłane do tego samego podzbioru.
w powyższym przykładzie ktoś może zaproponować funkcję, która wysyła 1 do zbioru {1}, 2 do zbioru {2,3} i 3 do zbioru {1,2}. Ale nic nie jest wysyłane do {1,2,3} więc najwyraźniej to nie działa.
aby to uogólnić, Cantor prosi nas o rozważenie „zbioru elementów, które nie są zawarte w podzbiorze, do którego są odwzorowane”. Np. w powyższym 3 jest wysyłane do {1,2} ale 3 nie jest w {1,2} więc pasuje do kryterium ładnie.
w naszej matematyczno-teoretycznej funkcji datowania, ten zestaw również potrzebuje partnera. Ale kto może być partnerem tego zestawu? Jeżeli element jest wysyłany do tego zbioru, to jeżeli jest zawarty w tym zbiorze, to nie może być. (tj. sprzeczność). Dlaczego? Ponieważ jest on zawarty w podzbiorze elementów, do których został zmapowany! A jeśli nie ma go w tym zestawie? Wtedy to też jest sprzecznością, jakby nie było jej w zbiorze, z definicji zbioru musi być w zbiorze, ponieważ nie jest zawarta w podzbiorze, do którego jest odwzorowana.
i tak zrobiona jest czarna magia Cantora. Zakładając, że nasza magiczna matematyczna funkcja datowania zadziałała, znaleźliśmy przykład, w którym nie mogła zadziałać.