Logiche del primo ordine

[TomSawyer1]

La regola di $\forall$-formazione dice
$\Gamma, z \in D \vdash A(z) \implies \Gamma \vdash (\forall x \in D)A(x)$, con $z$ non libera nel dominio $D$. Poi Wikipedia dice

"Ciò significa che z non deve già comparire in qualche proposizione del sequente altrimenti si avrebbe un sistema inconsistente: asserire che, dato A per una certa variabile, valga A per tutti gli elementi del dominio è assolutamente folle."

Ok, ma non è quello che si sta facendo, quando si scrive $(\forall x \in D)A(x)$? Oppure $x$ ha qualche altra proprietà implicita?

[TomSawyer1]

Io ho trovato questa affermazione su Wikipedia:
"Also, it follows from the [compactness]theorem that any theory that has an infinite model has models of arbitrary large cardinality (this is the Upward Löwenheim–Skolem theorem)."

Come devo interpretarla, allora?

[fields1]

"TomSawyer":Pensavo valesse anche l'altra implicazione, cioè pensavo che il teorema fosse: la proposizione $S$ ha un modello infinito sse ha modelli arbitrariamente grandi. Se è così, allora, se $X$ è finito, $F$ non ha modelli arbitrariamente grandi, quindi etc...

No, non vale il viceversa. Sai trovarmi una proposizione di un qualche linguaggio che ha un modello infinito ma non modelli finiti arbitrariamente grandi?

"TomSawyer":Oppure bisogna semplicemente osservare che, dato che ogni sottoinsieme di $X$ ha un modello, ed essendo $X$ finito, allora, per il th. di compattezza, il modello di $F$ è necessariamente finito? Che poi mi sembra più o meno la stessa argomentazione..

Non mi sembra corretto. Tra l'altro $X$ è un insieme di naturali, per cui cosa vuol dire: "dato che ogni sottoinsieme di $X$ ha un modello"?

L'argomentazione era analoga a quelle che la seguivano. Se $X$ e' finito, $NN-X$ e' infinito e dunque $\not F$ ha modelli arbitrariamente grandi e dunque un modello infinito la cui cardinalita' puo' essere presa uguale a quella del modello infinito di $F$, che dunque rendera' vero $F$ e $\not F$: assurdo.

[TomSawyer1]

Pensavo valesse anche l'altra implicazione, cioè pensavo che il teorema fosse: la proposizione $S$ ha un modello infinito sse ha modelli arbitrariamente grandi. Se è così, allora, se $X$ è finito, $F$ non ha modelli arbitrariamente grandi, quindi etc...

Oppure bisogna semplicemente osservare che, dato che ogni sottoinsieme di $X$ ha un modello, ed essendo $X$ finito, allora, per il th. di compattezza, il modello di $F$ è necessariamente finito? Che poi mi sembra più o meno la stessa argomentazione..

[fields1]

"TomSawyer":$F$ non ha un modello infinito, perché, essendo $X$ finito, non ha modelli arbitrariamente grandi, che sarebbe l'unica via per far avere ad $F$ un modello infinito. O sbaglio?

Attenzione "sarebbe l'unica via per far avere ad $F$ un modello infinito" non va bene come argomentazione. In realta' la cosa e' piu' sottile, riprova (inutile dire, servira' il th. di compattezza)

"TomSawyer":Alla fine, molti teoremi si dimostrano usando quasi sempre gli stessi argomenti. Molto belle queste dimostrazioni, comunque.

Te l'avevo detto che il teorema di compattezza e' ubiquo. Tra l'altro e' equivalente al principio dell'ultrafiltro, dunque si trova anche in topologia e algebra

[TomSawyer1]

Alla fine, molti teoremi si dimostrano usando quasi sempre gli stessi argomenti. Molto belle queste dimostrazioni, comunque.

$F$ non ha un modello infinito, perché, essendo $X$ finito, non ha modelli arbitrariamente grandi, che sarebbe l'unica via per far avere ad $F$ un modello infinito. O sbaglio?

[fields1]

Innanzitutto osserva che un modello di una qualsiasi proposizione della nostra teoria e' un semplice insieme. Il primo lemma che viene in mente è allora questo: due modelli di ugual cardinalità rendono vero lo stesso insieme di proposizioni della nostra teoria. Questo è ovvio: due modelli della stessa cardinalità, essendo semplici insiemi, sono isomorfi (e c'è un teorema che dice che se due modelli sono isomorfi rendono vero lo stesso insieme di proposizioni).

Sia allora $F$ un enunciato della nostra teoria. Sia $X$ l'insieme degli $n\in NN$ tali che $F$ ha un modello di cardinalita' $n$. Se $X$ e' finito, $F$ non ha un modello infinito (perche'?). Dunque $F$ e' banalmente equivalente a $\sigma(X)$.
Se $X$ e' infinito, supponiamo per assurdo che $NN-X$ sia infinito. Allora sia $F$ sia $\not F$ hanno modelli finiti arbitrariamente grandi e dunque, per il teorema di compattezza, hanno rispettivamente un modello infinito numerabile $M$ e un modello infinito numerabile $M'$. Ma $M$ e $M'$ hanno la stessa cardinalita', quindi rendono vero lo stesso insieme di proposizioni, e dunque entrambi rendono vere $F$ e $\not F$, assurdo. Dunque $NN-X$ e' finito e dunque $F$ equivale a $\not \sigma(NN-X)$.

[TomSawyer1]

Una cosa che non capisco e' perche' ogni proposizione di questa teoria sia equivalente o a $\sigma(N)$ o a $\neg\sigma(N)$, per qualche qualche sottoinsieme finito dei numeri non negativi, e $\sigma(N)$ dice che il numero di elementi e' in $N$.

[fields1]

Tu non hai utilizzato nessun predicato o nessuna funzione o costante nel tuo insieme di formule. Dunque hai rispettato il fatto che la segnatura e' vuota. Il simbolo di $=$ naturalmente e' primitivo, e' un simbolo logico, non fa parte mai della segnatura (ovvero, e' di serie )

[TomSawyer1]

Mi sono espresso male.. Intendevo: come è possibile definire degli assiomi del genere in questo tipo di logica, in cui la segnatura è vuota?

[fields1]

Sì, va bene il tuo insieme per definire l'infinito. Non è che ci siano molti altri modi. Un'altro può essere:

${\not \exists x_1...\exists x_n \forallx x=x_1\vee...\vee\x=x_n | n\in NN^+}$

[TomSawyer1]

Modificato il titolo del topic, in quanto piu' appropriato.

Ora ho delle domande sulla pure identity theory (la teoria della pura identita' ?). Prima di tutto, vorrei capire l'esatto senso di questa teoria. La sua segnatura e' vuota. Ma, allora, come si puo' definire in questo linguaggio un insieme infinito di assiomi, per esempio
$\exists x_1 \exists x_2 (x1\ne x_2)$
$\exists x_1 \exists x_2 \exists x_3 (x1\ne x_2 \wedge x_1\ne x_3 \wedge x_2\ne x_3)$
$\vdots$,
per definire l'infinito?

[fields1]

Ho utilizzato due volte la stessa lettera, ma non volevo dire che i modelli sono uguali. Correggo

[TomSawyer1]

Se $\Gamma \cup \Delta$ ha un modello $M$, come si può dire che si tratti dello stesso modello di prima, per cui hai dimostrato che $M \in \not P$?

Grazie per le dispense, sono davvero ricche.

[fields1]

Ho trovato delle dispense di logica davvero ricche, approfondite e ben fatte, al punto da essere in realtà un libro. http://www.dm.unito.it/personalpages/andretta/

[fields1]

Mi sembra che hai fatto confusione. Non si capisce chi è la tua $P$: una proprietà (quindi un insieme di modelli) o un'insieme di formule?

Comunque, l'esercizio si può fare così. Sia $P$ una proprietà non esprimibile con un numero finito di formule, ma esprimibile con un insieme infinito di formule $\Gamma$. Supponiamo per assurdo che $\not P$ sia esprimibile con un insieme di formule $\Delta$ (essendo $P$ un insieme di modelli, con $\not P$ indichiamo l'insieme complemento, ovviamente).
Consideriamo l'insieme ora $\Delta uu \Gamma$. Dimostriamo che ogni sottinsieme finito di $\Delta uu \Gamma$ ha un modello. Sia $F$ un sottinsieme finito di $\Gamma$ e $G$ un sottinsieme finito di $\Delta$. Poiché $F$ per ipotesi non esprime $P$, certamente $F$ ha un modello $M\in \not P$. Inoltre, poiché $\Delta$ esprime $\not P$, abbiamo che $M$ rende vero $\Delta$, e quindi $G$. Dunque, $M$ è un modello di $G uu F$.
Concludiamo allora, per il teorema di compattezza, che $\Gamma uu \Delta$ ha un modello $N$. Ma allora $N\in P$ e $N\in\not P$, assurdo.

[TomSawyer1]

Hmm direi che se $P$ è enunciata attraverso infinite proposizioni, allora $P$ è finitamente consistente, con modelli arbitrariamente grandi, dato che il modello di $P$ è infinito, che non permettono l'enunciazione di $\not P$. Ma mi sembra troppo semplice, quindi è di sicuro sbagliato.. Penso che si debba sruttare il fatto che i sottoinsiemi di $P$ abbiano modelli arbitrariamente grandi, ma non saprei esattamente come.

[fields1]

Fissiamo un certo linguaggio $L$. Una proprietà, estensionalmente, è un insieme di modelli adatti al linguaggio $L$ (ovvero modelli che devono avere relazioni, funzioni e costanti come richiesto dai simboli del linguaggio). Una proprietà $P$ si dice "esprimibile" se esiste un insieme $\Gamma$ di formule tale che $\Gamma$ e' vero in un modello $M$ sse $M\in P$.

Avendo formalizzato, ti sarebbe utile provare a fare il primo esercizio (se poi ti trovi in difficolta', chiedi). Devi soltanto usare il teorema di compattezza, null'altro.

Per il secondo, semplicemente, se una proprieta' e' esprimibile da un numero finito di proposizioni, allora e' esprimibile da un'unica formula $A$ (la loro congiunzione). Ma allora $\not A$ esprime la negazione della proprieta'.

[TomSawyer1]

Capito, $E'$ non ha variabili libere, ma generiche.

Ho letto che se una proprietà ha bisogno di infinite proposizioni della logica di primo ordine (FOL) per essere espressa, allora la sua negazione non può essere espressa nella FOL. Ma se una proprietà può essere espressa da un numero finito di proposizioni della FOL, allora anche la sua negazione può essere espressa nella FOL.

Quali sono i motivi (più o meno formali) di questi due fatti?

[fields1]

PS: Perché non ho considerato formule atomiche del tipo $x

Cita 0 0

Segnala

[fields1]

In ogni caso è bene notare che il metodo di eliminazione dei quantificatori che ho definito è costruttivo; ovvero, data una formula, in un numero finito di passi riusciamo a trasformarla in una equivalente senza quantificatori.

Passiamo ora alla completezza. Una formula nel linguaggio di $T$ si dice un enunciato se non ha variabili libere. Per la completezza dobbiamo dimostrare che per ogni enunciato nel linguaggio di $T$, o lui o la sua negazione sono conseguenza logica di $T$.

Sia allora $E$ un enunciato nel linguaggio di $T$. Per il risultato sull'eliminazione dei quantificatori, esso è equivalente ad una formula $E'$ senza quantificatori. Poiché $E$ non ha variabili libere, nemmeno $E'$ le ha; dunque, $E'$ è fatta soltanto con i simboli $\wedge,\vee,\not, V$. Dunque, $E'$ equivale sempre al vero oppure sempre al falso. Dunque o ogni modello di $T$ verifica $E'$ oppure ogni modello di $T$ verifica $\not E'$. Dunque o $E'$ o $\not E'$ è conseguenza logica di $T$, e per l'equivalenza, o $E$ o $\not E$ è conseguenza logica di $T$.