How can I prove that A\A\B = A&B?

63 Views Asked by At

I wanted to show that both sets are equal. My Textbook says following:

$\in$ means "is element of", $\land$ is the and operator, $\lnot$ is the not operator, $\notin$ means "is not element of", $\lor$ is the or operator

$$\def\-{\setminus}\begin{split} x \in A\-A\-B &\iff\\ (x \in A) \land (\lnot(x \in (A\-B)) &\iff\\ (x \in A) \land (\lnot(x \in A \land (\lnot(x \in B))) &\iff\\ (x \in A) \land (\lnot(x \in A \land x \notin B)) &\iff\\ (x \in A) \land (x \notin A \lor x \in B)\end{split}$$

Let $(x \in A)$ be $C$ and $(x \in B)$ be $D$

  • Case 1 $C$ True $D$ True -> Contradiction $x \in A \land x \notin A$ cannot be true
  • Case 2 $C$ True $D$ True -> Contradiction $x \in A \land x \notin A$ cannot be true
  • Case 3 $C$ False $D$ True -> True

Thus $$(x \in A) \land (x \notin A \lor x \in B) \iff\\ (x \in A) \land (x \in B) \iff\\ x \in (A \cap B)$$

What is the subsetproof? Because I have not fully understood the negation of $\land$

2

There are 2 best solutions below

0
On

Because I have not fully understood the negation of $\land$

The equivalences, $\neg(a\land b)\equiv (\neg a\lor\neg b)$ and $\neg(a\lor b)\equiv (\neg a\land\neg b)$, are known as deMorgan's Laws.   The justification is as follows:

$\neg(a\land b)$ is true when it is not the case that both $a$ and $b$ are true.   This happens exactly when at least one of $a$ or $b$ is false, that is $(\neg a\lor\neg b)$ is true.

$\neg(a\lor b)$ is true when it is not the case that at least one of $a$ or $b$ are true.   This happens exactly when at both of $a$ and $b$ are false, that is $(\neg a\land\neg b)$ is true.


In a similar vein, $a\land(\lnot a\lor b)$ is true exactly when $a$ is true and at least one of $\lnot a$ or $b$ is true.   So it means $a$ is true, and since $\lnot a$ cannot also be true, therefore $b$ must be.   Conversely $a\land b$ is true when $a$ and $b$ are both true.   Now $b$ being true implies that at least one of $b$ or $\neg a$ is true.   Therefore $a\land(\lnot a\lor b)\equiv (a\land b)$

0
On

The case work is incorrect.
Continue the sequence of equivalences using
'and' is distributive over 'or'.