[MatematicaDiscreta] Dimostrazione differenza tra insiemi

[klight1]

Ciao, per esercizio devo effettuare la seguente dimostrazione:
Siano $A, B$ insiemi con $A sube B$ dimostrare che $B - (B - A) = A$

Riesco a figurarmi mentalmente il relativo diagramma di Eulero-Venn in cui se agli elementi del $B$ originario tolgo gli elementi del suo complemento $C_B (A)$ ottengo, ovviamente, $A$ ma non riesco proprio a tradurlo nella formulazione di singoli passaggi.

A me viene da cominciare dicendo che bisognerebbe dimostrare la doppia inclusione, ovvero: (1) $B - (B - A) sube A$ e (2) $A sube B - (B - A)$.

Per cui (1) dalla definizione di differenza tra insiemi:

$x in B - (B - A) = x in B ^^ x notin B \ A$

al che mi verrebbe di conseguenza da dire che:

$x notin B - A = x in A ^^ x notin B$

e se vado a sostituirlo alla formula sopra ottengo:

$x in B ^^ x notin B ^^ x in A$

E vado in contraddizione. Qual è allora il modo giusto di procedere? E come posso fare anche per gli altri passaggi mancanti dell'intera dimostrazione?


Grazie in anticipo per l'aiuto

[agnenga1]

Si ha che $x\in B-(B-A) \Leftrightarrow$ $x\inB \^^ x \notin B-A$, da cui $x \in A$ (visto che sta in $B$ e non sta nel complemento di $A$ rispetto a $B$, deve stare in $A$).
Se $x\in A$ è ovvio che sia anche in $B$. .1:-)7

[klight1]

Grazie per la risposta veloce.

Ok, ricapitolando ora abbiamo per (1) che:
$x in B - (B - A) hArr x in B ^^ x notin B - A$
da cui si deduce che $x in A$ per cui $B - (B - A) sube A$ è verificato

Ora per la parte (2) della dimostrazione, mi verrebbe da procedere così:
di $A sube B - (B - A)$ sappiamo che $A sube B$ è vera per via delle premesse, ma per $A sube B - A$ come potrei procedere?

[agnenga1]

Se $x \inA$ allora $x \in B$, inoltre si ha che $x \notin (B-A)$ (visto che è il complemento di $A$ in $B$ e abbiamo detto che $x$ sta in $A$ e il complemento ha intersezione nulla con $A$). Da tutto questo si evince che $x$ debba stare nel complemento di $B-A$ rispetto a $B$ ovvero $B-(B-A)$.
Comunque la dimostrazione di questo fatto è immediata usando l algebra degli insiemi e il fatto che l'operazione di complementazione è involutoria (= se applicata ripetutamente alterna continuamente due risultati: p.es. il complemento del complemento di un insieme è ancora l'insieme di partenza). Allora $B-(B-A) = (B - B) \uu A = \emptyset \uu A = A$.

[marco9551]

Sbagli nel fatto di considerare che
$xnotin(B-A)<=>xnotinB ^^ x inA$

Infatti:
$xnotin(B-A)<=>not(x in(B-A))<=>not (x inB^^xnotinA))<=>xnotinBvvx inA$ per la prima legge di De Morgan.

[agnenga1]

La catena di equivalenze è corretta, quindi è errata la prima con la congiunzione. Non capisco però cosa c'entri questa equivalenza (di carattere più generale rispetto al caso in esame) con quello che si deve dimostrare. Al primo membro infatti si ha $x \notin (B-A) \^^ A\sube B$, dalle quali direi che si possa dedurre $x \in A$ (che non stia in $B$ resta negato dalla seconda assunzione, e nella mia formula era esplicitamente espresso con $x \in B$).

[marco9551]

Devi dimostrare che, dati due insiemi A e B con $A subeB$ , se x è un generico elemento
$x inB-B-(B-A)<=>x inA$ che per definizione di uguaglianza tra insiemi è equivalente a dimostrare l'uguaglianza $B-(B-A)=A$

Dimostriamo il primo teorema cioè
$x inB-(B-A)=>x inA$

$x inB-(B-A)<=>(x inB)^^[(x notinB)vv(x inA)]=>x inA$ (è infatti un sillogismo disgiuntivo)

Dimostriamo il secondo teorema
$x inA=>x inB-(B-A)$

$x inA<=>x inB^^[(x notinB)vv(x inA)]$ (poichè sappiamo che $A subeB$;inoltre osserva che la proposizione tra paretensi quadre si deduce da $x inA$ sfruttando una regola di inferenza tautologica che non altera il valore logico del ragionamento. Puoi verificarlo con una tavola di verità.$<=>(x inB)^^[x notin(B-A)]<=>x inB-(B-A)$

Per cui l'uguaglianza è dimostrata.

[klight1]

Grazie a tutti per l'aiuto, finalmente sono riuscito a chiarirmi questi dubbi!