Stuck trying to prove that $A\cup(\overline{A}\cap B)= A \cup B $

Question

I am a beginner in set theory and would like to prove exactly that:

$$A\cup(\overline{A}\cap B)= A \cup B $$

I'm stuck here and I can't find alternative solutions

i) $$\Omega\cap(A\cup B)= A \cup B $$ where $\Omega$ is the universal set

ii) $$(A\cup\overline{A})\cap(A\cup B)= A \cup B $$

iii) $$((A\cup\overline{A})\cap A)\cup((A\cup\overline{A})\cup B)= A \cup B $$

iv) $$((\Omega\cap A)\cup((A\cup\overline{A})\cup B)= A \cup B $$

v) $$(A\cup((A\cup\overline{A})\cup B)= A \cup B $$

Answer 1

You are doing it the hard way going from the simple expression to the complicated expression. It's doable but you are groping in the dark. If you don't know the exact path going from simple to complicated can be wild guesses but going from complicated to simple is just and matter of simplifying and seeing where it takes you.

$A\cup(\overline{A}\cap B)=$

$(A\cup \overline A) \cap (A \cup B) $ by distribution

$=\Omega \cap (A \cup B)$

$A\cup B$.

I didn't know where I was going and that last line fell in my lap and actually surprised me.

Going the other way is possible:

$A\cup B = \Omega \cap (A\cup B)=$

$(A\cup \overline A) \cap (A\cup B) = $

$A \cup (\overline A\cap B)$

Honestly, going for line two to three was practically impossible to see even when I knew where I was going.

...

I still find element chasing is the most intuitive for me. $x \in A\cup (\overline A\cap B)$ means either $x \in A$ or $x \in A\cap B$. If $x \in A$ then $x \in A$ then $x \in A \cup B$ as $A \subset A\cup B$. If $x \not \in A$ then $x \in \overline A \cap B$ so $x \in B$. So $x \in A\cup B$ as $B \subset A\cup B$. So either way $x \in A \cup B$.

On the other hand of $y \in A\cup B$ then $y \in A $ or $y \in B$. If $y \in A$ then $y \in A\cup (\overline A \cap B)$. If $y \not \in A$ then $y \in B$ and $y \in \overline A$ so $y \in \overline A \cap B$. So $y \in A\cup (\overline A \cap B)$. So either way $y \in A\cup (\overline A \cup B)$

Answer 2

So, with the note that all complementation here is relative to superset $\Omega$ (call it the "universal set").   We just use identity, complementation, and the next step is distribution.

$$\begin{align}A\cup B ~&= \Omega\cap(A\cup B)&& \text{identity}\\&=(A\cup\overline A)\cap (A\cup B)&&\text{complementation} \\ &= \underline{\phantom{A\cup(\overline A\cap B)}}&&\text{distribution : }\\&&&&\blacksquare\end{align}$$

Also, always keep in mind that your goal.

Answer 3

just a suggestion:

if you are not very familiar with manipulating expressions using the boolean lattice operations $\cup$ and $\cap$ it may sometimes be easier, or more secure, to work with the boolean algebra notation. here the operation of addition ($+$) is symmetric difference and the multiplication (whose symbol may be omitted as in ordinary algebra) is just intersection.

in this notation a set union $A\cup B$ translates to $A+B+AB$ and complementation is given by $\bar A \equiv \Omega+A$ and we may use $1$ in place of $\Omega$, so keeping in mind that for any $A$ we have $A\bar A = 0$, $$ \begin{align} A\cup(\bar A \cap B) &\equiv A + (\bar A \cap B) + A(\bar A \cap B) \\ & \equiv A+ (1+A)B +A\bar AB \\ &\equiv A+1 B +AB +0 \\ &\equiv A+B+AB \\ &\equiv A\cup B \end{align} $$

Answer 4

The answers above solve the problem. However, as you are a beginner I would like to suggest: Let $x\in A\cup(\overline{A}\cap B)$ then $x\in A$ or $x\in (\overline{A}\cap B) $. If $x\in A$ then $x\in A\cup B$, now if $x\in \overline{A}\cap B$ then $x\in B$ so $x\in A\cup B$. This prove the "$\subset$" relation. Can you try the "$\supset$"?