definibilita

definibilità

Nella logica matematica, concetto utilizzato in due sensi: uno riferito alle costanti extralogiche di una teoria in un linguaggio L, l’altro alle relazioni o funzioni su una struttura per L caratterizzabili da formule del linguaggio. Esemplifichiamo nel caso in cui il linguaggio sia elementare. Data la teoria T nel linguaggio formale L in cui occorrono le costanti predicative Q₁,…,Q_n e la costante P, essa è definibile in T da Q₁,…,Q_n se esiste una formula D, che contiene solo queste costanti e non la costante P per cui in T si dimostra:

T⊦∀x₁,...,x_k (D(x₁,...,x_k) ↔ P(x₁,...,x_k)).

In questo caso diremo che la formula in questione è una definizione esplicita di P a partire da Q₁,…,Q_n, dove P è il definiendum e D il definiens. Discorso analogo si può fare per costanti funzionali o individuali. Diremo invece che P è definibile implicitamente in T da Q₁,…,Q_n se – indicando con T′ la teoria che si ottiene da T sostituendo uniformenente P in ogni assioma di T con una nuova costante P′ della stessa arietà – abbiamo

T∪T′⊦∀x₁,...,x_k (P′(x₁,...,x_k) ↔ P(x₁,...,x_k))

che esprime il fatto che se due modelli con lo stesso dominio interpretano allo stesso modo le Q_i interpreteranno allo stesso modo anche P. Il risultato fondamentale al riguardo è il teorema di Beth (1950) che fornisce una versione precisa di un criterio formulato da Alessandro Padoa nel 1900 per cui la costante P non è definibile da Q₁,…,Q_n in T se esistono due modelli di T con stesso dominio e stessa interpretazione delle Q_i che divergono su P. Il risultato vale non solo per le teorie elementari ma per teorie formulate in linguaggi più ricchi, per es., al secondo ordine dove era stato dimostrato precedentemente da Alfred Tarski nel 1935. Molti risultati interessanti riguardano il problema di sapere per quali linguaggi e sotto che forma il risultato può valere e quali varianti sono possibili. Passando al versante semantico – che rappresenta l’altra dimensione della definibilità – data una struttura M per il linguaggio L diciamo che la relazione R⊂Dⁿ_M è definibile con parametri in X⊂D_M se esiste una formula A(x₁,...,x_n, y₁,...,y_k) di L e b₁,…,b_k in X per cui

X={〈a₁,...,a_n>:M∣=A[a₁,...,a_n b₁,...,b_k]}.

Parleremo di definibilità tout court se X=∅. Discorso analogo si può fare per funzioni e per individui (in questo caso a∈D_M è definibile se lo è {a}). Ricerche fondamentali della moderna teoria dei modelli studiano e classificano gli insiemi definibili o definibili con particolari modalità in strutture matematicamente significative. Per capire la portata della cosa, basti pensare che varietà affini o proiettive, insiemi semialgebrici e costruibili sono tutti insiemi definibili in opportuni linguaggi elementari, come anche gli insiemi ricorsivi in ℕ. La teoria della definibilità offre metodi generali per lo studio di questi insiemi.

→ Modelli, teoria dei