[logica di base]Relazioni su un insieme

[AlexanderSC]

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?

[AlexanderSC]

Vi prego ho bisogno di saperlo, non ho trovato niente sul web e una cosa del genere non ce l'hanno mai spiegata

[otta96]

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.

[AlexanderSC]

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.

[otta96]

Ma ha dato spiegazioni il professore di quello che ha detto?

[fmnq]

https://math.stackexchange.com/question ... finite-set bastava googlare

[AlexanderSC]

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?

[AlexanderSC]

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?

[fmnq]

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.

[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.

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?