## 2014-01-08

### Unions & Intersections

Some of the more interesting exercises (a purely subjective qualification). Easy concepts, difficult language. Boo.

Theorem:
The following are equivalent:
- the union of C and (the union of the B-alphas, over the alphas in lambda,)
- the union of (the union of C and the B-alpha), over the alphas in lambda.
Proof:
\begin{align*}

p(x, C, \{B_\alpha\}_{\alpha\in\Lambda})& = \underbrace{x \in
\left\{C \cup
\left[\bigcup_{\alpha\in\Lambda}B_\alpha\right]
\right\}}\\[1em]

& = \underbrace{(x \in C)} \vee
\underbrace{\left( x \in
\left[\bigcup_{\alpha\in\Lambda}B_\alpha\right]
\right)}\\[1em]

& = \underbrace{
(x \in C)} \vee \underbrace{(\exists(B_\alpha), x\in B_\alpha)
}\\[1em]

& =
\underbrace{
\exists(C\cup B_\alpha), x \in (C\cup B_\alpha)
}\\[1em]

&=\underbrace{x\in \left\{\bigcup_{\alpha\in\Lambda}(C\cup B_\alpha)\right\}}\\[1em]

\end{align*}
Less than seven hours till first alarm. I really should get out of the office.

Theorem:
The following are equivalent:
- the intersection of C and (the intersection of the B-alphas, over the alphas in lambda,)
- the intersection of (the intersection of C and the B-alpha), over the alphas in lambda.
Proof:
\begin{align*}

p(x, C, \{B_\alpha\}_{\alpha\in\Lambda})& = \underbrace{x \in
\left\{C \cap
\left[\bigcap_{\alpha\in\Lambda}B_\alpha\right]
\right\}}\\[1em]

& = \underbrace{(x \in C)} \wedge
\underbrace{\left( x \in
\left[\bigcap_{\alpha\in\Lambda}B_\alpha\right]
\right)}\\[1em]

& = \underbrace{
(x \in C)} \wedge \underbrace{(\forall(B_\alpha), x\in B_\alpha)
}\\[1em]

& =
\underbrace{
\forall(C\cap B_\alpha), x \in (C\cap B_\alpha)
}\\[1em]

&=\underbrace{x\in \left\{\bigcap_{\alpha\in\Lambda}(C\cap B_\alpha)\right\}}\\[1em]

\end{align*}

### De Morgan's law:

Theorem:
Where all $(A_\alpha)$s are subsets of U, the following are equivalent:
- the complement in U of (the union over the alphas in lambda, of the A-alphas)
- the intersection over the alphas in lambda of (the complements in U, of the A-alphas)
Proof:
\begin{align*}

p(x, U, \{A_\alpha\}_{\alpha\in\Lambda})& = x\in\left[\bigcup_{\alpha\in\Lambda} A_\alpha\right]^{\mathsf{\complement}}_{U}\\[1em]

&=(x\in U)\wedge
(\underbrace{\forall A_\alpha, A_\alpha \in U)}\wedge \underbrace{\neg(\exists A_\alpha, x\in A_\alpha)}
\\[1em]

&=(x\in U)\wedge
(\underbrace{\forall A_\alpha, A_\alpha \in U)}\wedge \underbrace{(\forall A_\alpha, x\in (A_\alpha)^{\complement}_U)}
\\[1em]

&= x\in
\left[\bigcap_{\alpha\in\Lambda} (A_\alpha)^{\mathsf{\complement}}_{U}\right]\\[1em]

\end{align*}
Theorem:
Where all $(A_\alpha)$s are subsets of U, the following are equivalent:
- the complement in U of (the intersection over the alphas-in-lambda, of the A-alphas)
- the union over the alphas-in-lambda of (the complements in U, of the A-alphas)

Proof:
\begin{align*}

p(x, U, \{A_\alpha\}_{\alpha\in\Lambda})& = x\in\left[\bigcap_{\alpha\in\Lambda} A_\alpha\right]^{\mathsf{\complement}}_{U}\\[1em]

&=(x\in U)\wedge
(\underbrace{\forall A_\alpha, A_\alpha \in U)}\wedge \underbrace{\neg(\forall A_\alpha, x\in A_\alpha)}
\\[1em]

&=(x\in U)\wedge
(\underbrace{\forall A_\alpha, A_\alpha \in U)}\wedge \underbrace{(\exists A_\alpha, x\in (A_\alpha)^{\complement}_U)}
\\[1em]

&= x\in
\left[\bigcup_{\alpha\in\Lambda} (A_\alpha)^{\mathsf{\complement}}_{U}\right]\\[1em]

\end{align*}

Theorem:
Proof: