Pagina 1 di 1

Numero di relazioni di equivalenza in un insieme

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 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

MessaggioInviato: 12/01/2019, 21:50
da Pazzuzu
Sto dicendo che esiste un'espressione in forma chiusa per calcolare l'ennesimo numero di Bell.