[dispensa] Logica formale del prim'ordine

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

[dispensa] Logica formale del prim'ordine

Messaggioda maurer il ven 11 feb 2011, 13:44

Nota Iniziale. Ho visto che la sezione di Logica del forum non è proprio sviluppatissima. Mi propongo allora di aggiungere qualche post in teoria incentrata sulla Logica del Primo Ordine, al limite delle mie (scarse) conoscenze in merito. Piano dell'opera: linguaggi del prim'ordine, termini, formule, equivalenza elementare, esistenza di estensioni elementari, teorema di compattezza. Svilupperei poi un po' in dettaglio l'esempio fornito dall'Analisi nonstandard. Qualsiasi correzione, suggerimento o partecipazione sono i benvenuti!

Convenzioni. Se A, B sono insiemi denoteremo con A \times B il loro prodotto cartesiano. Abbrevieremo con A^n il prodotto cartesiano di A per se stesso n volte, per n \in \mathbb{N}_0 := \{1, 2, \ldots \}. Convenzionalmente poniamo poi A^0 := \{\emptyset\}.

Definizione (linguaggio del prim'ordine) Un linguaggio del prim'ordine è una coppia (L,\text{ar}) dove L è un insieme partizionato in L = L_{\text{fun}} \cup L_{\text{rel}} e \text{ar} è una funzione \text{ar} \colon L \to \mathbb{N}, detta arietà. Gli elementi di L_{\text{fun}} sono detti simboli di funzione, gli elementi di L_{\text{rel}} sono detti simboli di relazione.

Nota 1. I due insiemi L_{\text{fun}} e L_{\text{rel}} potrebbero essere vuoti (v. gli esempi qui sotto).
Nota 2. Se f \in L_{\text{fun}} e \text{ar}(f) = 1, f si dirà simbolo di funzione unaria. In generale se \text{ar}(f) = n, f si dirà simbolo di funzione n-aria.

Gli elementi di L possono essere, a priori, qualsiasi cosa. Nel seguito, tuttavia, utilizzeremo simboli che suggeriscono un'interpretazione. Ad esempio utilizzeremo come simboli per funzioni le lettere f,g,h,\ldots e come simboli per relazioni r, \sigma, \tau, \ldots.

Definizione (costante) Sia (L,\text{ar}) un linguaggio del prim'ordine. Chiamiamo costanti i simboli di funzione di arietà 0, ossia i simboli f \in L_{\text{fun}} tali che \text{ar}(L) = 0.

Definizione (struttura) Sia (L,\text{ar}) un linguaggio del prim'ordine. Diciamo che la coppia (M, (\cdot)^M) è una struttura di segnatura L se
  • M è un insieme
  • (\cdot)^M è una funzione che associa ad ogni simbolo di funzione f \in L_{\text{fun}} di arietà n una funzione f^M \cdot M^n \to M e ad ogni simbolo di relazione r \in L_{\text{rel}} di arietà n una relazione r^M \subseteq M^n.
Se f è un simbolo di funzione e r è un simbolo di relazione, f^M e r^M saranno dette interpretazioni in M di f e r.

Nota 3. Se (L,\text{ar}) è un linguaggio del prim'ordine e M è una struttura di segnatura L, se f è un simbolo di funzione 0-aria (ossia una costante) allora f^M è una funzione di dominio M^0 = \{\emptyset\}. Dare un'interpretazione di f equivale quindi a scegliere un elemento di M.

Esempi.
  • Denotiamo con L_{gm} il linguaggio dei gruppi moltiplicativi. Esplicitamente poniamo L_{gm} = \{1, (\cdot)^{-1}, \cdot\}, dove 1 è un simbolo funzione di arietà 0 (quindi una costante); (\cdot)^{-1} è un simbolo di funzione di arietà 1; \cdot è un simbolo di funzione binaria. Un qualsiasi gruppo moltiplicativo G è una struttura di segnatura (L_{gm},\text{ar}), che interpreta gli elementi nel linguaggio nel modo naturale: il simbolo 1 viene interpretato nell'elemento neutro del gruppo, il simbolo (\cdot)^{-1} è interpretato nell'operazione che associa ad ogni elemento il suo elemento inverso; il simbolo \cdot è interpretato nell'usuale operazione del gruppo. Si osservi che in questo caso L_{\text{rel}} = \emptyset.
  • Denotiamo con L_{\text{grf}} il linguaggio dei grafi. Esplicitamente L_{\text{grf}} = \{r\}, dove r è un simbolo di relazione binaria. Una struttura di segnatura L_{\text{grf}} è un qualsiasi grafo e l'interpretazione di r è data dall'interpretazione naturale: r^M è la relazione di adiacenza. In questo caso L_{\text{fun}} = \emptyset.
  • Denotiamo con L_v il linguaggio degli spazi vettoriali sul campo K. Esso è dato dall'unione di \{0, +, -\} \cup K, dove 0 è un simbolo di costante, + è un simbolo di una funzione binaria, - è un simbolo di funzione unaria e ogni elemento di K è visto come simbolo di una funzione unaria. Una struttura di segnatura L_v è un qualsiasi spazio vettoriale V sul campo K. L'interpretazione è quella naturale: il simbolo 0 è interpretato nel vettore nullo, il simbolo + è interpretato nell'usuale somma di vettori, il simbolo - è interpretato come la funzione che ad ogni vettore associa il vettore opposto. Infine, se \lambda \in K si pone
      \begin{matrix} \lambda^V \colon & V & \to & V \\ & \mathbf{v} & \mapsto & \lambda \mathbf{v} \end{matrix}
    Si osservi che in questo caso il linguaggio è formato da infiniti simboli (è addirittura più che numerabile se si prende, ad esempio, K = \mathbb{R}.

Definizione (tupla) Sia \lambda un ordinale e sia A \ne \emptyset un insieme. Diciamo tupla di elementi di A una qualsiasi funzione a \colon \lambda \to A. Denoteremo l'elemento a(i) con la giustapposizione ai o con la notazione a_i. Se la tupla è suriettiva, diremo che è una enumerazione di A. Se a \colon \lambda \to A è una tupla, diremo lunghezza della tupla a il numero ordinale \lambda. Scriveremo \text{lh}(a) = \lambda. Se l'ordinale è finito allora scriveremo anche a = \langle a_1 a_2 \ldots a_n \rangle. Per indicare che a è una tupla di elementi di A scriveremo, con abuso di notazione, a \subseteq A (l'abuso è dovuto al fatto che in generale a \subseteq A^{\text{lh}(a)}}; omettiamo quindi il riferimento alla lunghezza della tupla considerata).

Definizione (concatenazione) Sia A \ne \emptyset un insieme e siano a, b \subseteq A due tuple finite. Posto n := \text{lh}(a), m := \text{lh}(b), definiamo la concatenazione di a con b come la tupla c \colon \{0, 1, \ldots, m +n -1\} \to A definita da
c_i = \begin{cases} a_i & \text{se } 0 \le i \le n - 1 \\ b_{i - n} & \text{se } n \le i \le n + m -1 \end{cases}
Denoteremo la concatenazione di a con b con la scrittura ab.

Definizione (Insieme delle variabili) Sia (L,\text{ar}) un linguaggio del prim'ordine e sia A un insieme (anche vuoto), che chiameremo insieme dei parametri. Diciamo che un insieme V è un insieme di variabili se:
  • V è infinito;
  • V \cap L = \emptyset, V \cap A = \emptyset.
Denoteremo gli elementi di V con le lettere x,y,z,\ldots e li chiameremo variabili (libere).

Nota 4. Naturalmente, assegnato qualsiasi linguaggio del prim'ordine (L,\text{ar}) ed un qualsiasi insieme dei parametri è sempre possibile trovare un insieme di variabili. D'ora in poi, pertanto, eviteremo di dire "scelto un insieme delle variabili..."; assegnato un linguaggio del prim'ordine assumeremo implicitamente che venga anche assegnato un opportuno insieme delle variabili.

Definizione (termine) Sia (L,\text{ar}) un linguaggio del prim'ordine, sia A un insieme qualsiasi. Un termine t a parametri in A è una qualsiasi successione finita di simboli del linguaggio, variabili ed elementi di A soddisfacente al seguente procedimento di costruzione induttiva:
    b1) ogni elemento di A (cioè, ogni parametro) è un termine;
    b2) ogni variabile è un termine;
    i) se t_1, t_2, \ldots, t_n sono termini e se f \in L è un simbolo di funzione di arietà n allora ft_1 t_2 \ldots t_n è un termine.
Diremo che un termine è puro se è stato costruito senza utilizzare il passo b1); diremo che un termine è chiuso se è stato costruito senza utilizzare il passo b2); diremo che un termine è atomico se è stato costruito senza utilizzare il passo i). Se x è una tupla di variabili e t è un termine, scriveremo t(x) per indicare che nel termine t compaiono (occorrono) al più le variabili presenti in x.

Definizione (sostituzione). Sia (L,\text{ar}) un linguaggio del prim'ordine e sia A un insieme di parametri. Sia t(x) un termine a parametri in A, con x tupla (iniettiva) di variabili. Sia a una tupla di termini a parametri in A; definiamo la sostituzione di x con a in t(x) e scriviamo t(x/a) (o più brevemente t(a)) per induzione sulla sintassi di t(x):
    b1) se t(x) è un parametro, diciamo t(x) = c \in A, allora t(a) = c;
    b2) se t(x) è una singola variabile, diciamo t(x) = y, allora t(a) = y se y \not \in x; altrimenti t(a) = a_i se x_i = y;
    i) se f è un simbolo di funzione di arietà n e t(x) = ft_1(x) t_2(x) \ldots t_n(x) dove t_1(x), t_2(x), ..., t_n(x) sono termini per cui è già stata definita l'operazione di sostituzione, poniamo t(a) := f t_1(a) t_2(a) \ldots t_n(a).

