Relazioni di equivalenza
Ciao, ho un problema.
Si consideri l’insieme A = {1, 2, 3, 4, 5}. Fornire una risposta alla domanda seguente,
motivandola adeguatamente.
• Quante sono le possibili relazioni di equivalenza R su A tali che 1 R 5, 3 R 4 e 5 R/ 4 ?
R/ sta ad indicare R sbarrato.
Il numero delle relazioni di equivalenza è dato da $2^n$ dove n è l'ordine dell'insieme. In questo caso abbiamo quindi 32 relazioni di equivalenza. Come faccio a trovare quei casi? Cosa significano? Grazie in anticipo.
Si consideri l’insieme A = {1, 2, 3, 4, 5}. Fornire una risposta alla domanda seguente,
motivandola adeguatamente.
• Quante sono le possibili relazioni di equivalenza R su A tali che 1 R 5, 3 R 4 e 5 R/ 4 ?
R/ sta ad indicare R sbarrato.
Il numero delle relazioni di equivalenza è dato da $2^n$ dove n è l'ordine dell'insieme. In questo caso abbiamo quindi 32 relazioni di equivalenza. Come faccio a trovare quei casi? Cosa significano? Grazie in anticipo.
Risposte
Quanti sottoinsiemi di un insieme con $k$ elementi ne contengono due di fissati e non ne contengono uno?
Ovviamente poi le relazioni di equivalenza su un insieme di 5 elementi non sono $2^5$, è estremamente più complicato: https://math.stackexchange.com/question ... et-1-2-3-4
Ovviamente poi le relazioni di equivalenza su un insieme di 5 elementi non sono $2^5$, è estremamente più complicato: https://math.stackexchange.com/question ... et-1-2-3-4
Meno male che è arrivata la risposta di @k_b e relativo link, perché mi stavo imbarcando in un'impresa più grande di me 
... Riporto sotto l'inizio solo per far capire che era "molto improbabile" che il numero delle relazioni di equivalenza su un insieme di $n$ elementi fosse "semplicemente" $2^n$...
-----------------------------------------------------------------------------------------------------------------------------------------------------
Se $A$ è un insieme di $n$ elementi, $2^n$ è il numero di elementi dell'insieme delle parti di $A$, $\mathcal{P}(A)$. Il numero di partizioni di $A$ è pari al numero delle unioni disgiunte di elementi di $\mathcal{P}(A)$ che danno $A$. Quindi il numero di partizioni di $A$ si ottiene sottraendo dal numero di unioni che si possono fare con i $2^n$ elementi di $\mathcal{P}(A)$ il numero di quelle a intersezione non vuota e/o che non danno $A$, ecc.
... Riporto sotto l'inizio solo per far capire che era "molto improbabile" che il numero delle relazioni di equivalenza su un insieme di $n$ elementi fosse "semplicemente" $2^n$...-----------------------------------------------------------------------------------------------------------------------------------------------------
Se $A$ è un insieme di $n$ elementi, $2^n$ è il numero di elementi dell'insieme delle parti di $A$, $\mathcal{P}(A)$. Il numero di partizioni di $A$ è pari al numero delle unioni disgiunte di elementi di $\mathcal{P}(A)$ che danno $A$. Quindi il numero di partizioni di $A$ si ottiene sottraendo dal numero di unioni che si possono fare con i $2^n$ elementi di $\mathcal{P}(A)$ il numero di quelle a intersezione non vuota e/o che non danno $A$, ecc.
Scusate ma qui http://www.dmi.unict.it/~lizzio/corso/m ... iemi_l.pdf alla domanda 6 sta scritto chiaramente: le relazioni di equivalenza sono tante quante le possibili partizioni di A.
"knowitall":
Scusate ma qui http://www.dmi.unict.it/~lizzio/corso/m ... iemi_l.pdf alla domanda 6 sta scritto chiaramente: le relazioni di equivalenza sono tante quante le possibili partizioni di A.
Cosa ti fa pensare che le partizioni di un insieme di $n$ elementi siano $2^n$?
Ho cercato online e ho trovato che devo usare i numeri di Bell https://en.wikipedia.org/wiki/Bell_number
Quindi in questo caso l'insieme ha 15 relazioni di equivalenza, giusto?
Quindi in questo caso l'insieme ha 15 relazioni di equivalenza, giusto?
"knowitall":
Ok, puoi dirmi per favore come si calcola il numero di partizioni di un insieme. Sto cercando e non trovo nulla.
Quanto forte vuoi che mi metta a ridere? Dipende da cosa intendi come una risposta soddisfacente: una formula chiusa per il numero di partizioni $p(n)$ di un intero non esiste, esistono solo simpatiche asintotiche come
\[
p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right)
\] (Hardy-Ramanujan 1918).
Per $n=5$, si fa a mano, sono 7.
Non si devono usare i numeri di Bell? https://en.wikipedia.org/wiki/Bell_number
E quindi è 52 in questo caso?
E quindi è 52 in questo caso?
Seh, tombola!
Ti ho detto che le partizioni di un insieme di 5 elementi sono sette.
Ti ho detto che le partizioni di un insieme di 5 elementi sono sette.
No, sono 52 ti sbagli. Vatti a vedere i numeri Bell
Aaah, perché tu vuoi le partizioni di un insieme, non di un intero! Ecco cosa succede a fare gli esercizi agli altri senza ascoltare la consegna 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo