Zermelo-Fraenkel e insiemi amorfi

[otta96]

Idem sulla definizione di insieme infinito.

[hydro]

Potete trovare una funzione iniettiva $\mathbb N\to X$ per ricorsione: prendete $a_1\in X$ e definite $f(1)=a_1$. Ora $X\setminus \{a_1\}$ è non vuoto, perchè altrimenti $X$ sarebbe in biiezione con un insieme finito, quindi esiste $a_2\in X\setminus\{a_1\}$ e definite $f(2)=a_2$, e così via.

Ovviamente ci si può chiedere dove si sta usando l'assioma della scelta, e la risposta è che quando si definiscono le successioni per ricorsione si usa l'assioma della scelta dipendente. Nello specifico potete vederlo così: Per ogni $n\in \mathbb N$, esiste una funzione iniettiva $\{1,\ldots,n\}\to X$, altrimenti $X$ sarebbe finito. Adesso guardate l'insieme $S=\{f: \{1,\ldots,n\}\to X \text{ iniettive: }n\in\mathbb N\}$ e definite la seguente relazione: $\varphi:\{1,\ldots,n\}\to X$ è in relazione con $\psi:\{1,\ldots,m\}\to X$ se e solo se $m=n+1$ e $\psi$ estende $\varphi$. Questa è una relazione totale su $S$ perchè ogni funzione iniettiva $\{1,\ldots,n\}\to X$ può essere estesa ad una $\{1,\ldots,n+1\}\to X$, visto che $X$ è infinito. Per l'assioma della scelta dipendente esiste una funzione $f:\mathbb N\to S$ tale che $f(n)$ è in relazione con $f(n+1)$ per ogni $n$. Adesso la vostra successione iniettiva $\mathbb N\to X$ è definita da $n\mapsto f(m)(n)$, dove $m$ è un qualsiasi intero positivo tale che il dominio di $f(m)$ contenga $n$.

[otta96]

Ah ecco come si fa a farlo per bene, era da tempo che ogni tanto pensavo come si facesse a dimostrarlo con DC.
Ma anche con C pieno avevo pensato a qualcosa del tipo: $AAn\inNNEEa_n\inX(a_n!=a_iAA0<=i<n)$, poi definire $f:NN->X$ per ricorsione in modo che $f(n)=a_n$ facendo una funzione di scelta per la famiglia ${X_n={X\setminus{a_i|0<=i<n}}|n\inNN}$.
Il problema è che questa cosa non garantiva che $f(n)=a_n$, quindi non mi tornava.

[thedarkhero]

Interessante!

Provo a ricapitolare.
Assumiamo l'assioma della scelta dipendente.
Se $X$ è un insieme infinito allora posso costruire una successione iniettiva $(a_n)_{n \in NN}$ di elementi distinti di $X$ utilizzando l'assioma della scelta dipendente nel modo suggerito da @hydro, quindi posso considerare l'insieme $Y=\{a_{2n}:n \in NN\} \subseteq X$ che è ancora infinito ed ha il complementare infinito per concludere che $X$ non è amorfo, come suggerito da @otta96. Giusto?

Se invece che assumere l'assioma della scelta dipendente assumo l'assioma della scelta numerabile (che è più debole) posso ancora provare che gli insiemi amorfi non esistono (sempre lavorando in ZF)?

[otta96]

È una buona ricapitolazione, la risposta all'ultima domanda non la so ma mi sa di no.
A questo punto a me interesserebbe capire come da C si può dimostrare DC.

[bub]

ZF + "esiste un insieme amorfo" è equiconsistente con ZF, questo si trova ad esempio su Wikipedia e già sarebbe interessante trovare qualche riferimento accessibile (la fonte che cita Wikipedia non è liberamente accessibile).
Immagino però che si intenda che (se ZF è consistente) ZF + "esiste un insieme amorfo" è consistente dal punto di vista sintattico, cioè che da ZF + "esiste un insieme amorfo" non si possano derivare contraddizioni.
Io vorrei capire se ZF + "esiste un insieme amorfo" è consistente anche dal punto di vista semantico, cioè se esiste un modello di ZF + "esiste un insieme amorfo".
Inizialmente avevo pensato che la consistenza sintattica implica quella semantica ma per dimostrarlo serve l'assioma della scelta; se però assumiamo l'assioma della scelta gli insiemi amorfi non possono esistere.

Avevo già commentato, ma poi ho cancellato la risposta perché ho pensato di aver male interpretato cosa avevi scritto.

Credo che una prova dell'equiconsistenza sintattica di due sistemi non assicura la consistenza sintattica di nessune dei due comunque, anche l'equiconsistenza semantica non assicura che esiste un modello per nessuno dei due.
Se si afferma che

A) se ZF ha un modello allora ha un modello anche ZF + "esiste un insieme amorfo"

pur avendo dimostrato questa cosa non è determinato comunque se esistono questi modelli.

Non so cosa serve per dimostrare l'esistenza di un modello per ZF, probabilmente si dovrà usare un sistema rafforzato rispetto a ZF (non so in quale senso però) e servirà perciò comunque un sistema rafforzato rispetto a ZF anche per dimostrare la consistenza di ZF + "esiste un insieme amorfo", qualcosa bisognerà aggiungerla per forza di cose (qualche altro assioma a ZF).

Solo con ZF non si può riuscire a dimostrare l'esistenza di questo modello per ZF + "esiste un insieme amorfo" perché implicherebbe che ZF riesce a dimostrare la propria consistenza.

Per dimostrare l'esistenza di un modello per ZF, che sistema serve?
Tramite questo sistema forse poi si riesce a dimostrare l'esistenza di un modello anche per ZF + "esiste un insieme amorfo".

Che sono equiconsistenti sintatticamente immagino significhi che se è contraddittorio il primo (tramite le regole di deduzione) lo è il secondo e viceversa. Anche se si disponesse di un teorema che ci dice che si può passare dalla consistenza sintattica (non si derivano contraddizioni) a quella semantica (esiste un modello) comunque non si è dimostrato per nessuno dei due sistemi che uno dei due è consistente e perciò non si potrà affermare per nessuno dei due che c'è un modello, serve comunque qualcosa'altro.

[otta96]

Trovare modelli a teorie come ZF è sempre difficile per il secondo teorema di Godel, bisogna farlo necessariamente in na teoria più forte, e anche in quel caso non è una cosa facile.