Lemma Sia (L,\text{ar}) un linguaggio del prim'ordine e sia A un insieme di parametri. Se t(x) è un termine di L a parametri in a, dove x è una tupla (iniettiva) di variabili e s è una tupla di termini con \text{lh}(s) = \text{lh}(x), allora t[x/s] è ancora un termine di L a parametri in A.

Nota 5. La notazione introdotta per i termini viene detta notazione prefissa. In questo modo se assumiamo ad esempio il linguaggio L_{ga} = \{0,+,-\} dei gruppi addittivi, come insieme dei parametri A = \emptyset, sono termini +xy, +x-y, +-x+yz. Con l'usuale notazione infissa essi si leggono x+ y, x + (-y), (-x) + (y + z). La scelta della notazione prefissa semplifica molte trattazioni di natura teorica. Nella pratica, tuttavia, utilizzeremo comunque la notazione infissa.

Un termine può essere pensato come una tupla di elementi di L \cup V \cup A soddisfacente ad opportune regole sintattiche. Sorge spontaneamente la seguente domanda: è possibile leggere una tale sequenza in due modi distinti? La risposta è no, come ci apprestiamo a dimostrare.

Lemma (univoca leggibilità dei termini) Fissato un linguaggio del prim'ordine (L,\text{ar}) ed un insieme di parametri A, siano t_1, t_2, \ldots, t_n, s_1, s_2, \ldots, s_m termini a parametri in A pensati come tuple di elementi in L \cup V \cup A, tali che t_1 t_2 \ldots t_n = s_1 s_2 \ldots s_m (uguaglianza di tuple, cioè di funzioni). Allora n = m e t_i = s_i per ogni 1 \le i \le n.

Procederemo per induzione sul numero di simboli di funzione che occorrono in t_1 t_2 \ldots t_n. Se non compaiono simboli di funzione, allora necessariamente ciascun t_i è atomico e pertanto è un parametro oppure una singola variabile. Per uguaglianza di tuple, allora deve necessariamente seguire che n = m e t_i = s_i.
Supponiamo ora di aver dimostrato la tesi per sequenze in cui compaiono al più k-1 simboli di funzione e sia t_1 t_2 \ldots t_n una sequenza in cui compaiono esattamente k simboli di funzione. Se t_1 t_2 \ldots t_n = s_1 s_2 \ldots s_m e i è il più piccolo indice per cui t_i contiene un simbolo di funzione, allora necessariamente t_i inizia con un simbolo di funzione e quindi, per uguaglianza di tuple e per ipotesi induttiva, si deve concludere m \ge i e t_j = s_j per ogni 1 \le j \le i. Pertanto non è restrittivo supporre i = 1. In tal caso t_1 = f t_1' t_2' \ldots t_h', dove h è l'arietà del simbolo f. Analogamente, per uguaglianza di tuple, dovrà aversi s_1 = f s_1' s_2' \ldots s_h'. Pertanto otteniamo l'uguaglianza
t_1' t_2' \ldots t_h' t_2 \ldots t_n = s_1' s_2' \ldots s_h' s_2 \ldots s_m
in cui compaiono al più k-1 simboli di funzione. Segue la tesi per ipotesi induttiva. \square


Supponiamo che (M, (\cdot)^M) sia una struttura di segnatura L. Ci proponiamo di associare ad ogni termine t(x) a parametri in A \subseteq M, con x tupla finita di variabili, una funzione t^M \colon M^{\text{lh}(x)} \to M. Tale funzione sarà detta interpretazione di t(x) in M. Procediamo per gradi, definendo innanzi tutto l'interpretazione di un termine chiuso.

Definizione (interpretazione di un termine chiuso) Siano M, A ed L come nel discorso precedente, sia t un termine chiuso. Definiamo la sua interpretazione per induzione sulla sintassi di t:
b1) se t è atomico, e quindi è un parametro, diciamo t = a \in A \subseteq M, poniamo t^M = a;
i) se f è un simbolo di funzione di arietà n e t_1, \ldots t_n sono termini chiusi a parametri in A per cui è già stata definita l'interpretazione in M, poniamo (ft_1 t_2 \ldots t_n)^M := f^M(t_1^M, t_2^M, \ldots, t_n^M).

Nota 6. Si osservi che la precedente definizione è ben data solo alla luce del Lemma di univoca leggibilità dei termini. Infatti, solo grazie a tale lemma è possibile essere sicuri di poter individuare esattamente qual è il primo, il secondo, ..., l'n-esimo termine in ft_1 t_2 \ldots t_n.

Definizione (interpretazione di un termine) Siano M, A e L come nel discorso precedente, sia t(x) un termine a parametri in A, con x tupla finita (e iniettiva) di variabili. Definiamo l'interpretazione di t(x) in M come la funzione
\begin{matrix} t^M(x) \colon & M^{\text{lh}(x)} & \to & M \\ & a & \mapsto & (t[x/a])^M \end{matrix}

Esempio.
Sia L_{au} = \{0, 1, +, -, \cdot\} il linguaggio degli anelli unitari, con arietà naturale dei simboli. In questo caso i termini del linguaggio a parametri in A sono i polinomi a coefficienti in A. La loro interpretazione in un qualsiasi anello unitario è data dalle funzioni polinomiali.
Je n'ai jamais compris qu'on se rassasiât d'un être...
maurer
 
Messaggi: 1040
Iscritto il: mar 28 lug 2009, 12:14
Località: A metà strada per il Paradiso...!

Messaggioda maurer il ven 16 nov 2012, 23:17

Abbiamo visto come codificare, nell'ambito di un linguaggio del prim'ordine (L,\text{ar}) le "parole". Vedremo adesso come codificare le "frasi". Come in precedenza abbiamo associato ad ogni ad ogni parola un significato, associando una funzione ad ogni termine, adesso il nostro obiettivo è quello di assegnare ad ogni "frase" un insieme: l'insieme dei valori che rendono vera la "frase". Vediamo come si può rendere matematicamente solido tutto questo.

Esattamente come abbiamo fatto con i termini, definiremo le formule come sequenze di simboli che rispettano particolari leggi (induttive) di costruzione. Avremo, in più rispetto ai simboli del linguaggio, eventuali parametri e variabili, anche alcuni simboli logici, detti connettivi, che elenchiamo qui di seguito:
  • \bot, simbolo di contraddizione;
  • \land simbolo di congiunzione;
  • \lnot simbolo di negazione;
  • \exists quantificatore esistenziale.
Gli altri simboli logici con cui si lavora quotidianamente in matematica verranno introdotti a tempo debito come abbreviazioni di particolari formule.

E' conveniente motivare le definizioni che seguiranno con un esempio iniziale.

Esempio.
Fissiamo il linguaggio L_{ao} = \{0, 1, +, -, \cdot, <\} degli anelli ordinati, che estende il linguaggio degli anelli unitari con un simbolo di relazione binaria. I termini di questo linguaggio sono, come si è visto negli esempi precedenti, i polinomi. Fissata una struttura (M, (\cdot)^M) è abbastanza naturale prendere come insiemi definibili elementari gli insiemi della forma \{a \subseteq M \mid \: t(a) = s(a)\} e \{a \subseteq M \mid \: t(a) < s(a)\}. Questi insiemi possono essere codificati mediante le formule t(x) = s(x) e t(x) < s(x). Questo ci suggerisce un modo di definire in via generale la nozione di formula e, attraverso questo concetto, quello di insieme definibile.

Occorre ancora una premessa, prima della definizione di formula del prim'ordine. Supponiamo di aver fissato un linguaggio del prim'ordine (L,\text{ar}), un insieme di parametri A e un insieme di variabili V. Occorre introdurre un secondo insieme delle variabili, U, disgiunto da tutti gli insiemi considerati finora, che chiameremo insieme delle variabili ausiliarie. I suoi elementi saranno chiamati variabili ausiliarie oppure variabili quantificate. Il loro scopo è puramente tecnico e serve a facilitare le definizioni e le dimostrazioni. Nella pratica, non faremo particolare distinzione tra i due insiemi di variabili (piuttosto, ignoreremo le variabili ausiliarie).

Definizione (formula) Sia (L,\text{ar}) un linguaggio del prim'ordine e sia A un insieme di parametri. Diciamo formula in L a parametri in A una sequenza finita di elementi di L \cup A \cup V (dove V è un opportuno insieme di variabili) che soddisfa al seguente procedimento costruttivo induttivo:
    b1) se t e s sono due termini a parametri in A, allora \doteq ts è una formula;
    b2) se r è un simbolo di relazione di arietà n e t_1, t_2, \ldots, t_n sono termini a parametri in A allora rt_1 t_2 \ldots t_n è una formula a parametri in A;
    i1) \bot è una formula a parametri in A;
    i2) se \varphi è una formula a parametri in A, \lnot \varphi è una formula a parametri in A;
    i3) se \varphi, \psi sono due formule, \land \varphi \psi è una formula a parametri in A;
    i4) se \varphi è una formula, x è una (singola) variabile libera e u è una (singola) variabile ausiliaria che non occorre in \varphi allora \exists u \: \varphi[x/u] è una formula a parametri in A.
Diremo che una formula è atomica se è costruibile senza utilizzare i passi i1) - i4); diremo che una formula è chiusa, oppure che è un enunciato se non contiene variabili libere; diremo che una formula è pura se in essa non occorrono parametri. Scriveremo poi \varphi(x) per indicare che nella formula \varphi occorrono al più le variabili della tupla x.

Lemma Sia (L,\text{ar}) un linguaggio del prim'ordine e sia A un insieme di parametri. Se \varphi(x) è una formula a parametri in A, x è una tupla di variabili e t è una tupla di termini della stessa lunghezza di x allora anche \varphi[x/t] è una formula.

Lemma (univoca leggibilità delle formule) Sia (L,\text{ar}) un linguaggio del prim'ordine e sia A un insieme di parametri. Se \varphi_1, \varphi_2, \ldots, \varphi_n e \psi_1, \psi_2, \ldots, \psi_m sono formule pensate come tuple di elementi di L \cup A \cup V \cup U a cui si aggiungano i simboli logici tali che \varphi_1 \varphi_2 \ldots \varphi_n = \psi_1 \psi_2 \ldots \psi_m allora n = m e \varphi_i = \psi_i per ogni i = 1, 2, \ldots, n.

Possiamo ora definire l'interpretazione delle formule. Iniziamo, come abbiamo fatto per i termini, dalle formule chiuse, o enunciati.

Definizione (Interpretazione delle formule chiuse) Sia (L, \text{ar}) un linguaggio del prim'ordine e sia M un modello di L. Sia A \subseteq M un insieme di parametri. Definiamo l'interpretazione di una formula chiusa \varphi a parametri in A per induzione sulla sintassi:
    b1) se \varphi = \doteq ts dove t e s sono due termini chiusi a parametri in A poniamo
    (\doteq ts)^M = \begin{cases} \{\emptyset\} & \text{se } t^M = s^M \\ \emptyset & \text{altrimenti} \end{cases}
    b2) se \varphi = rt_1 \ldots t_n dove r è un simbolo di relazione n-aria e t_1, \ldots, t_n sono termini a parametri in A allora poniamo
    \varphi^M = \begin{cases} \{\emptyset\} & \text{se } (t_1^M, t_2^M, \ldots, t_n^M) \in r^M \\
\emptyset & \text{altrimenti} \end{cases}
    i1) \bot^M = \emptyset;
    i2) se \varphi è una formula chiusa a parametri in A per cui è già stata definita l'interpretazione allora (\lnot \varphi)^M := \{\emptyset\} \setminus \varphi^M;
    i3) se \varphi, \psi sono due formule chiuse a parametri in A per cui è già stata definita l'interpretazione allora (\land \varphi \psi)^M := \varphi^M \cap \psi ^M;
    i4) se \varphi(x) è una formula, con x singola variabile, tale che è già stata definita l'interpretazione di \varphi(a) per ogni a \in A allora
    \displaystyle (\exists u \: \varphi[x/u])^M := \bigcup_{a \in A} (\varphi(a))^M

Nota 1. Nel seguito poniamo scriveremo M \vDash \varphi per intendere \varphi^M = \{\emptyset\} e M \nvDash \varphi per intendere \varphi^M = \emptyset. Nel primo caso diremo che M modella \varphi, nel secondo caso che M non modella \varphi. Si osservi anche che M \nvDash \varphi \iff M \vDash \lnot \varphi.

Definizione (interpretazione delle formule) Sia (L, \text{ar}) un linguaggio del prim'ordine, sia M un suo modello e sia A \subseteq M un insieme di parametri. Sia poi \varphi(x) una formula a parametri in A con x tupla finita di variabili e sia n = \text{lh}(x). Diciamo interpretazione di \varphi(x) la relazione n-aria definita da
(a_1, \ldots, a_n) \in (\varphi(x))^M \iff M \vDash \varphi(a_1a_2\ldots a_n)

Se a \subseteq M è una tupla finita e \varphi(x) è una formula con \text{lh}(x) = \text{lh}(a) diremo che a verifica \varphi se M \vDash \varphi(a).

Definizione (Insiemi definibili) Diremo che un insieme è definibile se è costituito dalle tuple di elementi che verificano \varphi(x) per qualche formula \varphi(x).
Je n'ai jamais compris qu'on se rassasiât d'un être...
maurer
 
Messaggi: 1040
Iscritto il: mar 28 lug 2009, 12:14
Località: A metà strada per il Paradiso...!


Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron