Metodo avanti e indietro

Nella logica matematica , e in particolare nella teoria degli insiemi e nella teoria dei modelli , il metodo avanti e indietro è un metodo per dimostrare l' isomorfismo tra strutture numerabili che soddisfano determinate condizioni aggiuntive.

Utilizza

Il metodo avanti e indietro si applica a infiniti insiemi numerabili aventi una certa struttura (nel senso logico del termine). Permette di costruire una biiezione tra questi insiemi, una biiezione che ha proprietà di preservare la struttura, quindi che è un isomorfismo . Ecco alcuni esempi:

Il metodo può essere utilizzato per dimostrare che due denso ordinato set (cioè totalmente ordinata e tale che tra due elementi distinti, c'è sempre un terzo) numerabile e senza elementi estremali sono isomorfi (un isomorfismo fra totalmente ordinata è strettamente crescente biiezione ). Questo risultato implica per esempio che ci sono biiezioni strettamente crescenti tra l'insieme dei numeri razionali e l'insieme dei numeri algebrici .
Ci permette di dimostrare che due infinite algebre booleane numerabili senza atomi sono isomorfe.
Consente inoltre di dimostrare che due modelli atomici (en) numerabili equivalenti a una teoria logica sono isomorfi.
Dimostra che il modello di Erdős-Rényi (in) di grafi casuali , applicato a grafi infiniti numerabili, produce sempre un unico grafo, il grafo di Rado .
Dimostra che due insiemi m-complete (in) enumerabili ricorsivamente sono ricorsivamente isomorfi.

Applicazione a insiemi ordinati densi

Consideriamo due insiemi ordinati densi e numerabili, e senza elementi estremi, cioè senza elementi massimi o minimi. Fissiamo un'enumerazione degli elementi di e : ${\ displaystyle (A, \ leq _ {A})}$ ${\ displaystyle (B, \ leq _ {B})}$ $A$ $B$

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

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

e costruiamo una biiezione strettamente crescente tra e associando progressivamente elementi da a e da a . Inizialmente, nessun elemento di è associato a un elemento di . $A$ $B$ $A$ $B$ $B$ $A$ $A$ $B$

(1) Sia l'indice più piccolo tale che non sia associato ad un elemento di , e sia un indice tale che non sia associato ad un elemento di e tale che possa essere associato in modo che la corrispondenza sia strettamente crescente. Quindi associamo e . $io$ $avere}$ $B$ $j$ $b_j$ $A$ $avere}$ $b_j$ $avere}$ $b_j$

(2) Sia l'indice più piccolo tale che non sia associato ad un elemento di , e sia un indice tale che non sia associato ad un elemento di e tale che possa essere associato in modo che la corrispondenza sia strettamente crescente. Quindi associamo e . $j$ $b_j$ $A$ $io$ $avere}$ $B$ $b_j$ $avere}$ $b_j$ $avere}$

(3) Ricominciamo da (1).

È necessario verificare che le scelte ai punti (1) e (2) possano essere effettuate nel rispetto delle condizioni. Si consideri una fase (1): Se vi sono elementi e di corrispondenti agli elementi e di rispettivamente ad e , abbiamo scelto tra e , che è possibile dalla struttura densità. Altrimenti, scegliamo qualsiasi elemento abbastanza grande o abbastanza piccolo, il che è possibile perché non ha né l'elemento massimo né l'elemento minimo. Le scelte effettuate al punto (2) sono doppie rispetto alle precedenti. Infine, la costruzione termina dopo un numero di passaggi numerabile perché gli insiemi e sono numerabili. $a_ {p}$ ${\ displaystyle a_ {q}}$ $A$ ${\ 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$ $A$ $B$

Nota storica

Per quanto riguarda l'origine del metodo, Hodges 1993 :

“I metodi avanti e indietro sono spesso attribuiti a Cantor , Bertrand Russell e CH Langford (en) [...] , ma non ci sono prove a sostegno di nessuna di queste attribuzioni. "

Il teorema sugli insiemi ordinati densi numerabili chiamato " Teorema di Cantor nella teoria dell'ordine " è dovuto a Cantor (1895), il metodo alternativo con cui è ora dimostrato fu sviluppato da Huntington 1904 e Hausdorff 1914 . Successivamente, è stato applicato da Roland Fraïssé nella teoria dei modelli .

Note e riferimenti

"I metodi di avanti e indietro sono spesso attribuiti a Cantor , Bertrand Russell e CH Langford (in) [...] ma non ci sono prove a sostegno di uno di questi premi. "

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato “ Metodo avanti e indietro ” ( vedere l'elenco degli autori ) .

Edward Vermilye Huntington , The continuum and other types of serial order, con un'introduzione ai numeri transfiniti di Cantor , Harvard University Press ,1904( leggi online )
Felix Hausdorff , Grundzüge der Mengenlehre , Lipsia, Veit & Comp.,1914( leggi online )
Wilfrid Hodges , teoria dei modelli , Cambridge University Press ,1993, 772 p. ( ISBN 978-0-521-30442-9 , leggi in linea )
David Marker , Model Theory: An Introduction , Berlino, New York, Springer-Verlag , coll. " Testi per laureati in matematica ",2002, 345 p. ( ISBN 978-0-387-98760-6 , leggi online )

Articolo correlato

Partita Ehrenfeucht-Fraïssé