Problema banale sulle relazioni

[HowardRoark]

Dati i due insiemi $A={a,b,c,d}$ e $B={e,f,g}$, quante relazioni si possono definire tra di essi?
Ovviamente bisogna considerare $|P(A x B)|= 2^12=4096$. Questa è la risposta che dà il libro, però non si dovrebbero considerare anche tutte le relazioni che sono sottoinsiemi di $B x A$? Una relazione del tipo $R: e->a$, cioè l'insieme composto dalla coppia ordinata $(e,a)$, non sta dentro $P(A x B)$, ad esempio...

[DavidGnomo1]

Una relazione $R$ è un qualsiasi sottoinsieme del prodotto cartesiano $A \times B$, presi nell'ordine.
In definitiva $R \subset A \times B$. Va da se che considerare $B \times A$ genera delle relazioni diverse in quanto $A \times B \ne B \times A$ (a meno che $A = B$).

[HowardRoark]

Allora ho ragione a dire che il numero totale di relazioni possibili è $2*2^12$

[DavidGnomo1]

"HowardRoark":Allora ho ragione a dire che il numero totale di relazioni possibili è $2*2^12$

In generale
Siano $A$, $B$ due insieme non vuoti,
$|A| = m$
$|B| = n$
$|A \times B| = mn$
Numero di relazioni $2^{nm}$..

Nel tuo caso
$|A| = 4$
$|B| = 3$
$|A \times B| = 12$
Numero di relzioni $2^12 = 4096$

[DavidGnomo1]

Aggiungo che lui ti sta chiedendo il numero di relazioni da $A$ in $B$ presi nell'ordine scritto.
Tu invece vuoi tener conto anche delle relazioni di $B$ in $A$ che però non è quello che ti chiede.

[HowardRoark]

In realtà non mi sembra che mi chieda soltanto le relazioni da $A$ in $B$ (parla di "quante relazioni si possono definire tra essi"; le relazioni $BxA$ non rientrano in questa conta?), dal testo non si capisce se non dalla risposta che c'è scritta nel libro, ma a questo punto immagino che tu abbia ragione e allora c'è solo un problema di ambiguità del testo.

[DavidGnomo1]

Ti ha dato due insiemi in un certo ordine e ti ha chiesto un sottoinsieme del prodotto cartesiano dove l'ordine è molto importante. Nel senso che, se ti chiede quante relazioni ci possono essere tra $A$ e $B$ va da se che implicitamente si riferisce al loro prodotto cartesiano che, per come abbiamo detto prima, porta a dire che $A \times B \ne B \times A$. Per cui non puoi addizionare il numero di relazioni dei due prodotti cartesiani perchè sono cosi diverse.

[megas_archon]

Del resto \(A\times B\cong B\times A\), tra l'altro naturalmente in $A,B$...

Più nel merito: proprio per questa ragione, il numero delle relazioni tra $A$ e $B$ e il numero delle relazioni tra $B$ e $A$ sono lo stesso numero.

(Dato che una relazione, in quanto sottoinsieme di \(A\times B\cong B\times A\) non ha una vera e propria direzione, io preferisco dire che una relazione è "tra" $A$ e $B$, e non "da" $A$ a $B$, che implicherebbe una direzionalità.)

[HowardRoark]

"megas_archon":

Più nel merito: proprio per questa ragione, il numero delle relazioni tra $A$ e $B$ e il numero delle relazioni tra $B$ e $A$ sono lo stesso numero.

Questo mi era chiaro, ma non capivo se dovessi considerare anche i sottoinsiemi contenuti in $P(B x A)$ per la conta, cosa che ovviamente avrebbe raddoppiato il numero di relazioni totali. A quanto pare no, quindi alla fine il problema era più di ambiguità del testo.

[megas_archon]

Il testo non è ambiguo: tra due insiemi $A,B$ ci sono \(2^{A\times B}\) relazioni; una relazione \(R\subseteq A\times B\) ne identifica univocamente un'altra \(R^{op}\subseteq B\times A\), vedi qui https://www.matematicamente.it/forum/vi ... 5#p8491325 e segg.

[HowardRoark]

Che una relazione $Rsube(A \times B) $ identifica univocamente $R^(op) sube B\timesA$ mi sembra intuitivo, ciò nonostante le relazioni mi sembrano diverse. Faccio un esempio. Prendo $R sube (A \times B) = {(a,e), (a,g), (b,g), (c,f), (d,e) }$; la relazione inversa è ovviamente $R^(op) sube B \times A = {(e,a), (g,a), (g,b), (f,c), (e,d)}$. Queste sono due relazioni, non una, quindi se prendo $|P(A \times B)|$ e $|P(B \times A) |$ le relazioni individuate non dovrebbero essere $2*2^12$?
Studiando da un libro per bambini è difficile rispondere a tutto, però questa mi sembra una cosa terra terra da capire, spero di chiarirla.

[Studente Anonimo]

In pratica stai chiedendo quanto vale

$|P(A xx B) uu P(B xx A)|$ (*)

Non è così immediato, perché gli insiemi $P(A xx B)$ e $P(B xx A)$ non sono disgiunti in generale. Quindi (*) non è necessariamente uguale a $|P(A xx B)|+|P(B xx A)| = 2|P(A xx B)|$.

Osserva che se $X,Y$ sono insiemi, $P(X nn Y)=P(X) nn P(Y)$ ma non vale l'analogo per l'unione. Abbiamo

$|P(X) uu P(Y)|$
$=|P(X)|+|P(Y)|-|P(X) nn P(Y)|$
$=|P(X)|+|P(Y)|-|P(X nn Y)|$

Ora scegli $X=A xx B$ e $Y=B xx A$. Abbiamo $X nn Y=(A nn B) xx (A nn B)$ e quindi $|X nn Y|=|A nn B|^2$.

In questo modo riesci facilmente a calcolare (*). Ovviamente dipenderà non solo da $|A|$ e $|B|$ ma anche da $|A nn B|$.

[HowardRoark]

"Martino":
gli insiemi $P(A xx B)$ e $P(B xx A)$ non sono disgiunti in generale. Quindi (*) non è necessariamente uguale a $|P(A xx B)|+|P(B xx A)| = 2|P(A xx B)|$.

Però nel mio caso sono disgiunti, quindi se ho inteso bene il problema avrei ragione a dire che le relazioni totali sono $2*2^12$ (sicuramente avrò frainteso io, però intanto vorrei capire se il problema è l'ambiguità del testo o una mia lacuna, e da quello che hai scritto si direbbe più la prima, fortunatamente per me).

"Martino":
Osserva che se $X,Y$ sono insiemi, $P(X nn Y)=P(X) nn P(Y)$ ma non vale l'analogo per l'unione. Abbiamo

$|P(X) uu P(Y)|$
$=|P(X)|+|P(Y)|-|P(X) nn P(Y)|$
$=|P(X)|+|P(Y)|-|P(X nn Y)|$

Ora scegli $X=A xx B$ e $Y=B xx A$. Abbiamo $X nn Y=(A nn B) xx (A nn B)$ e quindi $|X nn Y|=|A nn B|^2$.

In questo modo riesci facilmente a calcolare (*). Ovviamente dipenderà non solo da $|A|$ e $|B|$ ma anche da $|A nn B|$.

Il ragionamento lo capisco, ma quale proprietà hai applicato per passare da $(A \times B) nn (B \times A)$ a $(A nn B) \times (A nn B)$?

[Studente Anonimo]

"HowardRoark":Però nel mio caso sono disgiunti, quindi se ho inteso bene il problema avrei ragione a dire che le relazioni totali sono $2*2^12$

Sì hai ragione.

quale proprietà hai applicato per passare da $(A \times B) nn (B \times A)$ a $(A nn B) \times (A nn B)$?

Nessuna proprietà, quei due insiemi sono uguali. Per dimostrarlo basta che pensi alle due inclusioni.

[HowardRoark]

Ok, provo a dimostrare che $(A \times B) nn ( B \times A) sube (A nn B) \times (A nn B)$ e viceversa.

Preso $x$ nell'insieme di sinistra, ho che $x in (A \times B) ^^ x in (B\times A) <=> x in (A nn B)^2 = x in (B nn A)^2$. Non riesco a capire se quella doppia implicazione sia ovvia, probabilmente sì.

[HowardRoark]

Ok ci sono arrivato, bastava ragionare sulla definizione di prodotto cartesiano.
Che bello.