(DIM) Corrispondenza opposta

maurioz
Stavo provando ad approfondire i concetti di corrispondenza e ho appreso la definizione di corrispondenza opposta. Nel libro tuttavia da perscontato che data una corrispondenza (come sottoinsieme di un prodotto cartesiano) ne esista l'opposta.

Definendo come $R_(op):={(b,a) in BxxA:(a,b) in R}$, con R corrispondenza, mi chiedo come dimostrare che esista sempre R_op.

Ad occhio è abbastanza ovvio nel senso che l'opposta fa parte del prodotto cartesiano commutato e ragionando sul fatto che in una dupla ho solo due posizioni/slot posso scambiare l'ordine delle due ottenendo la dupla commutata.

Però mi incespico sempre in questi concetti che non capisco se vadano dimostrati o meno. E' talmente banale che non saprei da dove partire.

Vi ringrazio :)

Risposte
fulcanelli
Esiste una biiezione \(\sigma\) tra \(P(A\times B)\) e \(P(B\times A)\), indotta da una biiezione \(A\times B \cong B\times A\) (ne esiste solo una di canonica, in un senso preciso che però non ti importa).

Data $R$, la relazione opposta \(R^\text{op}\) è l'immagine di \(R\in P(A\times B)\) tramite \(\sigma\). Questo identifica univocamente $R$, perché \(\sigma\) è biiettiva.

Dimostra il primo fatto, il secondo è una definizione.

maurioz
Sono molto alle basi-basi e vorre chiederti alcuni chiarimenti sul consiglio che mi hai proposto

ne esiste solo una di canonica

vorei chiederti in primis cosa si intende in questo caso per canonica e perché sia unica, non ho ben capito.


Poi vorrei provare a ragionare sul consiglio perché nonostante abbia gli elementi non ho idea di come procedere.

Insomma abbiamo l'insieme delle parti
$P(AxxB)={S⊆(AxxB)}$ cioè l'insieme dei sottoinsiemi del prodotto cartesiano
e
$P(BxxA)={S⊆(BxxA)}$

la biiezione su questi è indotta da una biiezione sul prodotto cartesiano, però per definizione una biiezione è

$∀(b,a)∈(BxxA),∃!(a,b)∈(AxxB)t.c$ gli elementi appartengano alla relazione binaria (chiamo R) ossia
$∀(b,a)∈(BxxA),∃!(a,b)∈(AxxB)|((a,b) ; (b,a))inR$? Ma da questo come mi districo, credo di aver preso una strata sbagliata :lol:

Grazie per il tuo aiuto :)

G.D.5
Da quello che mi sembra di capire siamo ai livelli iniziali di una tradizionale teoria degli insiemi, magari trattata anche in modo ingenuo, quindi, domanda: come è possibile usare le biiezioni prima ancora di avere a disposizione anche solo le funzioni?

maurioz
Certo, mi sono chiesto la stessa cosa (dato che un concetto discende dall'altro in ordine logico), ma dato che "conosco" già la parte successiva ho pensato comunque di seguire il consiglio per mera curiosità e vedere dove potevo arrivare.

Ad ogni modo sì, sto leggendo un libro di algebra base e la domanda iniziale rimane :lol: .

fulcanelli
Definisci \(s : A \times B \to B\times A\) mandando l'elemento \((a,b)\) in \((b,a)\); questa funzione è biiettiva.

Ora, un sottoinsieme \(U\in P(A\times B)\) si identifica a una e una sola funzione \(\chi_U : A\times B \to \{0,1\}\), che vale 1 su \((a,b)\) se e solo se \((a,b)\in U\).

Questa funzione si chiama la "funzione caratteristica" di \(U\). Avendo \(U\), e quindi \(\chi_U\), puoi precomporre \(\chi_U\) con \(s\), ottenendo una funzione \(\chi_U \circ s^{-1} : B\times A \to \{0,1\}\) la quale identifica uno e un solo sottoinsieme di \(B\times A\), chiamiamolo \(U'\).

Questo è il corrispondente di \(U\) in una biiezione \(P(A\times B) \cong \hom(A\times B, \{0,1\}) \to \hom(B\times A, \{0,1\})\cong P(B\times A)\).

Il sottoinsieme di funzione caratteristica \(\chi_U \circ s^{-1}\) è determinato esattamente come quel sottoinsieme \(U'\in P(B\times A)\) tale che \((b,a) \in U'\) se e solo se \((a,b)\in U\), se e solo se \(\chi_U(a,b)=1\).

Interpretando \(U\) come una relazione da A a B, \(U'\) è una relazione da B ad A, la relazione "opposta" di quella determinata da \(U\).

G.D.5
@fulcanelli

Non ti sembra di stare sparando ad una mosca con un cannone?

fulcanelli
No, è un ragionamento completamente elementare, e un ottimo pretesto per imparare la definizione di funzione e di biiezione.
Certamente il livello del mio interlocutore non è un mio problema. Se ha altre domande, come vedi, gli rispondo.

Quindi: ci sono altre domande?

maurioz
Ci sto ragionando un po' perché molti concetti non li conoscevo.

In primo lugo credo di non capire $χ_U∘s$ non mi torna il dominio di composizione.

EDIT: mi sono accorto che nella nuova riedizione c'è l' $s^-1$ ok questo primo punto ci sono.

Passando alla seconda parte:
Questo è il corrispondente di \(U\) in una biiezione \(P(A\times B) \cong \hom(A\times B, \{0,1\}) \to \hom(B\times A, \{0,1\})\cong P(B\times A)\).


Credo mi sfugga questa nomenclatura. Non credo di conoscere "hom()" ad esempio..

G.D.5
Ti rendi conto che nella teoria degli insiemi il concetto di funzione e quello di funzione biiettiva vengono parecchio dopo la definizione di corrispondenza?
Secondo il tuo approccio, si inizia con la definizione di corrispondenza, si passa a quella di funzione, di funzione biiettiva, di composizione delle funzioni e poi si torna indietro per giustificare una banalità come la corrispondenza opposta (o inversa) che si giustifica semplicemente con gli assiomi di ZFC. Ti pare una cosa elementare?
Senza trascurare il fatto che hai introdotto notazioni quali \( \cong \) e \( \hom \).
Sia chiaro: non sto dicendo che non va bene o che non è elegante, anzi. Sto solo dicendo che se una persona sta studiando seguendo un determinato percorso, quello che proponi tu è un extra, una via alternativa, certamente più raffinata ed elegante, ma non gli è utile per capire dove va a parare il testo o l'insegnate che sta seguendo. Tutto qua.

maurioz
"G.D.":
che si giustifica semplicemente con gli assiomi di ZFC. Ti pare una cosa elementare?


Però sul libro non l'ho trovato ad inizio, potrei chiederti una lettura per giustificare l'esistenza della corrispondenza opposta?

G.D.5
In ogni caso, seguendo un approccio più rozzo ma più in linea con quello che è il percorso di un testo base di algebra, che si basa su una versione più o meno ingenua di ZFC, la spiegazione è semplice: se puoi fare \( A \times B \), allora puoi fare anche \( B \times A \); la corrispondenza \( R_{op} \) è definita come un sottoinsieme di \( B \times A \), quindi, esistendo \( B \times A \), esiste anche \( R_{op} \). Inoltre la proprietà che definisce \( R_{op} \) come sottoinsieme di \( B \times A \), vale a dire la proprietà \( (a,b) \in A \times B \), è una proprietà che non crea problemi o ambiguità perché se \( (b,a) \in B \times A \), allora \( b \in B \) e \( a \in A \), sicché \( (a,b) \in A \times B \) e, per definizione, \( R \subseteq A \times B \).
Poi ovviamente enucleando gli assiomi di ZFC in modo corretto e completo si può fare vedere quanto sopra in modalità "pelo e contropelo" ma occorre partire dalla costruzione di \( A \times B \) come sottoinsieme di \( \mathcal{P} ( \mathcal{P} ( A \cup B ) ) \). Se ti va puoi consultare un qualunque testo di teoria ZFC, come il Jech, oppure puoi consultare qualcosa come le dispense del Prof. Degiovanni dell'Università Cattolica del Sacro Cuore di Brescia su Logica e Teoria degli Insiemi.

Edit.
Il motivo per il quale non hai trovato agli inizi del tuo testo l'assiomatica ZFC è che in un testo base di Algebra di parte con una versione molto ingenua della teoria degli insiemi, versione ingenua che può spaziare dal dare le nozioni sugli insiemi nel modo meno formale possibile, aggiustando il tiro con degli avvertimenti specifici quando l'autore sa che potrebbero nascere paradossi, al dare le nozioni sugli insiemi in una versione semplificata dell'assiomatica ZFC come in Halmos, Naive Set Theory.

maurioz
Grazie mille, gentilissimo anche per le letture :)

G.D.5
Aggiungo una osservazione.

La mia risposta risponde strettamente alla domanda iniziale, ovvero: data \( R \), cosa ci assicura che esiste sempre \( R_{op} \)?

Se invece la domanda fosse stata del tipo: come mostriamo che \( R \) e \( R_{op} \) hanno lo stesso numero di elementi? O ancora: come mostro che \( R \) e \( R_{op} \) si "sovrappongono"? In questi casi bisogna prima andare avanti e recuperare concetti quali quello di funzione e poi tornare indietro, passando per una risposta come quella di fulcanelli, la mia non è più sufficiente. Il che si ricollega a quanto dicevo prima: la risposta di fulcanelli non è ovviamente sbagliata, è che per chi si trova alle prime pagine di un testo base di Algebra che per giunta mette giù un'assiomatica molto ingenua di ZFC, è sovrabbondante. Tutto qua.

maurioz
Certo, infatti vorrei capire a fondo anche la sua risposta. PErché in realtà ho già letto i concetti dopo (più di metà libro) e ho cominciato una seconda lettura per capire meglio (solo una prima lettura noto che non mi basta capendo dopo alcune cose lette prima). Tuttavia come avevo quotato nel mio messaggio a pag. precedente mi sfuggono alcuni concetti. Se qualcuno avesse voglai di rispondere, già che siamo in argomento leggo volentieri :D

PS: la parte dubbia è questa
Questo è il corrispondente di \(U\) in una biiezione \(P(A\times B) \cong \hom(A\times B, \{0,1\}) \to \hom(B\times A, \{0,1\})\cong P(B\times A)\).

Il sottoinsieme di funzione caratteristica \(\chi_U \circ s^{-1}\) è determinato esattamente come quel sottoinsieme \(U'\in P(B\times A)\) tale che \((b,a) \in U'\) se e solo se \((a,b)\in U\), se e solo se \(\chi_U(a,b)=1\).

Interpretando \(U\) come una relazione da A a B, \(U'\) è una relazione da B ad A, la relazione "opposta" di quella determinata da \(U\).


Mi risulta un poco ostica, ad esempio non so bene cosa sia hom().

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.