Numero di relazioni di equivalenza in un insieme
Inviato:
08/01/2019, 17:04
da Spike32
Ciao a tutti, sto riproponendo questo argomento probabilmente già trattato in questo forum, ma sto effettuando ricerche sia qui e sia altrove e non riesco proprio a venirne a capo, neanche sul libro da dove sto studiando riporta queste informazioni. Come si fa a stabilire quante relazioni di equivalenza è possibile definire in un insieme?
Ad esempio su un insieme molto semplice come $S = {1, a, 3}$?
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
09/01/2019, 08:31
da Martino
Relazione di equivalenza = partizione. Quindi basta contare le partizioni.
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
09/01/2019, 09:19
da Spike32
Martino ha scritto:Relazione di equivalenza = partizione. Quindi basta contare le partizioni.
Se $S$ è un insieme finito con $|S|=n$ elementi, allora l'insieme delle parti di $S$ contiene $|P(S)|=2^n$ sottoinsiemi.
Quindi in ogni caso per trovare il numero di relazioni di equivalenza basta elevare 2 alla cardinalità dell'insieme?
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
09/01/2019, 10:36
da anti-spells
Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
09/01/2019, 11:51
da Spike32
anti-spells ha scritto:Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
Giusto giusto non ci avevo pensato. Quindi c'è un modo per calcolare il numero di partizioni di un insieme o bisogna procedere "a mano"?
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
09/01/2019, 12:10
da fmnq
Spike32 ha scritto:anti-spells ha scritto:Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
Giusto giusto non ci avevo pensato. Quindi c'è un modo per calcolare il numero di partizioni di un insieme o bisogna procedere "a mano"?
Notoriamente non c'è una formula chiusa per faro; puoi trovare delle relazioni di ricorrenza che ti permettono di implementare degli algoritmi relativamente efficaci che calcolino le partizioni di un intero dato, ma sono comunque molto dispendiose.
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
12/01/2019, 17:34
da Pazzuzu
"Notoriamente non c'è una formula chiusa per faro; puoi trovare delle relazioni di ricorrenza che ti permettono di implementare degli algoritmi relativamente efficaci che calcolino le partizioni di un intero dato, ma sono comunque molto dispendiose.".
Direi che invece c'è :
https://en.wikipedia.org/wiki/Bell_number
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
12/01/2019, 18:31
da fmnq
Pazzuzu ha scritto:"Notoriamente non c'è una formula chiusa per faro; puoi trovare delle relazioni di ricorrenza che ti permettono di implementare degli algoritmi relativamente efficaci che calcolino le partizioni di un intero dato, ma sono comunque molto dispendiose.".
Direi che invece c'è :
https://en.wikipedia.org/wiki/Bell_number
Cioè esiste una funzione $f : NN \to NN$, possibilmente ricorsiva, il cui valore in $n$ non dipenda da \(\{f(k)\mid k < n\}\), che permette di esprimere l'$n$-esimo numero di Bell?
Re: Numero di relazioni di equivalenza in un insieme
Inviato:
12/01/2019, 21:50
da Pazzuzu
Sto dicendo che esiste un'espressione in forma chiusa per calcolare l'ennesimo numero di Bell.