[Teoria degli insiemi] Leggi di cancellazione
Devo dimostrare o confutare le seguenti tre "leggi di cancellazione":
(i) $(A uu B) = (A uu C) => B = C$
(ii) $(A nn B) = (A nn C) => B = C$
(iii) $(A uu B) - (A nn B) = (A uu C) - (A nn C) => B = C$
($A - B$ indica la differenza tra gli insiemi $A$ e $B$)
La (i) e la (ii) sono false, dato che sono riuscito a trovare due controesempi che hanno confutato le leggi.
Al contrario, per la (iii) non sono riuscito a trovare un controesempio e mi sembra che la legge sia corretta. Il problema è che devo dimostrarlo...
Un metodo semplice potrebbe essere quello di sfruttare i diagrammi di Venn, ma preferirei una dimostrazione formale e precisa.
Grazie in anticipo per i vostri consigli e buona giornata
(i) $(A uu B) = (A uu C) => B = C$
(ii) $(A nn B) = (A nn C) => B = C$
(iii) $(A uu B) - (A nn B) = (A uu C) - (A nn C) => B = C$
($A - B$ indica la differenza tra gli insiemi $A$ e $B$)
La (i) e la (ii) sono false, dato che sono riuscito a trovare due controesempi che hanno confutato le leggi.
Al contrario, per la (iii) non sono riuscito a trovare un controesempio e mi sembra che la legge sia corretta. Il problema è che devo dimostrarlo...
Un metodo semplice potrebbe essere quello di sfruttare i diagrammi di Venn, ma preferirei una dimostrazione formale e precisa.
Grazie in anticipo per i vostri consigli e buona giornata
Risposte
Solitamente quando vuoi dimostrare che due insiemi coincidono dimostri che ciascuno sta dentro l'altro. Prova cosi'.
per la i, esistono controesempi e il primo che mi viene in mente é \(\{1\}\cup\{1\}\) ed \(\{1\} \cup \emptyset\), naturalmente \(\{1\}=\{1\}\cup\{1\}=\{1\} \cup \emptyset=\{1\}\) ma \(\{\{0\}\}=\{1\}\neq\emptyset=:0\)
per la ii idem, puoi usare \(\{1\}\cap \{0\}\) e \( \{1\}\cap \emptyset\), naturalmente \(\emptyset=\{1\}\cap \{0\}= \{1\}\cap \emptyset=\emptyset\) ma \(1:=\{0\}\neq \emptyset=:0\)
per la iii prova come suggerito da killing.. prova coi diagrammi di veen ma alla fine devi fare vedere le cose formalmente e non coi disegnini.. (prova a sfruttare il fatto che due insiemi se sono uguali allora la loro differenza (simmetrica) é nulla)
per la ii idem, puoi usare \(\{1\}\cap \{0\}\) e \( \{1\}\cap \emptyset\), naturalmente \(\emptyset=\{1\}\cap \{0\}= \{1\}\cap \emptyset=\emptyset\) ma \(1:=\{0\}\neq \emptyset=:0\)
per la iii prova come suggerito da killing.. prova coi diagrammi di veen ma alla fine devi fare vedere le cose formalmente e non coi disegnini.. (prova a sfruttare il fatto che due insiemi se sono uguali allora la loro differenza (simmetrica) é nulla)
Innanzitutto vi ringrazio per le vostre risposte 
Come da voi proposto, ho sfruttato il fatto che l'uguaglianza tra due insiemi è equivalente a una "doppia inclusione", ovvero:
$A = B iff (A sube B) ^^ (B sube A)$
Dimostrazione diretta della legge di cancellazione (iii):
$(A uu B) - (A nn B) = (A uu C) - (A nn C)$
$=> ((A uu B) - (A nn B) sube (A uu C) - (A nn C)) ^^ ((A uu C) - (A nn C) sube (A uu B) - (A nn B))$
$=> B sube C ^^ C sube B$
$=> B = C$
Eventuali commenti relativi alla dimostrazione sono graditi!
Come da voi proposto, ho sfruttato il fatto che l'uguaglianza tra due insiemi è equivalente a una "doppia inclusione", ovvero:
$A = B iff (A sube B) ^^ (B sube A)$
Dimostrazione diretta della legge di cancellazione (iii):
$(A uu B) - (A nn B) = (A uu C) - (A nn C)$
$=> ((A uu B) - (A nn B) sube (A uu C) - (A nn C)) ^^ ((A uu C) - (A nn C) sube (A uu B) - (A nn B))$
$=> B sube C ^^ C sube B$
$=> B = C$
Eventuali commenti relativi alla dimostrazione sono graditi!
"foo":non capisco come deduci la seconda \(\Rightarrow\) (graficamente é banale e su questo non ci piove, ma devi mostrare i passaggi o almeno dire cosa hai sfruttato)
Dimostrazione diretta della legge di cancellazione (iii):
$(A uu B) - (A nn B) = (A uu C) - (A nn C)$
$=> ((A uu B) - (A nn B) sube (A uu C) - (A nn C)) ^^ ((A uu C) - (A nn C) sube (A uu B) - (A nn B))$
$=> B sube C ^^ C sube B$
$=> B = C$
"garnak.olegovitc":
non capisco come deduci la seconda \(\Rightarrow\) (graficamente é banale e su questo non ci piove, ma devi mostrare i passaggi o almeno dire cosa hai sfruttato)
Prendiamo la parte "a sinistra" dell'operatore logico $^^$, ovvero:
$(A uu B) - (A nn B) sube (A uu C) - (A nn C)$
Il ragionamento che ho fatto è il seguente:
$(A uu B) - (A nn B) sube (A uu C) - (A nn C)$
$=> (A uu B) sube (A uu C)$
$=> B sube C$
@garnak.olegovitc: È quello che intendevi?
La prima deduzione mi sembra giusta e non banale, mentre la seconda è del tutto falsa. Come controesempio basta prendere un \(B\) che contiene \(A\) e un \(C\) che ne è disgiunto. Quindi non è la strada giusta. Io suggerisco di scomporre \(A\cup B\) come \((A\cap\overline{B})\sqcup(A\cap B)\sqcup(\overline{A}\cup B)\) dove con la linea ho indicato i complementari e con \(\sqcup\) le unioni di insiemi disgiunti.
"vict85":
La prima deduzione mi sembra giusta e non banale, mentre la seconda è del tutto falsa. Come controesempio basta prendere un \(B\) che contiene \(A\) e un \(C\) che ne è disgiunto. Quindi non è la strada giusta. Io suggerisco di scomporre \(A\cup B\) come \((A\cap\overline{B})\sqcup(A\cap B)\sqcup(\overline{A}\cup B)\) dove con la linea ho indicato i complementari e con \(\sqcup\) le unioni di insiemi disgiunti.
@vict85: Grazie per aver risposto, effettivamente la seconda deduzione è falsa.
Riguardo al tuo consiglio, nella tua risposta hai scritto $bar A uu B$, ma penso sia stato un errore di battitura. Intendi:
$A uu B = (A nn bar B) uu (A nn B) uu (bar A nn B)$
vero?
Si intendo quello..
"foo":jain!!
Prendiamo la parte "a sinistra" dell'operatore logico $^^$, ovvero:
$(A uu B) - (A nn B) sube (A uu C) - (A nn C)$
Il ragionamento che ho fatto è il seguente:
$(A uu B) - (A nn B) sube (A uu C) - (A nn C)$
$=> (A uu B) sube (A uu C)$
$=> B sube C$
@garnak.olegovitc: È quello che intendevi?
per la legge:
"foo":Pongo il simbolo \(\setminus\) per \(-\) (perché troppo legato al Latex sono...), é facile vedere da questo post, dove di recente l ho provato (anche per \(\mathrm{ZFC}\)), che $$( A \cup B) \setminus (A \cap B)= (A \setminus B) \cup (B \setminus A)$$$$(A \cup C) \setminus (A \cap C)=(A \setminus C) \cup (C \setminus A)$$ ma per definizione di differenza simmetrica non si ha altro che $$( A \cup B) \setminus (A \cap B)= (A \setminus B) \cup (B \setminus A)=: A \bigtriangleup B$$$$(A \cup C) \setminus (A \cap C)=(A \setminus C) \cup (C \setminus A)=: A \bigtriangleup C$$ quindi quello che devi mostrare, scritto in forma piú compatta, di modo che ti permetta di vedere subito alcune cose (anche piú algebricamente) é la seguente $$A \bigtriangleup B=A \bigtriangleup C \to B=C$$ e si dimostra facilmente ovvero $$\begin{align} B &=\emptyset \bigtriangleup B \\ &= (A\bigtriangleup A) \bigtriangleup B \\ &= A\bigtriangleup(A\bigtriangleup B) \\ &= A \bigtriangleup (A \bigtriangleup C) \, {\color{Red}\leftarrow} \text{ qui ho usato l ipotesi} \\&= (A \bigtriangleup A) \bigtriangleup C \\ &= \emptyset \bigtriangleup C \\ &=C \end{align}$$ Facile no? In effetti per completezza dovresti mostrare prima:
(iii) $(A uu B) - (A nn B) = (A uu C) - (A nn C) => B = C$
-nel punto \((1)\) che \(\emptyset \bigtriangleup B=B\)
-nel punto \((2)\) che \( A\bigtriangleup A=\emptyset\)
-nel punto \((3)\) che \(\bigtriangleup\) é associativa (mentre che ci sei mostri anche che é commutativa)
e questo lo puoi fare banalmente anche da solo (se hai difficoltá comunque chiedi)
ps= Come noterai da alcune proofs non vi é alcun disegnino coi diagrammi, in effetti questi ti servono per capire i concetti e usarli per dedurre, velocemente e su due piedi, certe proprietá o meno, ma possono pure portare a deduzioni errate nei casi piú patologici e "strambi"[nota]strani[/nota]. Inoltre, tu parli di legge di cancellazione, ed é corretto per caritá... ma se ti domando chi "é l elemento neutro e chi é il simmetrico?" mi sai dire cosí velocemente a fronte di quanto scritto?
@garnak.olegovitc: Ti ringrazio per la tua risposta precisa e dettagliata. Ecco le dimostrazioni che completano la tua (con $A o+ B$ mi riferisco alla differenza simmetrica tra i due insiemi $A$ e $B$):
$(1) \emptyset o+ B = B$
Dimostrazione diretta:
$\emptyset o+ B = (\emptyset uu B) - (\emptyset nn B)$ (def. di differenza simmetrica)
$=> \emptyset o+ B = B - (\emptyset nn B)$ (proprietà dell'insieme vuoto)
$=> \emptyset o+ B = B - \emptyset$ (proprietà dell'insieme vuoto)
$=> \emptyset o+ B = B$ (proprietà dell'insieme vuoto)
$(2) A o+ A = \emptyset$
Dimostrazione diretta:
$=> A o+ A = (A uu A) - (A nn A)$ (def. di differenza simmetrica)
$=> A o+ A = A - (A nn A)$ (proprietà di idempotenza)
$=> A o+ A = A - A$ (proprietà di idempotenza)
$=> A o+ A = \emptyset$ (proprietà dell'insieme vuoto)
$(3)$ La differenza simmetrica è associativa.
Per questa "laboriosa" dimostrazione mi affido a Wikipedia
https://proofwiki.org/wiki/Symmetric_Difference_is_Associative
Parlo di "legge di cancellazione", perché ho tradotto in italiano il termine "cancellation laws" dal testo in inglese dal quale ho preso l'esercizio
P.S.: Se qualcuno fosse in grado di dimostrare questa legge in un modo differente (magari sfruttando i suggerimenti che ho ricevuto nei post precedenti), sarei curioso di vedere anche dimostrazioni alternative
$(1) \emptyset o+ B = B$
Dimostrazione diretta:
$\emptyset o+ B = (\emptyset uu B) - (\emptyset nn B)$ (def. di differenza simmetrica)
$=> \emptyset o+ B = B - (\emptyset nn B)$ (proprietà dell'insieme vuoto)
$=> \emptyset o+ B = B - \emptyset$ (proprietà dell'insieme vuoto)
$=> \emptyset o+ B = B$ (proprietà dell'insieme vuoto)
$(2) A o+ A = \emptyset$
Dimostrazione diretta:
$=> A o+ A = (A uu A) - (A nn A)$ (def. di differenza simmetrica)
$=> A o+ A = A - (A nn A)$ (proprietà di idempotenza)
$=> A o+ A = A - A$ (proprietà di idempotenza)
$=> A o+ A = \emptyset$ (proprietà dell'insieme vuoto)
$(3)$ La differenza simmetrica è associativa.
Per questa "laboriosa" dimostrazione mi affido a Wikipedia
https://proofwiki.org/wiki/Symmetric_Difference_is_Associative
"garnak.olegovitc":
Inoltre, tu parli di legge di cancellazione, ed é corretto per caritá... ma se ti domando chi "é l elemento neutro e chi é il simmetrico?" mi sai dire cosí velocemente a fronte di quanto scritto?
Parlo di "legge di cancellazione", perché ho tradotto in italiano il termine "cancellation laws" dal testo in inglese dal quale ho preso l'esercizio
P.S.: Se qualcuno fosse in grado di dimostrare questa legge in un modo differente (magari sfruttando i suggerimenti che ho ricevuto nei post precedenti), sarei curioso di vedere anche dimostrazioni alternative
In questo caso è puro tecnicismo che alle volte mi fa venire il mal di testa alla Jackie Chan (se hai presente le immagini). Esistono alternative valide come quelle che passano per la funzione caratteristica, a me in mente mi frulla un teorema sul prodotto relativo fra tre relazioni che forse potrei inserire considerando l intersezione come insieme di "mezzo" tra due i prodotti cartesiani con le differenze), e comunque molte dimostrazioni di insiemistica passano per la logica e in questa si affronta sempre la doppia implicazione e lo XOR, quindi se nel dimostrare l associatività dell unione usi la logica (anche naive con le tabelle di verità) perché non farlo anche in questo caso riducendo il tutto a poche spicciole parole... 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo