Quante topologie
Voglio proporre un quesito di cui non conosco la risposta (purtroppo non sono granche' come combinatorista): dato un insieme finito $S$, quante topologie si possono definire su $S$?
Risposte
Se n è il numero di elementi di s allora ne hai esattamente
$2^n$
cioè la somma dei coefficienti binomiali n su k con k che va da 0 a n e che ancora non riesco a scrivere con questo mathML
$2^n$
cioè la somma dei coefficienti binomiali n su k con k che va da 0 a n e che ancora non riesco a scrivere con questo mathML
Alex non credo proprio...$2^n$ indica il numero di sottoinsiemi di un dato insieme di cardinalità $n$. Sul numero di topologie definibili su un insieme $S$ la questione è più complicata e per quanto ne so, a tutt'oggi, non esiste una formula che permetta di determinare il numero di topologie.
Saluti, Ermanno.
Saluti, Ermanno.
Grazie Nidhogg!
Effettivamente $2^n$ è sbagliato, stavo pensando che nel caso degli insiemi finiti, però ogni topologia è un sottoinsieme dell'insieme delle parti e che essendo S necessariamente discreto, queste devono coincidere con i sottoinsieme dell'insieme delle parti P(S), cioè P(P(S)), quindi la cardinalità dovrebbe essere $2^(2^n)$.
Ci penso ancora un po' e proverò a dimostrarlo per induzione.
Effettivamente $2^n$ è sbagliato, stavo pensando che nel caso degli insiemi finiti, però ogni topologia è un sottoinsieme dell'insieme delle parti e che essendo S necessariamente discreto, queste devono coincidere con i sottoinsieme dell'insieme delle parti P(S), cioè P(P(S)), quindi la cardinalità dovrebbe essere $2^(2^n)$.
Ci penso ancora un po' e proverò a dimostrarlo per induzione.
Ci ho ripensato un po' su e era giusta la prima delle mie ipotesi e adesso lo dimostro: 
Se S è un insieme di n elementi allora è in corrispondenza biunivoca con $S_n$={1,2,...,n}, quindi non è limitativo fare gli esempi su questo insieme campione.
Indichiamo con $Omega_0$={$Phi$,$S_n$} e $Omega_n=P(S_n)$ le topologie banali ($P(S_n)$ e l'insieme delle parti di $S_n$).
Notiamo che in analisi combinatoria $Omega_0$ coincide col l'evento di non fare nessuna scelta sugli elementi di $S_n$, ovvero $((n),(0))$ possibilità di scelte, mentre $Omega_n$ coincide con il fare n scelte tra gli elementi di $S_n$, ovvero $((n),(n))$ possibilità di scelta.
Andiamo adesso a considerare le topologie che contengono un singolo elemento di $S_n$, le indichiamo con $Omega_(i,1)$, allora avremo
$Omega_(1,1)${$Phi$,{1},$S_n$}
$Omega_(2,1)${$Phi$,{2},$S_n$}
...
e così via per un totale di $((n),(1))$=n scelte
In maniera analoga posso definire le topologie prese con due elementi di $S_n$
$Omega_((1,2),2)${$Phi$,{1},{2},{1,2},$S_n$}
$Omega_((1,3),2)${$Phi$,{1},{3},{1,3},$S_n$}
...
e con un semplice ragionamento di combinatoria queste sono $((n),(2))$.
Senza scomodare il principio di induzione è paalese che se prendo le topologie composte con 3 queste saranno $((n),(3))$, quelle con 4 saranno $((n),(4))$ e così via fino a n-1 che saranno $((n),(n-1))$ (il caso n è una topologia banale che abbiamo già visto).
Quindi il numero delle topologie che ho costruito è esattamente
$sum_{k=0}^n ((n),(k))
che se la memoria non mi inganna
da $2^n$ (e qui potrebbe essere) come avevo detto all'inizio.
Resta da dimostrare che ho costruito tutte le topologie possibili. Questo appare evidente se consideriamo che $S_n$ ha soltanto n elementi, è ho costruito tutte le possibili combinazioni fatte con 0,1,..., n elementi (risultato di combinatoria) e dall'assioma dei cassetti (uno dei tanti assiomi che definiscono l'infinito, in questo caso per negazione di cio che è finito): se ho un numero a di cassetti (o contenitori) e a+1 oggetti in almeno un cassetto ci saranno 2 oggetti. Se qualcuno provasse aprendere una combinazione di n oggetti inevitabilmente finirebbe per trovare una combinazione che ho già usato. CVD:finga:
L'errore che ho commesso nel precedente topic stava proprio nel fatto che prendessi tutti gli elementi di $P(P(S_n))$ senza considerare che alcuni di questi non formavano topologie
, mentre era giusto il ragionamento che avevo abbozzato nella prima risposta ma che non avevo completato. 
Mi resta ancora un commento da fare. Per concludere la dimostrazione ho usato lk'assioma dei cassetti che funziona con gli insiemi finiti, e per questo motivo tale dimostrazione non vale per gli insiemi infiniti, anche se sono convinto che usando il buon ordinamento possa essere estesa al solo insieme $NN$. Se qualcun'altro si vuole cimentare sarò lieto di complimentarnmi con lui nel caso di riuscita.
Se S è un insieme di n elementi allora è in corrispondenza biunivoca con $S_n$={1,2,...,n}, quindi non è limitativo fare gli esempi su questo insieme campione.
Indichiamo con $Omega_0$={$Phi$,$S_n$} e $Omega_n=P(S_n)$ le topologie banali ($P(S_n)$ e l'insieme delle parti di $S_n$).
Notiamo che in analisi combinatoria $Omega_0$ coincide col l'evento di non fare nessuna scelta sugli elementi di $S_n$, ovvero $((n),(0))$ possibilità di scelte, mentre $Omega_n$ coincide con il fare n scelte tra gli elementi di $S_n$, ovvero $((n),(n))$ possibilità di scelta.
Andiamo adesso a considerare le topologie che contengono un singolo elemento di $S_n$, le indichiamo con $Omega_(i,1)$, allora avremo
$Omega_(1,1)${$Phi$,{1},$S_n$}
$Omega_(2,1)${$Phi$,{2},$S_n$}
...
e così via per un totale di $((n),(1))$=n scelte
In maniera analoga posso definire le topologie prese con due elementi di $S_n$
$Omega_((1,2),2)${$Phi$,{1},{2},{1,2},$S_n$}
$Omega_((1,3),2)${$Phi$,{1},{3},{1,3},$S_n$}
...
e con un semplice ragionamento di combinatoria queste sono $((n),(2))$.
Senza scomodare il principio di induzione è paalese che se prendo le topologie composte con 3 queste saranno $((n),(3))$, quelle con 4 saranno $((n),(4))$ e così via fino a n-1 che saranno $((n),(n-1))$ (il caso n è una topologia banale che abbiamo già visto).
Quindi il numero delle topologie che ho costruito è esattamente
$sum_{k=0}^n ((n),(k))
che se la memoria non mi inganna
da $2^n$ (e qui potrebbe essere) come avevo detto all'inizio.Resta da dimostrare che ho costruito tutte le topologie possibili. Questo appare evidente se consideriamo che $S_n$ ha soltanto n elementi, è ho costruito tutte le possibili combinazioni fatte con 0,1,..., n elementi (risultato di combinatoria) e dall'assioma dei cassetti (uno dei tanti assiomi che definiscono l'infinito, in questo caso per negazione di cio che è finito): se ho un numero a di cassetti (o contenitori) e a+1 oggetti in almeno un cassetto ci saranno 2 oggetti. Se qualcuno provasse aprendere una combinazione di n oggetti inevitabilmente finirebbe per trovare una combinazione che ho già usato. CVD:finga:
L'errore che ho commesso nel precedente topic stava proprio nel fatto che prendessi tutti gli elementi di $P(P(S_n))$ senza considerare che alcuni di questi non formavano topologie
, mentre era giusto il ragionamento che avevo abbozzato nella prima risposta ma che non avevo completato. Mi resta ancora un commento da fare. Per concludere la dimostrazione ho usato lk'assioma dei cassetti che funziona con gli insiemi finiti, e per questo motivo tale dimostrazione non vale per gli insiemi infiniti, anche se sono convinto che usando il buon ordinamento possa essere estesa al solo insieme $NN$. Se qualcun'altro si vuole cimentare sarò lieto di complimentarnmi con lui nel caso di riuscita.
Prova a contare le topologie sull'insieme ${1,2,3}$. Vedrai che non sono $2^3$, ma di più.
S={1, 2, 3}
$U_0={Phi, S}$
$U_1,1={Phi, {1}, S}$
$U_2,1={Phi, {2}, S}$
$U_3,1={Phi, {3}, S}$
$U_12,2={Phi, {1}, {2}, {1, 2}, S}$
$U_13,2={Phi, {1}, {3}, {1, 3}, S}$
$U_23,2={Phi, {2}, {3}, {2, 3}, S}$
$U_3={Phi, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}=S}$
sono 8 cioè $2^3$ e non riesco a trovarne altre; scusa fields mi dici tu quali sono?
$U_0={Phi, S}$
$U_1,1={Phi, {1}, S}$
$U_2,1={Phi, {2}, S}$
$U_3,1={Phi, {3}, S}$
$U_12,2={Phi, {1}, {2}, {1, 2}, S}$
$U_13,2={Phi, {1}, {3}, {1, 3}, S}$
$U_23,2={Phi, {2}, {3}, {2, 3}, S}$
$U_3={Phi, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}=S}$
sono 8 cioè $2^3$ e non riesco a trovarne altre; scusa fields mi dici tu quali sono?
Per esempio {Φ,{1},{2},{1,2},{1,3},S} mi sembra un'altra topologia...
Ci sono anche queste
${Phi, {1, 2}, S}$
${Phi, {1, 3}, S}$
${Phi, {2, 3}, S}$
e ancora altre..
${Phi, {1, 2}, S}$
${Phi, {1, 3}, S}$
${Phi, {2, 3}, S}$
e ancora altre..
Mea culpa, mea culpa, mea massima culpa:prayer: Di notte si lavora al fresco ma la soglia di attenzione è bassa:
dopo io stesso ho trovato queste altre 3
{$Phi$, {1}, {2, 3}, S}
{$Phi$, {2}, {1, 3}, S}
{$Phi$, {3}, {1, 2}, S}
ma ero stranamente convinto che l'intersezione le eliminasse. Sono comunque convinto che debba esistere una formula, cercherò ancora di trovarla facendo più attenzione stavolta.
Secondo me il problema e' molto piu' difficile di quanto potrebbe sembrare a prima vista.
"temo" che Sandokan abbia ragione.
Indizi in merito sono:
http://links.jstor.org/sici?sici=0002-9 ... nlargePage
http://www.cs.uwaterloo.ca/journals/JIS ... ani11.html
o, volendo, direttamente all'articolo (in pdf):
http://www.cs.uwaterloo.ca/journals/JIS ... hani11.pdf
Indizi in merito sono:
http://links.jstor.org/sici?sici=0002-9 ... nlargePage
http://www.cs.uwaterloo.ca/journals/JIS ... ani11.html
o, volendo, direttamente all'articolo (in pdf):
http://www.cs.uwaterloo.ca/journals/JIS ... hani11.pdf
Anche qui viene spiegato quanto sia difficile e intrattabile questo problema. E' interessante il fatto che si riduca alla seguente equivalente questione: quanti ordini parziali si possono definire su un insieme finito?
Ringrazio Fioravante e TomSawyer per i riferimenti indicati. Non credevo comunque che il problema fosse difficile cosi' tanto!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo