Oda-vissza módszer

A matematikai logikában , különösen a halmazelméletben és a modellelméletben , az oda-vissza módszer egy bizonyos feltételeket kielégítő, megszámlálható struktúrák közötti izomorfizmus bemutatására szolgál .

Használ

Az oda-vissza a módszer a végtelen megszámlálható halmazok , amelyek egy bizonyos struktúrát (a logikai értelemben). Lehetővé teszi e halmazok közötti bijekció felépítését, olyan bijekciót, amelynek tulajdonságai megőrzik a szerkezetet, ezért ez izomorfizmus . Íme néhány példa:

A módszer használható annak igazolására, hogy a két sűrű megrendelt készletek (azaz teljesen rendezett és oly módon, hogy a két különböző elemből, mindig van egy harmadik) megszámlálható nélkül extremális elem izomorf (izomorfizmus között teljesen rendezett egy szigorúan monoton növekvő bijekciót ). Ez az eredmény azt jelenti például, hogy szigorúan növekvő bijekciók vannak a racionális számok halmaza és az algebrai számok halmaza között .
Ez lehetővé teszi annak megmutatását, hogy két megszámlálhatatlan végtelen Boole-algebra atom nélkül izomorf.
Azt is lehetővé teszi, hogy bemutassuk, hogy a logikai elmélettel egyenértékű két atom (en) megszámlálható modell izomorf.
Ez azt mutatja, hogy a modell Erdős-Rényi (in) a véletlen gráfok , alkalmazva a megszámlálható végtelen gráfok, mindig termel egy grafikonon, a grafikonon Rado .
Ez azt mutatja, hogy a két M-teljes (in) rekurzívan felsorolható a rekurzív izomorfak.

Alkalmazás sűrű rendezett halmazokra

Két sűrű és megszámlálható sorrendet veszünk figyelembe , szélső elemek nélkül, vagyis maximum vagy minimum elemek nélkül. Mi fix felsorolás elemeinek és : ${\ displaystyle (A, \ leq _ {A})}$ ${\ displaystyle (B, \ leq _ {B})}$ $NÁL NÉL$ $B$

{\ displaystyle A = \ {a_ {1}, a_ {2}, a_ {3}, \ ldots \}}

és

{\ displaystyle B = \ {b_ {1}, b_ {2}, b_ {3}, \ ldots \}}

és építünk egy szigorúan növekvő bijekciót között és fokozatos tömörítő elemeket a és a . Kezdetben a (z) elemhez nincs társítva a . $NÁL NÉL$ $B$ $NÁL NÉL$ $B$ $B$ $NÁL NÉL$ $NÁL NÉL$ $B$

(1) Legyen a legkisebb index, amely nem kapcsolódik a (z) elemhez , és legyen olyan index, amely nem kapcsolódik az elemhez, és amely társítható ahhoz , hogy a megfelelés szigorúan növekedjen. Tehát társulunk és . $én$ $van}$ $B$ $j$ $b_j$ $NÁL NÉL$ $van}$ $b_j$ $van}$ $b_j$

(2) Legyen a legkisebb index, amely nincs társítva a (z) eleméhez , és legyen olyan index, amely nincs társítva az elemhez, és amely társítható ahhoz , hogy a megfelelés szigorúan növekedjen. Tehát társulunk és . $j$ $b_j$ $NÁL NÉL$ $én$ $van}$ $B$ $b_j$ $van}$ $b_j$ $van}$

(3) Az (1) bekezdésben kezdjük újra.

Ellenőrizni kell, hogy az (1) és (2) lépésben a feltételek tiszteletben tartása mellett lehet-e választani. Tekintsünk egy (1) lépésben: Ha vannak elemek , és a , megfelelő elemek és a rendre, ilyen és , úgy döntünk között és , ami azért lehetséges, a sűrűség tulajdonság. Ellenkező esetben bármelyik elemet elég nagynak vagy elég kicsinek választjuk , ami lehetséges, mert nincs sem maximális, sem minimális eleme. A (2) lépésben meghozott döntések kettősek az előzőekkel. Végül az építkezés megszámlálható számú lépés után ér véget, mert a halmazok és megszámlálhatók. $a_ {p}$ ${\ displaystyle a_ {q}}$ $NÁL NÉL$ ${\ displaystyle b_ {p}}$ ${\ displaystyle b_ {q}}$ $B$ ${\ displaystyle a_ {p} <a_ {i} <a_ {q}}$ ${\ displaystyle b_ {p} <b_ {q}}$ $b_j$ ${\ displaystyle b_ {p}}$ $b_q$ $B$ $B$ $NÁL NÉL$ $B$

Történelmi megjegyzés

Ami a módszer eredetét illeti, Hodges 1993 :

„Az oda-vissza módszereket gyakran Cantornak , Bertrand Russellnek és CH Langford (en) -nek tulajdonítják [...] , de nincs bizonyíték ezen attribútumok egyikének alátámasztására. "

A " Cantor tételének rendelmélete " elnevezésű, megszámlálható sűrű rendezett halmazokról szóló tétel Cantornak (1895) köszönhető, ezt a viszonzási módszert, amellyel most bemutatták, Huntington 1904 és Hausdorff 1914 dolgozta ki . Ezt követően Roland Fraïssé alkalmazta a modellelméletben .

Megjegyzések és hivatkozások

"Az oda-vissza módszereket gyakran Cantornak , Bertrand Russell-nek és CH Langford-nak tulajdonítják (in) [...], de nincs bizonyíték e díjak egyikének alátámasztására. "

(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „ Back-oda módszer ” ( lásd a szerzők listáját ) .

Edward Vermilye Huntington , A folytonosság és más típusú sorozatok, bevezetővel Cantor transzfinit számaira , a Harvard University Press ,1904( online olvasás )
Felix Hausdorff , Grundzüge der Mengenlehre , Lipcse, Veit & Comp.,1914( online olvasás )
Wilfrid Hodges , modellelmélet , Cambridge University Press ,1993, 772 p. ( ISBN 978-0-521-30442-9 , online olvasás )
David Marker , Modellelmélet: Bevezetés , Berlin, New York, Springer-Verlag , koll. " Diplomás szövegek a matematikából ",2002, 345 p. ( ISBN 978-0-387-98760-6 , online olvasás )

Kapcsolódó cikk

Ehrenfeucht-Fraïssé játék