Esercizio di logica del primo ordine
Ciao a tutti!
Sto studiando la logica del primo ordine, e mi sono imbattuta nel seguente esercizio:
Nel linguaggio costituito da un solo simbolo unario di funzione $f$, con $f^{\mathfrak{A}}:A\rightarrow A$ (si intende: $f$ interpretata in $\mathfrak{A}$), formulare un enunciato $\sigma$ tale che:
(a) $\mathfrak{A}\models \sigma \Rightarrow \mathfrak{A}$ è infinito,
(b) ogni insieme infinito può essere esteso ad un modello di $\sigma$.
Dà anche un piccolo suggerimento dicendo che deve essere utilizzato il concetto di funzione iniettiva.
L'enunciato a cui ho pensato è il seguente:
$\sigma$ è $\forall x \forall y (f(x)=f(y) \rightarrow x=y) \wedge \exists y \forall x (\neg(y=f(x)))$
che è quanto dire che $f$ è iniettiva ma non suriettiva.
Il problema è il seguente: il punto (a) mi sembra soddisfatto, ma non capisco perché nel punto (b) si parla di estensione: dal mio punto di vista ogni insieme infinito è un modello di $\sigma$.
Dove sbaglio?
Sto studiando la logica del primo ordine, e mi sono imbattuta nel seguente esercizio:
Nel linguaggio costituito da un solo simbolo unario di funzione $f$, con $f^{\mathfrak{A}}:A\rightarrow A$ (si intende: $f$ interpretata in $\mathfrak{A}$), formulare un enunciato $\sigma$ tale che:
(a) $\mathfrak{A}\models \sigma \Rightarrow \mathfrak{A}$ è infinito,
(b) ogni insieme infinito può essere esteso ad un modello di $\sigma$.
Dà anche un piccolo suggerimento dicendo che deve essere utilizzato il concetto di funzione iniettiva.
L'enunciato a cui ho pensato è il seguente:
$\sigma$ è $\forall x \forall y (f(x)=f(y) \rightarrow x=y) \wedge \exists y \forall x (\neg(y=f(x)))$
che è quanto dire che $f$ è iniettiva ma non suriettiva.
Il problema è il seguente: il punto (a) mi sembra soddisfatto, ma non capisco perché nel punto (b) si parla di estensione: dal mio punto di vista ogni insieme infinito è un modello di $\sigma$.
Dove sbaglio?
Risposte
Premetto che anche io non sono sicuro del significato da dare al termine "esteso" nel secondo punto.
In ogni caso un insieme non è ancora un modello di una teoria formale. Un insieme può fungere da sostegno di un modello. Un modello è un oggetto strutturato formato da un insieme (detto in genere sostegno o dominio) e una serie di funzioni di interpretazione tra termini linguistici e particolari oggetti insiemistici.
Forse l'esercizio chiede di mostrare che, dato un qualsiasi insieme infinito $A$, esiste una funzione da $A$ in $A$ da poter usare per definire un modello $\mathfrak{A}$ interpretando poi il simbolo funzionale $f$ su questa funzione in maniera tale che $sigma$ sia soddisfatta.
Ma è un modo in cui ho interpretato le cose, può essere che "esteso" significa tutt'altro.
Ora comunque anche se la mia interpretazione della traccia è giusta, per verificare i due punti è necessario usare una qualche definizione di "insieme infinito". Se "insieme infinito" significa equipotente ad una sua parte propria la dimostrazione del secondo punto si conclude subito: basta interpretare $f$ su una di queste funzioni esistenti (secondo la definizione di infinito) tra il tutto e la parte. Se significa altro, come per esempio "dato un qualsiasi $n in N$ esistono $x_0,...,x_n in A$ tutti distinti tra loro" bisogna mostrare poi che la funzione biettiva tra tutto l'insieme $A$ e la sua parte propria esiste qualora sia vera questa assunzione che definisce l'infinità di $A$ per poter interpretare poi il simbolo funzionale $f$ opportunamente per costruire un modello di $sigma$ a partire dall'insieme infinito $A$.
Il secondo punto è diverso dal primo perché mentre il primo afferma solo che ogni modello di $sigma$ ha un dominio non finito (e non verifica affatto che debba esistere questo modello: in linea di principio potrebbe anche essere vuota la classe dei modelli ammissibili, infatti per verificare soltanto il primo punto avresti potuto usare anche un'asserzione contraddittoria del tipo $\forall x \not (f(x) = f(x))$), il secondo punto afferma che, anche se esistesse un solo insieme infinito la teoria con $sigma$ ha un modello che si può "costruire" a partire da questo insieme qua.
In generale dimostrare che una teoria al primo ordine ha solo modelli non finiti risulta abbastanza semplice (è vero per la teoria degli insiemi, è vero per la teoria dei numeri... E così via... Dimostrare che a partire da un insieme infinito che si usa come sostegno si può poi costruire un modello della teoria in genere è più complicato e problematico, una dimostrazione del genere sarebbe equivalente ad una dimostrazione della coerenza della teoria partendo dall'assunzione che un insieme infinito esiste. Comunque la tua soluzione, se la mia interpretazione è corretta dovrebbe verificare anche il punto due. Avresti già risolto il problema. Forse non hai notato il fatto che per verificare solo il punto a) avresti potuto usare un'asserzione $sigma$ contraddittoria.
In ogni caso un insieme non è ancora un modello di una teoria formale. Un insieme può fungere da sostegno di un modello. Un modello è un oggetto strutturato formato da un insieme (detto in genere sostegno o dominio) e una serie di funzioni di interpretazione tra termini linguistici e particolari oggetti insiemistici.
Forse l'esercizio chiede di mostrare che, dato un qualsiasi insieme infinito $A$, esiste una funzione da $A$ in $A$ da poter usare per definire un modello $\mathfrak{A}$ interpretando poi il simbolo funzionale $f$ su questa funzione in maniera tale che $sigma$ sia soddisfatta.
Ma è un modo in cui ho interpretato le cose, può essere che "esteso" significa tutt'altro.
Ora comunque anche se la mia interpretazione della traccia è giusta, per verificare i due punti è necessario usare una qualche definizione di "insieme infinito". Se "insieme infinito" significa equipotente ad una sua parte propria la dimostrazione del secondo punto si conclude subito: basta interpretare $f$ su una di queste funzioni esistenti (secondo la definizione di infinito) tra il tutto e la parte. Se significa altro, come per esempio "dato un qualsiasi $n in N$ esistono $x_0,...,x_n in A$ tutti distinti tra loro" bisogna mostrare poi che la funzione biettiva tra tutto l'insieme $A$ e la sua parte propria esiste qualora sia vera questa assunzione che definisce l'infinità di $A$ per poter interpretare poi il simbolo funzionale $f$ opportunamente per costruire un modello di $sigma$ a partire dall'insieme infinito $A$.
Il secondo punto è diverso dal primo perché mentre il primo afferma solo che ogni modello di $sigma$ ha un dominio non finito (e non verifica affatto che debba esistere questo modello: in linea di principio potrebbe anche essere vuota la classe dei modelli ammissibili, infatti per verificare soltanto il primo punto avresti potuto usare anche un'asserzione contraddittoria del tipo $\forall x \not (f(x) = f(x))$), il secondo punto afferma che, anche se esistesse un solo insieme infinito la teoria con $sigma$ ha un modello che si può "costruire" a partire da questo insieme qua.
In generale dimostrare che una teoria al primo ordine ha solo modelli non finiti risulta abbastanza semplice (è vero per la teoria degli insiemi, è vero per la teoria dei numeri... E così via... Dimostrare che a partire da un insieme infinito che si usa come sostegno si può poi costruire un modello della teoria in genere è più complicato e problematico, una dimostrazione del genere sarebbe equivalente ad una dimostrazione della coerenza della teoria partendo dall'assunzione che un insieme infinito esiste. Comunque la tua soluzione, se la mia interpretazione è corretta dovrebbe verificare anche il punto due. Avresti già risolto il problema. Forse non hai notato il fatto che per verificare solo il punto a) avresti potuto usare un'asserzione $sigma$ contraddittoria.
Grazie, mi hai illuminata su più di un punto! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo