Suppose that $A, B$ and $C$ are sets. For each of the following statements either prove it is true or give a counterexample to show that it is not. By $X \subsetneq Y$ we mean that $X$ is a proper subset of $Y: X \subseteq Y$ and $X \neq Y$.
(a) $A \in B \wedge B \in C \Longrightarrow A \in C$
(b) $A \subseteq B \wedge B \subseteq C \Longrightarrow A \subseteq C$
(c) $A \subsetneq B \wedge B \subsetneq C \Longrightarrow A \subsetneq C$
(d) $A \in B \wedge B \subseteq C \Longrightarrow A \in C$
(e) $C \in \mathcal{P}(A) \Longleftrightarrow C \subseteq A$
(f) $A=\emptyset \Longleftrightarrow \mathcal{P}(A)=\emptyset$

Which of the following conditions imply that $B=C ?$ In each case, either prove or give a counterexample.
(a) $A \cup B=A \cup C$
(b) $A \cap B=A \cap C$
(c) $A \oplus B=A \oplus C$
(d) $A \times B=A \times C$

Suppose that $A, B$ and $C$ are sets. For each of the following statements either prove it is true or give a counterexample to show that it is not.
(a) $A \backslash(B \cup C)=(A \backslash B) \cup(A \backslash C)$
(b) $(A \backslash B) \times C=(A \times C) \backslash(B \times C)$
(c) $(A \oplus B) \times C=(A \times C) \oplus(B \times C)$
(d) $(A \cup B) \times(C \cup D)=(A \times C) \cup(B \times D)$

(a) List, in lexicographic order, the first six strings, of ${a, b c}^{}-{a b c}^{} . \quad($ Assume $a<b<c .)$ (b) Consider the language of all binary strings whose first two characters are the same as the string’s last two characters. (Say that a string must have at least two character to satisfy this condition.) Find a way to write this language by combining finite sets (written {list-of-strings}) with union, concatenation, and star (written $\cup, \circ, *$ ). Of course you can use parentheses to make the order of operations clear. (The convention is star, then concatenation, then union.)

*5. A stupid math teacher tells Zack to write down every positive integer from 1 to 99999 . Numbers are to be written in the usual way, with no leading zeros. In carrying out this tedious exercise, how many times will Zach write the digit 1? Find an easy way to get to the answer.

*6. Find a picture-proof (in the spirit of those in Lecture 5) that $\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\frac{1}{256}+\cdots=\frac{1}{3}$.