Teoria del primo ordine

Niente fonti!
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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: ∃ x | ∀ y   a m i c o ( x , y ) {\displaystyle \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 φ {\displaystyle \varphi } in una teoria del primo ordine T è una sequenza ordinata di formule

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

tale che

  • φ n = φ {\displaystyle \varphi _{n}=\varphi }
  • ogni formula φ i {\displaystyle \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 φ {\displaystyle \varphi } è dimostrabile in T si usa la notazione

⊢ T φ {\displaystyle \vdash _{T}\varphi }

o semplicemente

⊢ φ {\displaystyle \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 φ {\displaystyle \varphi } si ha
⊢ T φ {\displaystyle \vdash _{T}\varphi } oppure ⊢ T ¬ φ {\displaystyle \vdash _{T}\neg \varphi }
  • sintatticamente coerente se non esiste nessuna formula φ {\displaystyle \varphi } per cui si ha
⊢ T φ {\displaystyle \vdash _{T}\varphi } e contemporaneamente ⊢ T ¬ φ {\displaystyle \vdash _{T}\neg \varphi }

Note

  1. ^ 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

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