secondo ordine, teoria del

secondo ordine, teoria del

secondo ordine, teoria del in logica, locuzione utilizzata per contraddistinguere una particolare categoria di teorie matematiche formalizzate. Formalizzare una teoria significa esprimere i suoi assiomi nonché le sue regole di → inferenza in un linguaggio formale (si consideri per esempio l’aritmetica formalizzata dagli assiomi di → Peano). Solitamente le teorie matematiche sono formalizzate in un linguaggio dei → predicati, facendo quindi uso di:

• variabili e costanti, che indicano gli elementi di base della teoria;

• lettere predicative e lettere funzionali per indicare le proprietà e le relazioni fra variabili;

• quantificatori per specificare a “quanti” elementi si riferisce una data proprietà. Si usano due quantificatori: il quantificatore universale, indicato con il simbolo ∀ (si legge «per ogni»), e il quantificatore esistenziale indicato con il simbolo ∃ (si legge «esiste»).

Una teoria formalizzata si dice teoria del secondo ordine se i quantificatori ∀ e ∃ possono essere applicati non soltanto alle singole variabili, come nelle teorie del → primo ordine, ma anche a insiemi di variabili. Si consideri per esempio la frase «se x è un qualsiasi numero naturale e M un qualsiasi insieme di numeri naturali, allora si ha una delle seguenti possibilità: o x appartiene a M o x non appartiene a M». Indicando: con M(x) la forma «x appartiene a M», con il simbolo ￢ la negazione di una forma predicativa (￢M(x) indica «x non appartiene a M») e con il simbolo ⋁ la disgiunzione fra due forme, la frase precedente può essere tradotta nella forma ∀x∀M(M(x) ⋁ ￢M(x)). Questa formula ben formata è espressa in un linguaggio predicativo del secondo ordine in quanto il quantificatore ∀ è riferito sia alla variabile x sia all’insieme di variabili M.

La possibilità di quantificare su insiemi di variabili dà alle teorie del secondo ordine un potere espressivo maggiore rispetto alle teorie del primo ordine. Si consideri per esempio il cosiddetto principio di buon → ordinamento, valido per i numeri naturali, secondo il quale «ogni sottoinsieme non vuoto dell’insieme dei numeri naturali ammette un minimo, cioè un elemento minore di tutti gli altri». Per la sua formalizzazione non basta una teoria del primo ordine perché il quantificatore universale (per ogni) viene applicato non alle singole variabili, cioè ai numeri naturali, ma agli insiemi di numeri naturali.

In una interpretazione di un linguaggio logico le variabili assumono valori in un insieme di riferimento detto dominio di interpretazione. Ogni proprietà che si riferisce a una variabile del linguaggio in questione corrisponde a un sottoinsieme del dominio di interpretazione. Se per esempio si considera un linguaggio logico predicativo per formalizzare l’aritmetica, il quale abbia come dominio di interpretazione l’insieme dei numeri naturali, allora ogni proprietà che è possibile attribuire a un numero naturale corrisponde a un sottoinsieme dell’insieme dei numeri naturali. Per esempio, la proprietà «n è un intero positivo multiplo di 5» corrisponde all’insieme {5, 10, 15, 20, ...}. Per questo motivo in un linguaggio del secondo ordine, in cui è ammessa la quantificazione sugli insiemi di variabili, è possibile quantificare anche sulle proprietà, cioè sui predicati, che si riferiscono alle variabili stesse. Ciò risulta utile per esprimere formalmente il principio di → induzione matematica che è parte integrante degli assiomi di Peano. Il principio di induzione matematica afferma che «se P è una proprietà concernente i numeri naturali soddisfatta da zero e tale che, se soddisfatta da un dato numero naturale, lo è anche dal suo successore, allora P è soddisfatta da ogni numero naturale»; per formalizzare in maniera completa questo principio occorre utilizzare un linguaggio del secondo ordine che permetta di quantificare universalmente sull’insieme di tutte le proprietà P esprimibili sui numeri naturali.

È possibile considerare anche teorie di ordine superiore al secondo. A tal proposito si consideri che in una teoria del primo ordine si può quantificare solo sulle variabili x, y, z... e in una teoria del secondo ordine è possibile quantificare anche su simboli predicativi che hanno come argomenti le variabili P(x), Q(x), R(x, y)... Per passare a una teoria di ordine superiore al secondo si considerano dei simboli di ordine superiore che hanno come argomenti sia le variabili sia i simboli predicativi: α(P(x), y), β(x, Q(y)) e si ammette la quantificazione anche su tali simboli (∀α... ∃α...).