- Show that for all sets $S$ and $T, S-T = S \cap \overline{T}$.
Proof. i) Let us suppose $x \in S-T$. Since $x \in S$ and $ x \notin T$, $ x \in S \cap \overline{T}$ holds.
ii) Suppose $x \in S \cap \overline{T}$. Then, $x \in S$ and $ x \in \overline{T}$ hold. Note that $x \in \overline{T}$ implies $ x \notin T$. Hence, $ x \in S - T$ holds.
Since we have proved that a string $w$ exists in $S - T$ if and only if $S \cap \overline{T}$, we have proved that $ S-T = S \cap \overline{T}$ holds.
- Show that $S_1 = S_2$ if and only if $S_1\cup S_2 = S_1 \cap S_2$.
Proof. Let us prove the contrapositive of the original statement, which is, $S_1\cup S_2 \ne S_1 \cap S_2$ if and only if $S_1 \ne S_2$. We first prove the if direction of the statement in i) and the only-if direction in ii).
i) (if direction) Since $S_1 \ne S_2$, there always exists a string $w$ such that $w \in S_1$ (or $w \in S_2$) and $w \notin S_2$ (or $w \notin S_1$).
Since $w \in S_1$ and $w \notin S_2$, $w \in S_1 \cup S_2$ and $w \notin S_1 \cap S_2$. Therefore, $S_1 \cup S_2 \ne S_1 \cap S_2$ holds.
ii) (only-if direction) Since $S_1 \cup S_2 \ne S_1 \cap S_2$, there always exists a string $w$ such that $w \in S_1 \cup S_2$ and $w \notin S_1 \cap S_2$. From $w \notin S_1 \cap S_2$, we can see that the string $w$ exists only in one of $S_1$ and $S_2$. Therefore, $S_1 \ne S_2$ holds.
Since we have proved both directions, we conclude that $S_1\cup S_2 \ne S_1 \cap S_2$ if and only if $S_1 \ne S_2$ holds. Then, since the contrapositive of the statement is proven to be true, we have proved that $S_1 = S_2$ if and only if $S_1\cup S_2 = S_1 \cap S_2$ also holds.
- Show that if $S_1$ and $ S_2$ are finite sets with $\lvert S_1 \rvert = n$ and $\lvert S_2 \rvert = m$, then $\lvert S_1 \cup S_2 \rvert \leq n+m$.
Proof. $\lvert S_1 \cup S_2 \rvert = \lvert S_1\rvert + \lvert S_2\rvert-\lvert S_1\cap S_2\rvert = n+m-\lvert S_1\cap S_2\rvert \leq n+m$.
- Show that $S_1 = S_2$ if and only if $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset$.
Proof. We first prove the if direction of the statement in i) and the only-if direction in ii).
i) (if direction) It is easy to see that $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset$ implies $S_1 \cap \overline{S_2} = \emptyset$ and $S_1 \cap \overline{S_2} = \emptyset$. Since $S_1 \cap \overline{S_2} = S_1 - S_2 = \emptyset$, we can deduce that $S_1 \subseteq S_2$. Moreover, $\overline{S_1} \cap S_2 = \emptyset$ implies $S_2 \subseteq S_1$. Since $S_1 \subseteq S_2$ and $S_2 \subseteq S_1$, we deduce that $S_1 = S_2$.
ii) (only-if direction) Since $S_1 = S_2$, $S_1 \cap \overline{S_2} = S_1-S_2 = \emptyset$ and $\overline{S_1} \cap S_2 = S_2\cap\overline{S_1} = S_2-S_1 = \emptyset$. Hence, $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset \cup \emptyset = \emptyset$.
- Show that $S_1 \cup S_2 -(S_1 \cap \overline{S_2}) = S_2$.
Proof. $S_1 \cup S_2 -(S_1 \cap \overline{S_2}) $
$= (S_1 \cup S_2)\cap (\overline{S_1\cap\overline{S_2}})$
$=(S_1 \cup S_2)\cap(\overline{S_1} \cup S_2)$
$=(S_1\cap \overline{S_1})\cup S_2$
$=\emptyset \cup S_2 = S_2$
- Show that $\sum_{i=0}^n 2^i = 2^{n+1}-1.$
Proof. Let us prove by induction on $n$.
Basis: Prove that the statement holds when $n=0$. \[ \sum_{i=0}^0 2^i = 2^0 = 1 \textrm{ and }2^{0+1}-1 = 1. \]
Inductive Step: Assume that the statement holds when $n = k$ and prove that it holds even when $n = k+1$.
\[\sum_{i=0}^{k+1} 2^i = \sum_{i=0}^k 2^i+2^{k+1} = 2^{k+1}-1 + 2^{k+1}\] \[=2(2^{k+1})-1 = 2^{k+2}-1.\]
- Show that $\sum_{i=1}^n \frac{1}{i^2} \leq 2-\frac{1}{n}$.
Proof. Let us prove by induction on $n$.
Basis: Prove that the statement holds when $n=1$. \[ \sum_{i=1}^1 \frac{1}{i^2} = \frac{1}{1} = 1 \leq 2-\frac{1}{1} = 1 \]
Inductive Step: Assume that the statement holds when $n = k$ and prove that it holds even when $n = k+1$.
By assumption, we know that the following holds: \[ \sum_{i=1}^{k} \frac{1}{i^2} \le 2 - \frac{1}{k}. \]
If we add $\frac{1}{(k+1)^2}$ to both sides of the equation, then we have \[ \sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k} + \frac{1}{(k+1)^2}. \]
Now we prove $2-\frac{1}{k}+\frac{1}{(k+1)^2} \leq 2-\frac{1}{(k+1)}$ as follows:
\[\frac{1}{(k+1)^2} \leq \frac{1}{k}-\frac{1}{k+1}\] \[\Rightarrow \frac{1}{(k+1)^2} \leq \frac{1}{k(k+1)}\] \[\Rightarrow (k+1)^2 \ge k(k+1)\]
- Let $\Sigma = \{ a,b \}$ and $L= \{ aa,bb \} $. Use set notation to describe $\overline{L}$.
Proof. $\overline{L}$ = $\{\epsilon,a,b,ab,ba\} \cup \{w \in \Sigma^* \mid \lvert w \rvert \geq 3\}.$
- Are there languages for which $\overline{L^* }=(\overline{L})^*$?
Proof. By definition of the Kleene star (or the Kleene closure), $\epsilon \in L^* $ for every $L$. Hence, $\epsilon \notin \overline{L^* }$. We have a contradiction because $\epsilon \in (\overline{L})^*$.
Therefore, we can conclude that there is no such language $L$.
- Prove or disprove the following claims. $(L_1 \cup L_2)^R = L_1^R\cup L_2^R$ for all languages $L_1$ and $L_2.$
Proof. To prove equality, we first prove that i) $(L_1 \cup L_2)^R \subseteq L_1^R\cup L_2^R$ and then prove that ii) $L_1^R\cup L_2^R \subseteq (L_1 \cup L_2)^R$.
i) Consider a string $w \in (L_1 \cup L_2)^R$. Since $w \in (L_1 \cup L_2)^R$, $w^R \in L_1 \cup L_2$. This, in turn, implies that $w^R$ is either in $L_1$ or $L_2$. Since $w^R \in L_1$ or $w^R \in L_2$, it is immediate that $w \in L_1^R$ or $w \in L_2^R$, and thus, $w \in L_1^R \cup L_2^R$. Since we have proved that every string $w$ in $(L_1 \cup L_2)^R$ also exists in $L_1^R \cup L_2^R$, we conclude that $(L_1 \cup L_2)^R \subseteq L_1^R\cup L_2^R$ holds.
ii) Consider a string $w \in L_1^R \cup L_2^R$. Then, $w$ exists either in $L_1^R$ or $L_2^R$. This implies that either $w^R \in L_1$ or $w^R \in L_2$ holds. In other words, $w^R \in L_1 \cup L_2$. From $w^R \in L_1 \cup L_2$, it is immediate that $w \in (L_1 \cup L_2)^R$. Therefore, we have proved that $L_1^R\cup L_2^R \subseteq (L_1 \cup L_2)^R$ also holds.
Since we have proved both directions of the statement, we have proved that $(L_1 \cup L_2)^R = L_1^R\cup L_2^R$ for all languages $L_1$ and $L_2.$