Il monoide degli insiemi finiti è cancellativo
Un fatto simpatico che ho imparato oggi: forse c'è una dimostrazione più semplice, che non fa uso di un "trucco" (come si dice in italiano "swindle"?).
Se \(A,B,C\) sono insiemi finiti, ed esiste una biiezione \(A\sqcup C\cong B\sqcup C\), allora esiste una biiezione \(A\cong B\); chiaramente (?) è falso per insiemi infiniti.
E' in effetti vera una cosa più forte: se si chiamano
- \({\sf B}(X,Y)\) l'insieme delle biiezioni tra l'insieme $X$ e l'insieme $Y$;
- \(R_{ABC} : {\sf B}(A\sqcup C, B\sqcup C) \to {\sf B}(A,B)\) la funzione costruita prima, che alla biiezione \(\alpha : A\sqcup C\cong B\sqcup C\) associa la biiezione \(R[\alpha] : A \cong B\)
Allora per ogni biiezione \(\phi : A\to A'\) e \(\psi : B \to B'\) si ha
\(R_{ABC}[\alpha]\circ \phi = R_{A'BC}[\alpha\circ(\varphi+C)]\) e \(\psi\circ R_{ABC}[\alpha] = R_{AB'C}[(\psi+C)\circ \alpha]\)
dove \(\phi + C : A \sqcup C \to A'\sqcup C\) agisce come \(\phi\) su $A$ e come l'identità su $C$, e analogamente fa \(\psi + C \). Ometto i pedici dalle $R$.
Se \(A,B,C\) sono insiemi finiti, ed esiste una biiezione \(A\sqcup C\cong B\sqcup C\), allora esiste una biiezione \(A\cong B\); chiaramente (?) è falso per insiemi infiniti.
E' in effetti vera una cosa più forte: se si chiamano
- \({\sf B}(X,Y)\) l'insieme delle biiezioni tra l'insieme $X$ e l'insieme $Y$;
- \(R_{ABC} : {\sf B}(A\sqcup C, B\sqcup C) \to {\sf B}(A,B)\) la funzione costruita prima, che alla biiezione \(\alpha : A\sqcup C\cong B\sqcup C\) associa la biiezione \(R[\alpha] : A \cong B\)
Allora per ogni biiezione \(\phi : A\to A'\) e \(\psi : B \to B'\) si ha
\(R_{ABC}[\alpha]\circ \phi = R_{A'BC}[\alpha\circ(\varphi+C)]\) e \(\psi\circ R_{ABC}[\alpha] = R_{AB'C}[(\psi+C)\circ \alpha]\)
dove \(\phi + C : A \sqcup C \to A'\sqcup C\) agisce come \(\phi\) su $A$ e come l'identità su $C$, e analogamente fa \(\psi + C \). Ometto i pedici dalle $R$.
Risposte
Con \(\sqcup\) intendi l'unione disgiunta? Se sì, non basta usare il fatto che \( \lvert A\sqcup C\rvert = \lvert A \rvert + \lvert C \rvert\)? Comunque non è detto che la biiezione tra \( A\sqcup C\) e \(B\sqcup C \) fissi \(C\). Sbaglio?
"vict85":Sì, esatto.
Con \(\sqcup\) intendi l'unione disgiunta?
Se sì, non basta usare il fatto che \( \lvert A\sqcup C\rvert = \lvert A \rvert + \lvert C \rvert\)?No, non basta, per il semplice motivo che la biiezione che ti è stata data non necessariamente manda \(A\) in \(B\); però, se esiste una biiezione tra le somme, ne esiste un'altra che ha questa proprietà.
(Funziona anche con insiemi infiniti, ma è più difficile.)
Non capisco: il mio suggerimento era di dimostrare che A e B avevano la stessa cardinalità e questo è equivalente all'esistenza di una biiezione tra di loro. Insomma non era una dimostrazione costruttiva.
Relativamente a questa parte:
Il teorema, da solo, non definisce alcuna \(R_{ABC}\). Quello che dice è che se \({\sf B}(A\sqcup C, B\sqcup C) \neq \emptyset\) allora \({\sf B}(A, B) \neq \emptyset\). La tua dimostrazione forse ne definisce una, ma non è strettamente necessario farlo. Inoltre la verità di quello che scrivi dipende da \(R_{ABC}\).
"fulcanelli":
- \({\sf B}(X,Y)\) l'insieme delle biiezioni tra l'insieme $X$ e l'insieme $Y$;
- \(R_{ABC} : {\sf B}(A\sqcup C, B\sqcup C) \to {\sf B}(A,B)\) la funzione costruita prima, che alla biiezione \(\alpha : A\sqcup C\cong B\sqcup C\) associa la biiezione \(R[\alpha] : A \cong B\).
Il teorema, da solo, non definisce alcuna \(R_{ABC}\). Quello che dice è che se \({\sf B}(A\sqcup C, B\sqcup C) \neq \emptyset\) allora \({\sf B}(A, B) \neq \emptyset\). La tua dimostrazione forse ne definisce una, ma non è strettamente necessario farlo. Inoltre la verità di quello che scrivi dipende da \(R_{ABC}\).
"vict85":Infatti: come dimostri questo fatto? Una biiezione \(A\sqcup C\cong B\sqcup C\) definisce, per restrizione, una biiezione tra A e una copia di A in \(B\sqcup C\): cosa ti assicura che questa copia sia in biiezione con B? Pensare di poter "cancellare C" e di ottenere un insieme di cardinalità |B|, è una petizione di principio: è ciò che devi dimostrare. Il fatto, poi, dipende dalla finitezza degli insiemi in gioco: per insiemi infiniti, \(A\sqcup A\cong A\) e tuttavia, ovviamente, \(A\not\cong \varnothing\)...
Non capisco: il mio suggerimento era di dimostrare che A e B avevano la stessa cardinalità e questo è equivalente all'esistenza di una biiezione tra di loro.
"vict85":Questo è il significato di "è vera una cosa più forte": la regola con cui una biiezione \(A\sqcup C \cong B\sqcup C\) induce una biiezione \(A\cong B\) è una funzione \({\sf B}(A\sqcup C,B\sqcup C)\to {\sf B}(A,B)\).
Relativamente a questa parte:
Il teorema, da solo, non definisce alcuna \(R_{ABC}\).
Inoltre la verità di quello che scrivi dipende da \(R_{ABC}\).No, per fortuna no: se $R$ è naturale, è unica.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo