Teoria del primo ordine

Nella logica matematica, una teoria del primo ordine (o calcolo dei predicati) è un particolare sistema formale, cioè una teoria formale, in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico. La teoria del prim'ordine estende di fatto la logica proposizionale con l'introduzione di quantificatori esistenziali e universali, predicati, funzioni, variabili e costanti, che apportano maggiore potenza espressiva al calcolo dei predicati^[1].

Come per la logica proposizionale, la teoria del primo ordine può essere scissa in due parti separate:

la sintassi, che definisce il vocabolario simbolico di base e le regole per la costruzione di enunciati complessi,
la semantica, che interpreta questi enunciati come espressione delle relazioni tra gli elementi di un dominio, aggregati mediante un assegnamento.

Un predicato è un'espressione linguistica che può essere collegata a uno o più elementi del dominio per formare una frase. Ad esempio, nella frase "Marte è un pianeta", l'espressione "è un pianeta" è un predicato che è legato al nome (un simbolo costante) "Marte" per formare una frase. Nella frase "Giove è più grande di Marte", l'espressione "è più grande di" è un predicato che collega i due nomi, "Giove" e "Marte", per formare una frase.

In logica matematica, quando un predicato è legato a un'espressione, si dice che esprime una proprietà (come la proprietà di essere un pianeta nell'esempio precedente), e quando è legato a due o più espressioni, si dice che esprime una relazione (come la relazione per un pianeta di essere più grande di un altro). Così è ragionare su affermazioni come "Ogni x è bello" e "Esiste un x tale che per ogni y, x è amico di y", che simbolicamente è espresso dalla formula: $\exists x|\forall y~\mathrm {amico} (x,y)$ .

Va notato che la teoria del primo ordine non contiene in sé nessuna relazione specifica (come una relazione d'ordine, inclusione o uguaglianza).

Definizione

Gli elementi che definiscono una teoria del primo ordine sono:

un alfabeto, ovvero un insieme finito di simboli,
un linguaggio del primo ordine, costituito da un insieme di formule ben formate che rappresentano enunciati di senso compiuto,
un insieme di assiomi logici, cioè un insieme di formule che esprimono le relazioni logiche relative ai connettivi logici e ai quantificatori,
un insieme di assiomi propri, che stabiliscono alcune relazioni fondamentali tra gli oggetti della teoria non deducibili dagli assiomi logici (come l'assioma "per due punti passa una e una sola retta"),
un insieme di regole di inferenza, che stabiliscono quando una formula è una conseguenza logica di altre formule.

Esempi di teorie del primo ordine sono l'aritmetica di Peano, l'aritmetica di Robinson, la teoria degli insiemi di Zermelo-Fraenkel.

Dimostrazioni formali

Una dimostrazione di una formula $\varphi$ in una teoria del primo ordine T è una sequenza ordinata di formule

(\varphi _{1},\varphi _{2},...,\varphi _{n})

tale che

$\varphi _{n}=\varphi$
ogni formula $\varphi _{i}$ o è un assioma di T o è deducibile da una o più formule ad essa precedenti mediante una regola di inferenza.

Una formula che ha una dimostrazione formale in T si dice dimostrabile o derivabile. Se la formula $\varphi$ è dimostrabile in T si usa la notazione

\vdash _{T}\varphi

o semplicemente

\vdash \varphi

se la teoria di riferimento è evidente dal contesto.

Proprietà sintattiche

Una teoria del primo ordine T si dice:

sintatticamente completa se per ogni formula $\varphi$ si ha

\vdash _{T}\varphi

oppure

\vdash _{T}\neg \varphi

sintatticamente coerente se non esiste nessuna formula $\varphi$ per cui si ha

\vdash _{T}\varphi

e contemporaneamente

\vdash _{T}\neg \varphi

Note

^ Asperti e Ciabattoni, pp. 99-100.

Bibliografia

Andrea Asperti e Agata Ciabattoni, 4. Logica dei predicati, in Logica a informatica, McGraw-Hill, 1997.

Voci correlate

Collegamenti esterni

primo ordine, teoria del, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
(EN) lower predicate calculus, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Predicate calculus, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
(EN) Denis Howe, first-order logic, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Asperti e Ciabattoni, pp. 99-100.

[1]