Numero di relazioni riflessive su un insieme A, con card(A)=n
Siccome non ero capace di risolvere l'esercizio, ho guardato la soluzione, e sinceramente mi lascia non poco perplesso.
Se qualcuno fosse così gentile da spiegarmi.
Allora la soluzione è la seguente:
i)Le relazioni riflessive su un insieme $ A $ sono quelle che contengono tutte le coppie $ (x,x) $ tali che $ x in A $.
Ed ecco che arriva il punto che non capisco:
ii) le relazioni riflessive sono quindi tante quante i sottoinsiemi dell'insieme $ A^2 - {(x,x): x in A} $ .
iii) poichè $ |{(x,x): x in A} |=n $ e $ | A^2 - {(x,x): x in A} | = n^2 - n $ allora le relazioni riflessive sono $ 2^(n^2-n)$.
Il punto ii) non l'ho capito assolutamente. Quell'insieme mi sembra che sia l'insieme di tutti gli $(x,y)$ tali che $ x!= y $ quindi non capisco il motivo di contare i suoi sottoinsiemi per trovare il numero di relazioni riflessive.
Grazie
Se qualcuno fosse così gentile da spiegarmi.
Allora la soluzione è la seguente:
i)Le relazioni riflessive su un insieme $ A $ sono quelle che contengono tutte le coppie $ (x,x) $ tali che $ x in A $.
Ed ecco che arriva il punto che non capisco:
ii) le relazioni riflessive sono quindi tante quante i sottoinsiemi dell'insieme $ A^2 - {(x,x): x in A} $ .
iii) poichè $ |{(x,x): x in A} |=n $ e $ | A^2 - {(x,x): x in A} | = n^2 - n $ allora le relazioni riflessive sono $ 2^(n^2-n)$.
Il punto ii) non l'ho capito assolutamente. Quell'insieme mi sembra che sia l'insieme di tutti gli $(x,y)$ tali che $ x!= y $ quindi non capisco il motivo di contare i suoi sottoinsiemi per trovare il numero di relazioni riflessive.
Grazie
Risposte
Devi contare i sottoinsiemi di [tex]A^2[/tex] che contengono [tex]D=\{(x,x)\ :\ x \in A\}[/tex]. Essi sono ovviamente in biiezione coi sottoinsiemi di [tex]A^2-D[/tex], quindi conti quelli. Un altro modo di dirlo: ogni sottoinsieme di [tex]A^2[/tex] che contiene [tex]D[/tex] e' del tipo [tex]U \cup D[/tex] con [tex]U[/tex] un sottoinsieme di [tex]A^2[/tex] disgiunto da [tex]D[/tex]. Quindi i sottoinsiemi di [tex]A^2[/tex] che contengono [tex]D[/tex] sono tanti quanti i sottoinsiemi di [tex]A^2[/tex] disgiunti da [tex]D[/tex].
Giusto! ti ringrazio la seconda risposta mi ha chiarito.