Metoda tam a zpět - Back-and-forth method
v matematická logika, zvláště teorie množin a teorie modelů, metoda tam a zpět je metoda zobrazování izomorfismus mezi počítatelně nekonečný struktury splňující stanovené podmínky. Zejména to lze použít k prokázání toho
- jakékoli dvě počítatelně nekonečný hustě nařízeno množiny (tj. lineárně uspořádané tak, že mezi libovolnými dvěma členy je další) bez koncových bodů jsou izomorfní. Izomorfismus mezi lineární objednávky je prostě přísně rostoucí bijekce. Tento výsledek například naznačuje, že mezi množinou všeho existuje přísně rostoucí bijekce racionální čísla a soubor všech nemovitý algebraická čísla.
- jakékoli dva spočítatelné nekonečné atomy Booleovy algebry jsou navzájem izomorfní.
- jakékoli dva ekvivalentní počitatelné atomové modely teorie jsou izomorfní.
- the Erdős – Rényiho model z náhodné grafy, když je aplikován na nespočetně nekonečné grafy, vždy vytvoří jedinečný graf, Rado graf.
- jakékoli dvě mnoho-kompletní rekurzivně spočetné sady jsou rekurzivně izomorfní.
Aplikace na hustě uspořádané sady
Předpokládejme to
- (A, ≤A) a (B, ≤B) jsou lineárně uspořádané množiny;
- Oba jsou neomezení, jinými slovy ani jedno A ani B má buď maximum, nebo minimum;
- Jsou hustě uspořádané, tj. Mezi jakýmikoli dvěma členy je další;
- Jsou nespočetně nekoneční.
Opravte výčty (bez opakování) podkladových sad:
- A = { A1, A2, A3, … },
- B = { b1, b2, b3, … }.
Nyní vytvoříme korespondenci jedna k jedné mezi A a B to se přísně zvyšuje. Zpočátku žádný člen A je spárován s jakýmkoli členem skupiny B.
- (1) Nechat i být nejmenším takovým indexem Ai ještě není spárován s žádným členem skupiny B. Nechat j být nějaký index takový, že bj ještě není spárován s žádným členem skupiny A a Ai lze spárovat s bj důsledně s požadavkem, aby se párování přísně zvyšovalo. Pár Ai s bj.
- (2) Nechat j být nejmenším takovým indexem bj ještě není spárován s žádným členem skupiny A. Nechat i být nějaký index takový, že Ai ještě není spárován s žádným členem skupiny B a bj lze spárovat s Ai důsledně s požadavkem, aby se párování přísně zvyšovalo. Pár bj s Ai.
- (3) Vraťte se zpět ke kroku (1).
Stále je třeba zkontrolovat, zda je v kroku požadována volba (1) a (2) lze skutečně vyrobit v souladu s požadavky. Pomocí kroku (1) jako příklad:
Pokud již existují Astr a Aq v A souhlasí s bstr a bq v B respektive takové, že Astr < Ai < Aq a bstr < bq, vybíráme si bj mezi bstr a bq pomocí hustoty. Jinak zvolíme vhodný velký nebo malý prvek z B díky tomu, že B nemá ani maximum, ani minimum. Volby provedené v kroku (2) jsou duálně možné. Nakonec stavba končí po spočetně mnoha krocích, protože A a B jsou nespočetně nekonečné. Všimněte si, že jsme museli použít všechny předpoklady.
Dějiny
Podle Hodgese (1993):
- Často se připisují metody tam a zpět Cantor, Bertrand Russell a C. H. Langford […], Ale neexistují žádné důkazy na podporu kterékoli z těchto připisování.
Zatímco teorém o spočetných hustě uspořádaných množinách je způsoben Cantorem (1895), metodu tam a zpět, kterou nyní dokazují, vyvinuli Huntington (1904) a Hausdorff (1914). Později to bylo aplikováno v jiných situacích, zejména u Roland Fraïssé v teorie modelů.
Viz také
Reference
- Huntington, E. V. (1904), Kontinuum a další typy sériového řádu s úvodem do Cantorových transfinitních čísel, Harvard University Press
- Hausdorff, F. (1914), Grundzüge der Mengenlehre
- Hodges, Wilfrid (1993), Teorie modelů, Cambridge University Press, ISBN 978-0-521-30442-9
- Marker, David (2002), Teorie modelu: Úvod, Postgraduální texty z matematiky, Berlín, New York: Springer-Verlag, ISBN 978-0-387-98760-6