Set definibile - Definable set

In logica matematica , un insieme definibile è un n ario relazione sul dominio di una struttura di cui elementi sono precisamente quegli elementi che soddisfano alcune formula nel linguaggio del primo ordine di tale struttura. Un insieme può essere definito con o senza parametri , che sono elementi del dominio a cui si può fare riferimento nella formula che definisce la relazione.

Definizione

Sia un linguaggio del primo ordine, una struttura con dominio , un sottoinsieme fisso di e un numero naturale . Poi: ${\ displaystyle {\ mathcal {L}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {L}}}$${\ displaystyle M}$${\ displaystyle X}$${\ displaystyle M}$${\ displaystyle m}$

• Un insieme è definibile in con parametri da se e solo se esiste una formula ed elementi tali che per tutti , ${\ displaystyle A \ subseteq M ^ {m}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle X}$${\ displaystyle \ varphi [x_ {1}, \ ldots, x_ {m}, y_ {1}, \ ldots, y_ {n}]}$${\ displaystyle b_ {1}, \ ldots, b_ {n} \ in X}$${\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}$

${\ displaystyle (a_ {1}, \ ldots, a_ {m}) \ in A}$ se e solo se ${\ displaystyle {\ mathcal {M}} \ models \ varphi [a_ {1}, \ ldots, a_ {m}, b_ {1}, \ ldots, b_ {n}]}$

La notazione tra parentesi qui indica la valutazione semantica delle variabili libere nella formula.

• Un set è definibile in senza parametri se è definibile in con parametri dal set vuoto (cioè senza parametri nella formula di definizione). ${\ displaystyle A}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$
• Una funzione è definibile in (con parametri) se il suo grafico è definibile (con quei parametri) in . ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$
• Un elemento è definibile in (con parametri) se l' insieme singleton è definibile in (con quei parametri). ${\ displaystyle a}$${\ displaystyle {\ mathcal {M}}}$ ${\ displaystyle \ {a \}}$${\ displaystyle {\ mathcal {M}}}$

Esempi

I numeri naturali con solo la relazione d'ordine

Sia la struttura costituita dai numeri naturali con il solito ordinamento. Quindi ogni numero naturale è definibile senza parametri. Il numero è definito dalla formula che afferma che non esistono elementi inferiori a x : e un numero naturale è definito dalla formula che afferma che esistono esattamente elementi inferiori a x : ${\ displaystyle {\ mathcal {N}} = (\ mathbb {N}, <)}$${\ displaystyle {\ mathcal {N}}}$${\ displaystyle 0}$${\ displaystyle \ varphi (x)}$${\ displaystyle \ varphi = \ neg \ esiste y (y <x),}$${\ displaystyle n> 0}$${\ displaystyle \ varphi (x)}$${\ displaystyle n}$

${\ displaystyle \ varphi = \ exist x_ {0} \ cdots \ exist x_ {n-1} (x_ {0} <x_ {1} \ land \ cdots \ land x_ {n-1} <x \ land \ forall y (y <x \ rightarrow (y \ equiv x_ {0} \ lor \ cdots \ lor y \ equiv x_ {n-1})))}$

Al contrario, non si può definire alcun intero specifico senza parametri nella struttura costituita dagli interi con l'ordinamento usuale (vedere la sezione sugli automorfismi di seguito). ${\ displaystyle {\ mathcal {Z}} = (\ mathbb {Z}, <)}$

I numeri naturali con le loro operazioni aritmetiche

Sia la struttura del primo ordine costituita dai numeri naturali e dalle loro usuali operazioni aritmetiche e dalla relazione d'ordine. Gli insiemi definibili in questa struttura sono noti come insiemi aritmetici e sono classificati nella gerarchia aritmetica . Se la struttura è considerata nella logica del secondo ordine anziché nella logica del primo ordine, gli insiemi definibili di numeri naturali nella struttura risultante sono classificati nella gerarchia analitica . Queste gerarchie rivelano molte relazioni tra definibilità in questa struttura e teoria della computabilità , e sono anche di interesse nella teoria descrittiva degli insiemi . ${\ displaystyle {\ mathcal {N}} = (\ mathbb {N}, +, \ cdot, <)}$

Il campo dei numeri reali

Sia la struttura costituita dal campo dei numeri reali . Sebbene la solita relazione di ordinamento non sia direttamente inclusa nella struttura, esiste una formula che definisce l'insieme dei reali non negativi, poiché questi sono gli unici reali che possiedono radici quadrate: ${\ displaystyle {\ mathcal {R}} = (\ mathbb {R}, 0,1, +, \ cdot)}$

${\ Displaystyle \ varphi = \ exist y (y \ cdot y \ equiv x).}$

Quindi any è non negativo se e solo se . In combinazione con una formula che definisce l'inverso additivo di un numero reale in , si può usare per definire il solito ordinamento in : for , set if e only if non è negativo. La struttura allargata s è chiamata estensione di definizione della struttura originale. Ha la stessa potenza espressiva della struttura originaria, nel senso che un insieme è definibile sulla struttura ingrandita da un insieme di parametri se e solo se è definibile sulla struttura originaria da quello stesso insieme di parametri. ${\ displaystyle a \ in \ mathbb {R}}$${\ displaystyle {\ mathcal {R}} \ models \ varphi [a]}$${\ displaystyle {\ mathcal {R}}}$${\ displaystyle \ varphi}$${\ displaystyle {\ mathcal {R}}}$${\ displaystyle a, b \ in \ mathbb {R}}$${\ displaystyle a \ leq b}$${\ displaystyle ba}$${\ displaystyle {\ mathcal {R}} ^ {\ leq} = (\ mathbb {R}, 0,1, +, \ cdot, \ leq)}$

La teoria di ha quantifier eliminazione . Pertanto gli insiemi definibili sono combinazioni booleane di soluzioni di uguaglianze e disuguaglianze polinomiali; questi sono chiamati insiemi semi-algebrici . Generalizzare questa proprietà della linea reale porta allo studio della o-minimalità . ${\ displaystyle {\ mathcal {R}} ^ {\ leq}}$

Invarianza sotto automorfismi

Un risultato importante sui set definibili è che sono conservati sotto automorfismi .

Lasciate essere uno struttura che specifica i domini , e definibile in con i parametri da . Sia un automorfismo di cui è l'identità . Quindi per tutti , ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {L}}}$${\ displaystyle M}$${\ displaystyle X \ subseteq M}$${\ displaystyle A \ subseteq M ^ {m}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle X}$${\ displaystyle \ pi: M \ to M}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle X}$${\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}$

${\ displaystyle (a_ {1}, \ ldots, a_ {m}) \ in A}$ se e solo se ${\ displaystyle (\ pi (a_ {1}), \ ldots, \ pi (a_ {m})) \ in A}$

Questo risultato a volte può essere utilizzato per classificare i sottoinsiemi definibili di una data struttura. Ad esempio, nel caso di cui sopra, qualsiasi traduzione di è un automorfismo che preserva l'insieme vuoto di parametri, e quindi è impossibile definire un intero particolare in questa struttura senza parametri in . Infatti, poiché due interi qualsiasi sono trasportati l'uno all'altro da una traduzione e dal suo inverso, gli unici insiemi di interi definibili in senza parametri sono l'insieme vuoto e se stesso. Al contrario, ci sono infinitamente molti insiemi definibili di coppie (o addirittura n -tuple per ogni fisso n > 1) di elementi di , poiché ogni automorfismo (traslazione) preserva la "distanza" tra due elementi. ${\ displaystyle {\ mathcal {Z}} = (\ mathbb {Z}, <)}$${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle \ mathbb {Z}}$${\ displaystyle {\ mathcal {Z}}}$

Risultati aggiuntivi

Il test di Tarski – Vaught viene utilizzato per caratterizzare le sottostrutture elementari di una data struttura.

Riferimenti

• Hinman, Peter. Fondamenti di logica matematica , AK Peters, 2005.
• Marker, David. Teoria dei modelli: un'introduzione , Springer, 2002.
• Rudin, Walter. Principi di analisi matematica , 3 °. ed. McGraw-Hill, 1976.
• Slaman, Theodore A. e W. Hugh Woodin. Logica matematica: il corso universitario di Berkeley . Primavera 2006.