Metoda w przód iw tył

W logice matematycznej , zwłaszcza w teorii mnogości i teorii modeli , metoda wstecz iz powrotem jest metodą pokazywania izomorfizmu między przeliczalnie nieskończonymi strukturami spełniającymi określone warunki. W szczególności można to wykorzystać do udowodnienia tego

dowolne dwa przeliczalnie nieskończone , gęsto uporządkowane zbiory (tj. uporządkowane liniowo w taki sposób, że między dowolnymi dwoma elementami jest inny) bez punktów końcowych są izomorficzne. Izomorfizm między rzędami liniowymi jest po prostu ściśle rosnącą bijekcją . Wynik ten implikuje na przykład, że istnieje ściśle rosnąca bijekcja między zbiorem wszystkich liczb wymiernych a zbiorem wszystkich rzeczywistych liczb algebraicznych .
dowolne dwie przeliczalnie nieskończone bezatomowe algebry Boole'a są względem siebie izomorficzne.
dowolne dwa równoważne policzalne modele atomowe teorii są izomorficzne.
grafów losowych Erdősa -Rényiego , zastosowany do przeliczalnie nieskończonych grafów, prawie na pewno daje unikalny graf, wykres Rado .
dowolne dwa zestawy rekurencyjnie przeliczalne z wieloma kompletami są rekurencyjnie izomorficzne.

Zastosowanie do zbiorów gęsto uporządkowanych

Jako przykład, metodę tam iz powrotem można wykorzystać do udowodnienia twierdzenia o izomorfizmie Cantora , chociaż nie był to oryginalny dowód Georga Cantora . Twierdzenie to stwierdza, że dwa nieograniczone policzalne gęste rzędy liniowe są izomorficzne.

Przypuszczam, że

( A , ≤ _A ) i ( B , ≤ _B ) są zbiorami uporządkowanymi liniowo;
Oba są nieograniczone, innymi słowy, ani A , ani B nie mają maksimum ani minimum;
Są one gęsto uporządkowane, tj. pomiędzy dowolnymi dwoma członami jest inny;
Są policzalnie nieskończone.

Napraw wyliczenia (bez powtórzeń) podstawowych zestawów:

ZA = { za ₁ , za ₂ , za ₃ , ... },

B = { b ₁ , b ₂ , b ₃ , ... }.

Teraz konstruujemy relację jeden do jednego między A i B , która jest ściśle rosnąca. Początkowo żaden członek A nie jest sparowany z żadnym członkiem B .

(1) Niech i będzie najmniejszym indeksem takim, że a _i nie jest jeszcze sparowany z żadnym członkiem B . Niech j będzie takim indeksem, że b _j nie jest jeszcze sparowany z żadnym elementem A i a _i może być sparowany z b _j zgodnie z wymaganiem, aby parowanie było ściśle rosnące. Połącz a _i z b _j .

(2) Niech j będzie najmniejszym indeksem takim, że b _j nie jest jeszcze sparowany z żadnym członkiem A . Niech i będzie takim indeksem, że a _i nie jest jeszcze sparowane z żadnym elementem B , a b _j może być sparowane z a _i zgodnie z wymaganiem, aby parowanie było ściśle rosnące. Sparuj b _j z a _i .

(3) Wróć do kroku (1) .

Należy jeszcze sprawdzić, czy wybór wymagany w kroku (1) i (2) rzeczywiście może zostać dokonany zgodnie z wymaganiami. Używając kroku (1) jako przykładu:

Jeśli istnieją już a _p i a _q w A odpowiadające odpowiednio b _p i b _q w B takie, że a _p < a _i < a _q i b _p < b _q , wybieramy b _j pomiędzy b _p i b _q za pomocą gęstość. W przeciwnym razie wybieramy odpowiedni duży lub mały element B , korzystając z faktu, że B nie ma ani maksimum, ani minimum. Wybory dokonane w kroku (2) są możliwe podwójnie. Ostatecznie konstrukcja kończy się po policzalnie wielu krokach, ponieważ A i B są policzalnie nieskończone. Zauważ, że musieliśmy wykorzystać wszystkie wymagania wstępne.

Historia

Według Hodgesa (1993):

Metody tam iz powrotem są często przypisywane Cantorowi , Bertrandowi Russellowi i CH Langfordowi [...], ale nie ma dowodów na poparcie którejkolwiek z tych atrybucji.

Podczas gdy twierdzenie o policzalnych, gęsto uporządkowanych zbiorach pochodzi od Cantora (1895), metoda „tam iz powrotem”, za pomocą której jest obecnie udowodniona, została opracowana przez Edwarda Vermilye Huntingtona (1904) i Felixa Hausdorffa (1914). Później został zastosowany w innych sytuacjach, zwłaszcza przez Rolanda Fraïssé w teorii modeli .

Zobacz też

Gra Ehrenfeuchta-Fraïsségo

Hausdorff, F. (1914), Grundzüge der Mengenlehre
Hodges, Wilfrid (1993), teoria modeli , Cambridge University Press , ISBN 978-0-521-30442-9
Huntington, EV (1904), Kontinuum i inne rodzaje porządku szeregowego, ze wstępem do liczb pozaskończonych Cantora , Harvard University Press
Marker, David (2002), Model Theory: An Introduction , Graduate Texts in Mathematics , Berlin, Nowy Jork: Springer-Verlag , ISBN 978-0-387-98760-6