[logica di base]Relazioni su un insieme
Salve a tutti,
Durante l'orale universitario di un mio amico gli hanno fatto la seguente domanda:
"In un insieme di 10 elementi, quante relazioni di simmetria possiamo trovare?"
Lui non ha saputo rispondere, mentre il professore gli disse "1024".
Ora ho notato che quella è la cardinalità dell'insieme delle parti dell'insieme con 10 elementi, ma non capisco il collegamento.
Mi potete aiutare ad arrivarci?
P.S.
Se gli avesse chiesto qualsiasi altra relazione la risposta sarebbe stata la stessa?
Durante l'orale universitario di un mio amico gli hanno fatto la seguente domanda:
"In un insieme di 10 elementi, quante relazioni di simmetria possiamo trovare?"
Lui non ha saputo rispondere, mentre il professore gli disse "1024".
Ora ho notato che quella è la cardinalità dell'insieme delle parti dell'insieme con 10 elementi, ma non capisco il collegamento.
Mi potete aiutare ad arrivarci?
P.S.
Se gli avesse chiesto qualsiasi altra relazione la risposta sarebbe stata la stessa?
Risposte
Vi prego ho bisogno di saperlo, non ho trovato niente sul web e una cosa del genere non ce l'hanno mai spiegata 
Secondo me è sbagliato perché le relazioni su un insieme $X$ sono tutti i sottoinsiemi di $X\times X$.
Quelle simmetriche hanno il vincolo che devono contenere $(x,y)<=>$ contengono $(y,x)$, quindi bisogna scegliere solamente i sottoinsiemi di ${(x,y)|x<=y}$, che sono $2^55$ perché quell'insieme ha $55$ elementi.
Quelle simmetriche hanno il vincolo che devono contenere $(x,y)<=>$ contengono $(y,x)$, quindi bisogna scegliere solamente i sottoinsiemi di ${(x,y)|x<=y}$, che sono $2^55$ perché quell'insieme ha $55$ elementi.
Questa è la terza volta che provo ad inviare una risposta:
Il professore lo ha confermato, poi l'esempio che hai fatto tu è di una relazione antisimmetrica, cioè quella di ordinamento parziale, quindi la tua dimostrazione potrebbe essere sbagliata.
Il professore lo ha confermato, poi l'esempio che hai fatto tu è di una relazione antisimmetrica, cioè quella di ordinamento parziale, quindi la tua dimostrazione potrebbe essere sbagliata.
Ma ha dato spiegazioni il professore di quello che ha detto?
"otta96":
Ma ha dato spiegazioni il professore di quello che ha detto?
No, ha solo dato la risposta e poi ha continuato con le domande, serviva per farci "ragionare", ma visto che nessuno mi ha ancora dato una risposta certa, comincio a dubitare fortemente la validità di questa domanda durante un interrogazione.
Nonostante ciò, è vero che corrisponde a 2^n le relazioni simmetriche possibili, almeno con gli insiemi che arrivano a 5 elementi (sì l'ho verificato), ma non sò come dimostrarlo.
Non sò come arrivarci logicamente ad una conclusione del genere, magari conosci qualcuno che sarebbe in grado di dimostrarlo?
"fmnq":
https://math.stackexchange.com/questions/15108/how-many-symmetric-relations-on-a-finite-set bastava googlare
Ti ringrazio, ma ciò non risolve il mio problema, soprattutto perché si mettono a parlare di matrici, cos'è che in logica non abbiamo fatto, non aiuta il fatto che sia tutto in inglese,.
Ma se ritieni che la loro spiegazione soddisfi la mia domanda, non è che potresti spiegarmelo con le tue parole?
Una relazione simmetrica \(R\) su un insieme \(A\) è un sottoinsieme dell'insieme \(A\times A\). Possiamo scrivere \(R\) cme un'unione disgiunta \(B\cup C\), dove \(B\subset \{(a,a)\mid a\in A\}\) e \(C\subset \{(b,c)\in A\times A\mid b\ne c\}\).
Nota che $B$ può essere un qualsiasi sottoinsieme di \(A\), e ci sono \(2^n\) tali scelte.
Per contare il numero dei possibili sottoinsiemi \(C\), dobbiamo usare il fatto che \(C\) è essa stessa una relazione simmetrica, ossia, se \((b,c)\in C\) allora anche \((c,b)\in C\). Ora, sia \({}[A]^2\) la collezine dei sottoinsiemi di \(A\) con 2 elementi (in particolare, \({}[A]^2\) consiste di sottoinsiemi e non di coppie ordinate). Dato un sottoinsieme \(D\) di \({}[A]^2\), gli possiamo associare un insieme del tipo \(C\) che cerchiamo ponendo \(C=\{(b,c)\mid \{b,c\}\in D\}\). Nota che \(C\) è simmetrica, dal momento che \(\{b,c\}=\{c,b\}\).
Viceversa, ogni \(C\) simmetrica corrisponde a un unico \(D\subseteq[A]^2\) come sopra, nella fattispecie a \(\{\{b,c\}\mid (b,c)\in C\}\). Questo è il motivo per cui in \(C\) ammettiamo solo la presenza di coppie \((b,c)\) con \(b\ne c\), cosicché il \(D\) risultante sia un sottoinsieme di \({}[A]^2\).
Abbiamo così dimostrato che ci sono tanti \(C\) quanti sottoinsiemi \(D\) di \({}[A]^2\). Ma ora, ovviamente, \[\displaystyle |[A]^2|={n\choose 2}=\frac{n(n-1)}2.\]
Facendo la somma dei due risultati, il numero di relazioni binarie simmetriche su un insieme con $n$ elementi è \(2^{n+{n\choose 2}}=2^{{n+1}\choose 2}\) .
PS: Dovresti imparare l'inglese, o perlomeno l'intraprendenza che mi ha portato a copincollare il testo della risposta di Caicedo in Google translate.
PPS: rappresentare le relazioni come matrici è una tecnica elementare, e soprattutto è un modo molto chiaro di risolvere il problema. Pensaci.
Nota che $B$ può essere un qualsiasi sottoinsieme di \(A\), e ci sono \(2^n\) tali scelte.
Per contare il numero dei possibili sottoinsiemi \(C\), dobbiamo usare il fatto che \(C\) è essa stessa una relazione simmetrica, ossia, se \((b,c)\in C\) allora anche \((c,b)\in C\). Ora, sia \({}[A]^2\) la collezine dei sottoinsiemi di \(A\) con 2 elementi (in particolare, \({}[A]^2\) consiste di sottoinsiemi e non di coppie ordinate). Dato un sottoinsieme \(D\) di \({}[A]^2\), gli possiamo associare un insieme del tipo \(C\) che cerchiamo ponendo \(C=\{(b,c)\mid \{b,c\}\in D\}\). Nota che \(C\) è simmetrica, dal momento che \(\{b,c\}=\{c,b\}\).
Viceversa, ogni \(C\) simmetrica corrisponde a un unico \(D\subseteq[A]^2\) come sopra, nella fattispecie a \(\{\{b,c\}\mid (b,c)\in C\}\). Questo è il motivo per cui in \(C\) ammettiamo solo la presenza di coppie \((b,c)\) con \(b\ne c\), cosicché il \(D\) risultante sia un sottoinsieme di \({}[A]^2\).
Abbiamo così dimostrato che ci sono tanti \(C\) quanti sottoinsiemi \(D\) di \({}[A]^2\). Ma ora, ovviamente, \[\displaystyle |[A]^2|={n\choose 2}=\frac{n(n-1)}2.\]
Facendo la somma dei due risultati, il numero di relazioni binarie simmetriche su un insieme con $n$ elementi è \(2^{n+{n\choose 2}}=2^{{n+1}\choose 2}\) .
PS: Dovresti imparare l'inglese, o perlomeno l'intraprendenza che mi ha portato a copincollare il testo della risposta di Caicedo in Google translate.
PPS: rappresentare le relazioni come matrici è una tecnica elementare, e soprattutto è un modo molto chiaro di risolvere il problema. Pensaci.
Apprezzo il fatto che tu ti sia preso la briga di metterlo su google translator per poi copiarlo e incollarlo qua, ma io volevo una tua spiegazione visto che non ho capito nulla delle dimostrazioni di quella risposta.
Le matrici, ribadisco, non le abbiamo fatte, proprio per questo non mi sono state d'aiuto, io non posso arrivare logicamente a qualcosa se non ne ho le conoscenze (magari potresti darmi te una breve spiegazione a riguardo?).
L'inglese lo sò, tant'è che ritengo le mie traduzioni più affidabili di un traduttore universale che non è in grado di capire il contesto del discorso.
Quindi non è che mi faresti il piacere di spiegarmelo a parole tue?
Le matrici, ribadisco, non le abbiamo fatte, proprio per questo non mi sono state d'aiuto, io non posso arrivare logicamente a qualcosa se non ne ho le conoscenze (magari potresti darmi te una breve spiegazione a riguardo?).
L'inglese lo sò, tant'è che ritengo le mie traduzioni più affidabili di un traduttore universale che non è in grado di capire il contesto del discorso.
Quindi non è che mi faresti il piacere di spiegarmelo a parole tue?
"AlexanderSC":
Apprezzo il fatto che tu ti sia preso la briga di metterlo su google translator per poi copiarlo e incollarlo qua, ma io volevo una tua spiegazione visto che non ho capito nulla delle dimostrazioni di quella risposta.
Cosa non ti è chiaro della dimostrazione di sopra? Partiamo da lì.
Le matrici, ribadisco, non le abbiamo fatte, proprio per questo non mi sono state d'aiuto, io non posso arrivare logicamente a qualcosa se non ne ho le conoscenze (magari potresti darmi te una breve spiegazione a riguardo?).
E' piuttosto semplice: se \(R : A \curvearrowright A\) è una relazione, stai rappresentandola come una matrice, i cui ingressi sono coppie di elementi di $A$; al posto $(i,j)$ c'è la coppia $(a_i, a_j)$ per qualche enumerazione $A = \{a_1,...,a_n\}$ degli elementi di $A$. Ora, quante scelte possibili hai, affinché questa matrice sia simmetrica? Facile: devi prendere un sottoinsieme della diagonale, e poi un sottoinsieme della zona sopra la diagonale. Quanti sono i primi? Quanti sono i secondi? Fai la somma.
Questo è esattamente il conto che Caicedo fa senza nominare le matrici (ai fini della soluzione di questo problema, "le matrici" sono rettangoli divisi in caselle, dentro le quali sono stati messi dei simboli presi da un alfabeto arbitrario, non serve "avere fatto le matrici" per disegnarne una e guardarci dentro.)
L'inglese lo sò, tant'è che ritengo le mie traduzioni più affidabili di un traduttore universale che non è in grado di capire il contesto del discorso.Se non ti mancano delle conoscenze linguistiche, te ne mancano di matematiche, ma la dimostrazione di Caicedo è elementare nel senso tecnico del termine, quindi non mi capacito tu non l'abbia compresa; forse ti sfugge qualcosa di ancor più elementare? Forse non sto capendo la domanda?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo