Numero di relazioni di equivalenza in un insieme

Messaggioda Spike32 » 08/01/2019, 17:04

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}$?
Spike32
New Member
New Member
 
Messaggio: 33 di 82
Iscritto il: 07/05/2016, 12:19

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda Martino » 09/01/2019, 08:31

Relazione di equivalenza = partizione. Quindi basta contare le partizioni.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 7327 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda Spike32 » 09/01/2019, 09:19

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?
Spike32
New Member
New Member
 
Messaggio: 34 di 82
Iscritto il: 07/05/2016, 12:19

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda anti-spells » 09/01/2019, 10:36

Direi proprio di no, una partizione deve soddisfare diversi criteri, non basta prendere sottoinsiemi qualsiasi in $P(A)$
anti-spells
Junior Member
Junior Member
 
Messaggio: 41 di 210
Iscritto il: 08/08/2018, 18:20

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda Spike32 » 09/01/2019, 11:51

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"?
Spike32
New Member
New Member
 
Messaggio: 35 di 82
Iscritto il: 07/05/2016, 12:19

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda fmnq » 09/01/2019, 12:10

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.
fmnq
Average Member
Average Member
 
Messaggio: 92 di 764
Iscritto il: 03/10/2017, 23:14

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda Pazzuzu » 12/01/2019, 17:34

"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
Pazzuzu
Average Member
Average Member
 
Messaggio: 267 di 536
Iscritto il: 08/05/2011, 16:29

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda fmnq » 12/01/2019, 18:31

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?
fmnq
Average Member
Average Member
 
Messaggio: 104 di 764
Iscritto il: 03/10/2017, 23:14

Re: Numero di relazioni di equivalenza in un insieme

Messaggioda Pazzuzu » 12/01/2019, 21:50

Sto dicendo che esiste un'espressione in forma chiusa per calcolare l'ennesimo numero di Bell.
Pazzuzu
Average Member
Average Member
 
Messaggio: 268 di 536
Iscritto il: 08/05/2011, 16:29


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite