Numero di relazioni antisimmetriche

[FE7]

Ho il seguente esercizio.
Sia A un insieme con $ |A| = n $ . Quante sono le relazioni antisimmetriche su A?
Sul libro la soluzione è $ 2^n*3^((n^2-n)/2) $ .

Infatti, innanzitutto ogni relazione formata da elementi esclusivamente del tipo $ (x,x) $ ( es: $ R={(a,a) (c,c)} $ su $ A={a,b,c} $ ) è antisimmetrica. Tra le relazioni formate esclusivamente da elementi di tipo $ (x,y) $ ,con $ x != y $ , invece affinché siano antisimmetriche deve verificarsi una delle tra possibilità: 1) sia presente $ (x,y) $ ma non $ (y,x) $ 2) viceversa 3) non siano presenti nessuna delle due. Dal momento che il numero di elementi di $ A^2 $ è $ n^2 $ e che il numero di elementi di tipo $ (x,x) $ in $ A^2 $ è $ n $ allora si ha che le coppie di tipo $ (x,y) $ sono $ n^2 - n $ e le coppie di coppie $ ( (x,y) ; (y,x) ) $ sono $ (n^2 - n)/2 $. Da ciò segue che le relazioni antisimmetriche ottenibili dalle coppie di tipo $ ( (x,y) ; (y,x) ) $ siano $ 3^((n^2-n)/2) $ ( tre scelte per ciascuna coppia) che vanno moltiplicate per il numero di relazioni ottenibili con elementi di tipo $ (x,x) $ cioè $ 2^n $. Da ciò si ha: $ 2^n*3^((n^2-n)/2) $

.
La mia soluzione appare diversa da quella del libro. Le due coincidono per $ n=1 $ e $ n=2 $ ma poi già per $ n=3 $ non coincidono. Do la mia soluzione nella speranza di capire perché la mia è sbagliata.

Innanzitutto parto dall'osservazione (sbagliata?) che ogni relazione su $ A $ è antisimmetrica o simmetrica o entrambe.
Nessuna relazione può non essere né simmetrica né antisimmetrica. Infatti, ogni relazione non simmetrica è antisimmetrica e ogni relazione non antisimmetrica è simmetrica.
Le relazioni che sono sia simmetriche che antisimmetriche sono tutte e sole le relazioni i cui elementi sono di tipo $ (x,x) $ .
Dunque dal momento che: {relazioni su A}= {simmetriche} $ uu $ {antisimmetriche} avrò:
numero relazioni antisimmetriche = numero relazioni totali - numero simmetriche + intersezione tra simm. e antisimm. (cioè quelle i cui elementi siano solo di tipo $ (x,x) $ ).
Le relazioni totali sono tutti i sottoinsiemi di $ A^2 $ quindi $ 2^(n^2) $ . Le relazioni simmetriche sono invece $ 2^n*2^((n^2-n)/2) $ ( era un esercizio precedente). Il numero di relazioni ottenibili con elementi di tipo $ (x,x) $ è $ 2^n $ .
La mia soluzione è quindi $ 2^(n^2)+2^n*2^((n^2-n)/2)-2^n $ .
Dove sbaglio secondo voi?

[FE7]

Dai ragazzi datemi una mano

[Studente Anonimo]

Beh ci sono relazioni che non sono né simmetriche né antisimmetriche. Per lo stesso motivo ci sono matrici che non sono simmetriche e non sono antisimmetriche: basta scegliere due elementi [tex]a,b[/tex] distinti e decidere che [tex]a[/tex] è in relazione con [tex]b[/tex] e [tex]b[/tex] non è in relazione con [tex]a[/tex], poi sceglierne altri due [tex]c,d[/tex] distinti e decidere che sono in relazione nei due sensi.

Considera per esempio la relazione [tex]\rho[/tex] sull'insieme dei sottoinsiemi di un insieme finito [tex]X[/tex] definita da [tex]U \rho V[/tex] se e solo se [tex]|U| \leq |V|[/tex]. Questa ovviamente, escluso il caso in cui [tex]X[/tex] è vuoto o ha un solo elemento, non è simmetrica perché può succedere che sia [tex]|U| < |V|[/tex], e non è nemmeno antisimmetrica perché da [tex]|U| = |V|[/tex] non segue necessariamente [tex]U = V[/tex].

Se ne possono costruire altre partendo da un insieme [tex]A[/tex] e una particolare funzione [tex]f:A \to \mathbb{R}[/tex] e definendo la relazione [tex]\rho[/tex] su [tex]A[/tex] ponendo per [tex]x,y \in A[/tex], [tex]x \rho y[/tex] se e solo se [tex]f(x) \leq f(y)[/tex]. Questa relazione è sempre riflessiva, transitiva e pure totale (essendo [tex]\leq[/tex] riflessiva, transitiva e totale in [tex]\mathbb{R}[/tex]), ma non è simmetrica non appena [tex]f[/tex] assume più di un valore e non è antisimmetrica non appena [tex]f[/tex] non è iniettiva. Nel caso sopra ho scelto come [tex]A[/tex] parti di [tex]X[/tex] e come [tex]f[/tex] la funzione che assegna ad un insieme la sua cardinalità.

Più in generale data una funzione [tex]f:A \to B[/tex] se ho una relazione [tex]\rho[/tex] su [tex]B[/tex] posso definire una relazione [tex]\rho_f[/tex] su [tex]A[/tex] ponendo [tex]x \rho_f y[/tex] se e solo se [tex]f(x) \rho f(y)[/tex]. La corrispondenza [tex]\rho \mapsto \rho_f[/tex] preserva la riflessività, la transitività e la totalità ma come visto in generale non preserva la simmetria e l'antisimmetria. Preserva l'antisimmetria se e solo se preserva la simmetria, se e solo se [tex]f[/tex] è iniettiva. Inoltre per esempio è ben noto che ogni relazione di equivalenza è del tipo [tex]=_f[/tex] - dove la funzione [tex]f[/tex] è quella che associa un elemento alla sua classe di equivalenza. Quindi l'uguaglianza è in questo senso la relazione di equivalenza "archetipica" non mi sono mai chiesto qual è la relazione d'ordine archetipica. Sì, mi sono dilungato troppo.