\documentclass[12pt]{article}

\usepackage[fleqn]{amsmath}
\usepackage{amsfonts}
\usepackage[margin=1in]{geometry}
\usepackage{enumitem}

\begin{document}
\setlength{\parindent}{0cm}

\begin{center} \large{CSC 208 \hfill Lab: Artificial Examples and Sets \hfill Spring 2025} \\ \end{center}
\begin{center} Wednesday, February 26th \end{center}

\textbf{Important Note:} some of these solutions are much more detailed than I would typically expect you to be in your labwork (or even in the Demos). This is meant to be a solution set, so I have included extra explanation to hopefully help your understanding. \textbf{The proofs in Problems 3 and 5 are at roughly the level that I would expect from you.}

\section*{Problem 1: Corners}

\begin{enumerate}

\item Consider the claim:\\

\textbf{Claim:} for any sets $S_1$ and $S_2$, $|S_1 \cup S_2| = |S_1|+|S_2|$.\\

This claim is not always true. For example, if we define the sets
\[
S_1 = \{a,b,c\}, \quad \text{and} \quad S_2 = \{b,c,d\},
\]
we can see that 
\[
S_1 \cup S_2 = \{a,b,c,d\}.
\]
But, $|S_1|=3$ and $|S_2|=3$, while $|S_1 \cup S_2| = 4 \neq 6$. The sets could overlap, but we do not count repeated elements, which is why this is not true.

\item The empty set is a subset of any set and is a subset of itself.\\

Consider the definition of a subset: a set $A$ is a subset of set $B$ if for all elements $x\in A$, then $x\in B$.\\

But how can we reason about all $x\in\emptyset$?\\

We consider the contrapositive of the statement: if $P\rightarrow Q$, then it must be the case that $\neg Q\rightarrow\neg P$. This is called the contrapositive of the original statement, and it is logically equivalent.\\

So we can reword the definition of a subset to instead say that $A$ is a subset of $B$ if there does not exist an $x\in A$ such that $x\notin B$ (i.e., $x\notin B\rightarrow x\notin A$).\\

Now we can reason directly about the empty set: since there does not exist an $x\in\emptyset$, then clearly there does not exist an $x\in\emptyset$ such that $x\notin S$ for any set $S$. Thus the empty set is a subset of any set, including itself!\\

\newpage

\item It depends on how we specifically think of defining our ``negative'' sets.\\

Note that the empty set $\emptyset$ acts like $0$ when using sets:
\[
A \cup \emptyset =\emptyset, \text{ like } x+0=x.
\]
\[
A - \emptyset = A, \text{ like } x-0=x.
\]
However, if we try to use this idea to define a ``negative'' set, we might try something analogous to $0-x = -x$. The problem here is that
\[
\emptyset - A = \emptyset.
\]
However, what if we try another analogy? Note that $x + (-x) = 0$. Since union and addition seem related, is there a set that we can union with $A$ to get $\emptyset$? Well... no.\\

However, there is one more thing we can try. What if we think about the universe set: $\mathcal{U}$? We find that
\[
A \cup \bar{A} = \mathcal{U}, \text{ and } \mathcal{U} - A = \bar{A}.
\]
So if somehow both $\emptyset$ and $\mathcal{U}$ ``act like'' our idea of $0$, then the set complement ``acts like'' a sort of ``negative'' set.\\

\item First, how does the Cartesian Product act like multiplication?\\

Let $A = \{a,b,c\}$ and $B = \{1,2,3\}$. Then we have 
\[
A\times B = \{(a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3)\}.
\]
We note that $|A|\cdot|B|=|A\times B|$, since $3$ elements when paired with $3$ elements produced $9$ pairs.\\

Now, is there a set that behaves like the ``$0$'' of the Cartesian Product? For multiplication, $x\cdot 0 = 0$. So is there a set $S$ such that $A\times S = S$ for all other sets $A$?\\

Yes, the empty set: there are no elements to pair with!
\[
A\times\emptyset = \emptyset.
\]

\item The power set is like exponentiation!\\

Consider the set $A = \{a,b,c\}$. Then its power set is
\[
\mathcal{P}(A) = \{\; \emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \;\}.
\]
Note that $|A|=3$ and $|\mathcal{P}(A)| = 8 = 2^3$. In general, it is true that 
\[
|\mathcal{P}(A)| = 2^{|A|}.
\]
So the power set ``acts like'' exponentiation (2 ``raised to the power of'' a given exponent - this is why we call it a ``power'' set!).

\end{enumerate}

\newpage

\section*{Problem 2: Trickiness}

\begin{enumerate}
\item Let $T = \{a,b,c,d,e\}$. Then a partition of $T$ could be the sets $S_1 = \{a,d\}$ and $S_2 = \{b,c,e\}$. Note that $S_1\cap S_2 = \emptyset$, and that $S_1\cup S_2 = T$, so this is a valid partition.

\item Consider all classes that you could enroll in at Grinnell this semester. Let this be the set $T$. Then a valid partition would be to let $S_1$ be the set of all classes listed (or cross-listed) as CSC, while letting $S_2$ be all classes not listed (or cross-listed) as CSC.\\

Note that these two sets of classes do not overlap since no class can both be listed and not listed as CSC. So their intersection is empty.\\

Meanwhile, every class you could enroll in at Grinnell this semester is either listed as CSC or not listed as CSC. So clearly their union is the entire original set $T$.\\

Something to be careful with: what if we defined $S_1$ as CSC classes and $S_2$ as HIS (history) classes? Their intersection might be empty, but their union is not all classes! So not a partition.\\

Another thing to be careful with: what if we defined $S_1$ as CSC classes and $S_2$ as MAT (math) classes? We would need to be careful when discussing cross-listed classes, because technically CSC-208 is also MAT-208, and so their intersection is not empty!\\

And finally, note that I have not been very careful with my example. When defining the sets as all classes listed (or cross-listed) as CSC, I did not specify that they were classes being offered this semester. So while CSC-213 is a CSC class that would be in set $S_1$, it would not be in $T$ since you cannot enroll in it this semester. So technically, my example is wrong because $S_1\cup S_2$ is not a subset of $T$, and therefore not equal to $T$...\\

\item So what is a partition? Basically, we take a set of things and split it into two subgroups. These groups cannot overlap, but all of the original things must be in one group or the other.\\

We \textit{partition} the set, in the same sense that we think of when we use the English word ``partition.'' This is just a formal/mathematical definition for that word!
\end{enumerate}

\newpage

\section*{Problem 3: The Other Side}

Consider the following claim
\[
\bar{A}\cap\bar{B}\subseteq\overline{A\cup B}.
\]
To prove this claim, start by considering an element $x\in\bar{A}\cap\bar{B}$. We need to show that this means that $x\in\overline{A\cup B}$.\\

Since $x\in\bar{A}\cap\bar{B}$, we know that $x\in\bar{A}$ and $x\in\bar{B}$ by the definition of set intersection. These facts then tell us that $x\notin A$ and $x\notin B$ by the definition of set complement. But this means that $x$ is not in either $A$ or $B$, and thus $x\notin A\cup B$. By the definition of set complement, we can now conclude that $x\in\overline{A\cup B}$. Therefore we know that $\bar{A}\cap\bar{B}\subseteq\overline{A\cup B}$.\\

Now we can also prove the other side (from the reading) for the sake of being complete.\\

Consider the following claim
\[
\overline{A\cup B}\subseteq\bar{A}\cap\bar{B}.
\]
To prove this claim, start by considering an element $x\in\overline{A\cup B}$. We need to show that this means that $x\in\bar{A}\cap\bar{B}$.\\

Since $x\in\overline{A\cup B}$, we know that $x\notin A\cup B$ by the definition of set complement. This means that $x$ cannot be in either $A$ or $B$, and so $x\notin A$ and $x\notin B$. But this means that $x\in\bar{A}$ and $x\in\bar{B}$ by the definition of set complement. Since $x$ is in both of these sets, then by the definition of set intersection, we can conclude that $x\in\bar{A}\cap\bar{B}$. Therefore we know that $\overline{A\cup B}\subseteq\bar{A}\cap\bar{B}$.\\

Putting these to facts together, we have shown that 
\[
\bar{A}\cap\bar{B}\subseteq\overline{A\cup B} \quad \text{and} \quad \overline{A\cup B}\subseteq\bar{A}\cap\bar{B}.
\]
Thus we have proved what is known as De Morgan's Law:
\[
\overline{A\cup B}=\bar{A}\cap\bar{B}.
\]

\newpage

\section*{Problem 4: Pivoting to New Things}

Consider the claim from this problem:\\

Let $a\in S$. Define $T_1, T_2\subseteq \mathcal{P}(S)$ as follows:
\begin{itemize}
\item $T_1 = \mathcal{P}(S-\{a\})$.
\item $T_2 = \{\; B\cup\{a\} \;|\; B\in\mathcal{P}(S-\{a\}) \;\}$.
\end{itemize}
$T_1$ and $T_2$ form a partition of $\mathcal{P}(S)$ where $a$ is its \textit{pivot}.\\

\begin{enumerate}
\item Let the set $S = \{1,2,3,4\}$.

\item Now set our pivot element to be $a=3$. \\

Then $S-\{a\} = \{1,2,4\}$, and so 
\[
T_1 = \mathcal{P}(S-\{a\}) = \{\emptyset, \{1\}, \{2\}, \{4\}, \{1,2\}, \{1,4\}, \{2,4\}, \{1,2,4\}\}.
\]

Now consider the definition of $T_2 = \{\; B\cup\{a\} \;|\; B\in\mathcal{P}(S-\{a\}) \;\}$. How to interpret this definition?\\

Note that this is the set of $\{a\}$ union-ed with all sets $B\in\mathcal{P}(S-\{a\})$. But we just listed all of those sets above! So we just have to take all of those sets, and union them with $\{a\}$, i.e., we just add $a=3$ into each of them.\\

This gives us
\[
T_2 = \{\{3\}, \{1,3\}, \{2,3\}, \{3,4\}, \{1,2,3\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\}\}.
\]

\item Note that the power set of $S$ is 
\begin{eqnarray*}
\mathcal{P}(S) &=& \{\;\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\},\{2,3\}, \{2,4\}, \{3,4\}, \\
&\;& \;\;\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\}\;\}.
\end{eqnarray*}
This is indeed the union of $T_1$ and $T_2$ from above, and we also note that $T_1$ and $T_2$ don't overlap. So they do form a partition of $\mathcal{P}(S)$. But why?\\

Note something interesting about $T_1$ and $T_2$: they are both sets of subsets of $S$ (and are therefore both subsets of $\mathcal{P}(S)$ as we need). But, if we look closely at them, we can see an important fact:
\begin{itemize}
\item $T_1$ is the set of all subsets of $S$ \textbf{that do not contain $a$}. (here $a=3$)
\item $T_2$ is the set of all subsets of $S$ \textbf{that do contain $a$}. (here $a=3$)
\end{itemize}
We can actually see this from their definitions. $T_1$ is the power set of $S-\{a\}$, i.e., is the set of all subsets of $S-\{a\}$, which is the set of all sets of elements containing elements of $S$ that are not $a$.\\

Meanwhile $T_2$ is the set of all $B\cup\{a\}$ where $B$ is a set in $T_1$. So $B$ is any subset of $S$ that does not contain $a$. So what is $B\cup\{a\}$? It is a subset of $S$ that now contains $a$ - we just added $a$ to the subsets that didn't contain it!\\

Clearly the set of all subsets of $S$ that contain $a$ and the set of all subsets of $S$ that do not contain $a$ form a partition of the set of all subsets of $S$: they cannot overlap since no set can both contain and not contain $a$, and together they form the full power set of $S$ since all subsets of $S$ must either contain or not contain $a$. This will be the key idea to our proof.\\

\item Technically, to formally prove that $T_1$ and $T_2$ form a partition of $\mathcal{P}(S)$, we would need to prove both that $T_1\cap T_2=\emptyset$ and that $T_1\cup T_2=\mathcal{P}(S)$.\\

You will prove $T_1\cap T_2=\emptyset$ in Demo 4.\\

To prove $T_1\cup T_2=\mathcal{P}(S)$, we must prove both $T_1\cup T_2\subseteq\mathcal{P}(S)$ and $\mathcal{P}(S)\subseteq T_1\cup T_2.$\\

You will prove $T_1\cup T_2\subseteq\mathcal{P}(S)$ in Demo 4.\\

So let's consider the claim that $\mathcal{P}(S)\subseteq T_1\cup T_2$.\\

(Note: everything inside parentheses is my commentary, and is not part of the proof.)\\

(We are trying to prove that one set, $\mathcal{P}(S)$, is a subset of another, $T_1\cup T_2$. So we will proceed as we usually do. We will show that any element in $\mathcal{P}(S)$ must also be an element of $T_1\cup T_2$. The trick now is that each element of $\mathcal{P}(S)$ is actually a set.)\\

Let the set $X\in\mathcal{P}(S)$. By the definition of the power set, this means that $X\subseteq S$. By the definition of a subset, we can now see that $X$ is a set that must contain only elements that are contained in $S$, i.e., $\forall y. y\in X\rightarrow y\in S$.\\

Now let's consider a special element: our pivot value $a$. We appeal to the Law of the Excluded Middle: it must be the case that either $a\in X$ or $a\notin X$. We will now perform a case analysis on these two options!\\

(Let's actually start with $a\notin X$. Note: the order doesn't matter here, but this makes the proof clearer to follow since we will reason about $T_1$ first.)

\newpage

(Our goal going forward with this proof will be to somehow show that $X$ is in $T_1$ or $X$ is in $T_2$. Since $X$ is a set, we will need to consider an element $y \in X$, and reason about that element.)

\begin{itemize}
\item Case 1: $a\notin X$.\\

(Note that this case is related to $T_1$, the set of all subsets of $S$ that do not contain $a$. We are going to show that $X\in T_1$ here. How? $T_1 = \mathcal{P}(S-\{a\})$, so we will need to show that $X\subseteq S-\{a\}$ to show that it is in the power set.)\\

In this case, we want to reason about some element $y\in X$. We know two facts about $y$. First, we know that $y\neq a$ since $a\notin X$. Second, we know that $y\in S$, since $\forall y. y\in X\rightarrow y\in S$.\\

But since $y\neq a$, we can say that $y\notin\{a\}$, since $\{a\}$ is the set of just the single element $a$, and $y$ is not that element.\\

So we now know that $y\in S$ and $y\notin\{a\}$. By the definition of set difference, we can conclude that $y\in S-\{a\}$.\\

But this means that if $a\notin X$, then for all $y\in X$, we can see that $y\in S-\{a\}$. By the definition of a subset, we now know that $X\subseteq S-\{a\}$.\\

But by the definition of the power set, we now know that $X\in\mathcal{P}(S-\{a\})=T_1$.\\

Finally, by the definition of the union, we can say that $X\in T_1\cup T_2$.\\

\item Case 2: $a\in X$.\\

(Note that now we are going to reason about $T_2$ since we now are including $a$. Our idea here is to show that for each $y\in X$, then either $y\in\{a\}$ or $y\in S-\{a\}$. This will be a bit tricky. The basic idea is to ask whether $y=a$ or $y\neq a$, and reason from there. The first case gives us $y\in\{a\}$, and the second will give us $y\in S-\{a\}$ since $y\in S$. Since we show that $y\in\{a\}$ or $y\in S-\{a\}$, we know that $X\in T_2$.)\\

In this case, we want to reason about some element $y\in X$. All we know now is that $y\in S$, since $\forall y. y\in X\rightarrow y\in S$.\\

But by the Law of the Excluded Middle, either $y=a$ or $y\neq a$. We need another case analysis!\\
\begin{itemize}
\item Consider the case where $y=a$. Then clearly $y\in\{a\}$, and so $y\in\{a\}$ or $y\in B$ for any set $B$ (by $\vee$-intro). By the definition of union, we can see that $y\in B \cup \{a\}$ for any set $B$, and hence $y\in B \cup \{a\}$ when $B$ is any particular set, like $B\in\mathcal{P}(S-\{a\})$ for instance. But this means that $X\in T_2$ in this case.\\

\item  Now consider the case where $y\neq a$. This means that $y\notin\{a\}$. But we know that $y\in S$. Thus $y\in S-\{a\}$. Now by the definition of the power set, we know that $y\in B$ for some $B\in\mathcal{P}(S-\{a\})$. But that means that $y\in B$ for some $B\in\mathcal{P}(S-\{a\})$ or $y\in\{a\}$ (again an $\vee$-intro). So $y\in B \cup \{a\}$ where $B\in\mathcal{P}(S-\{a\})$, and thus $X\in T_2$ in this case.\\
\end{itemize}

In either case, we can conclude that $X\in T_2$.\\

Finally, by the definition of the union, we can again conclude that $X\in T_1\cup T_2$.\\
\end{itemize}

In either case, we showed that $X\in T_1\cup T_2$. Thus for any $X\in\mathcal{P}(S)$, it must be that $X\in T_1\cup T_2$. Therefore we can conclude that $\mathcal{P}(S)\subseteq X\in T_1\cup T_2$.\\
\end{enumerate}

Wow, that was a long proof! But note: everything we did was just using the principals of natural deduction along with the definitions of the set operations. It sometimes just takes some work...\\

\newpage

\textbf{Aside about Problem 4's Proof:}\\

As a final note about this problem: we used the Law of the Excluded Middle to give us the fact that $a\in X\vee a\notin X$. We then did an $\vee$-elim in our case analysis.\\

In Case 1 where $a\notin X$, we showed that this meant $X\in T_1$. We then used $\vee$-intro to say that $X\in T_1$ or $X\in T_2$, and so $X\in T_1\cup T_2$.\\

In Case 2, we again appealed to the Law of the Excluded Middle to say that $y=a\vee y\neq a$. We did an $\vee$-elim on those sub-cases. In each sub-case, we ended up using an $\vee$-intro to conclude that $y\in B\cup\{a\}$ where $B\in\mathcal{P}(S-\{a\})$. This let us conclude that $X\in T_2$ in either case, completing that $\vee$-elim. We then used an $\vee$-intro to say that $X\in T_1$ or $X\in T_2$, and so $X\in T_1\cup T_2$.\\

We saw that $X\in T_1\cup T_2$ in either Case 1 or Case 2, and completed our $\vee$-elim.\\

The basic outline of the proof was:
\begin{enumerate}[noitemsep, label=(\arabic*)]
\item $X\in\mathcal{P}(S)$ [given]
\item $a\notin X \vee a\in X$ [Law of the Excluded Middle]\\

    {\setlength\itemindent{15pt}\item $a\notin X$ [assume Case 1]}
    {\setlength\itemindent{15pt}\item $X\in T_1$ [ends up getting proved from 1 and 3]}
    {\setlength\itemindent{15pt}\item $X\in T_1\vee X\in T_2$ [$\vee$-intro 4]\\}
    
    {\setlength\itemindent{15pt}\item $a\in X$ [assume Case 2]}
    {\setlength\itemindent{15pt}\item $y=a \vee y\neq a$ [Law of the Excluded Middle]\\}
    
        {\setlength\itemindent{30pt}\item $y=a$ [assume for $\vee$-elim 7]}
        {\setlength\itemindent{30pt}\item $X\in T_2$ [ends up getting proved from 1, 6, and 8]\\}
        
        {\setlength\itemindent{30pt}\item $y\neq a$ [assume for $\vee$-elim 7]}
        {\setlength\itemindent{30pt}\item $X\in T_2$ [ends up getting proved from 1, 6, and 10]\\}
        
    {\setlength\itemindent{15pt}\item $X\in T_2$ [$\vee$-elim 7, 8-9, 10-11]}
    {\setlength\itemindent{15pt}\item $X\in T_1 \vee X\in T_2$ [$\vee$-intro 12]\\}
    
\item $X\in T_1 \vee X\in T_2$ [$\vee$-elim 2, 3-5, 4-13]
\end{enumerate}

Can you see how this mimics the structure of the proof itself? Can you see how lines 3-5 correspond to Case 1 in the proof, and lines 6-13 correspond to Case 2 in the proof?

\newpage

\section*{Problem 5: Double the Practice Makes Perfect}

\begin{enumerate}
\item Consider the following Absorption Claim (Union Absorbs Intersection):
\[
A \cup (A \cap B) = A.
\]
To prove the equality of two sets, we must prove double containment. So we must prove that both $A \cup (A \cap B) \subseteq A$ and $A \subseteq A \cup (A \cap B)$.
\begin{itemize}
\item Consider the claim that $A \cup (A \cap B) \subseteq A$.\\

Let $x\in A \cup (A \cap B)$. Then it must be the case that $x\in A$ or $x\in A\cap B$. But if $x\in A\cap B$, then $x\in A$ and $x\in B$. So either way, we know that $x \in A$. Thus $A \cup (A \cap B) \subseteq A$.\\

\item Consider the claim that $A \subseteq A \cup (A \cap B)$.\\

Let $x\in A$. Then it is certainly true that $x\in A \vee x\in S$ where $S$ can be any set, since we already know that $x \in A$. Because $S$ can be whatever set we want, we can now say that $x\in A$ or $x\in A\cap B$. This means that $x\in A\cup (A\cap B)$, and thus $A \subseteq A \cup (A \cap B)$.
\end{itemize}

We have proved double containment, and therefore can conclude that $A \cup (A \cap B) = A$.\\

\item Consider the following Claim about the Distribution Property of Set Difference:
\[
(A-B)-C = A-(B\cup C).
\]
Again, we must prove double containment.
\begin{itemize}
\item Consider the claim that $(A-B)-C \subseteq A-(B\cup C)$.\\

Let $x\in (A-B)-C$. This means that $x\in A-B$ and $x\notin C$, which tells us that $x\in A$ and $x\notin B$ and $x\notin C$. So it is the case that $x$ is not in either $B$ or $C$, and thus $x\notin B\cup C$. Since $x\in A$ but $x\notin B\cup C$, we can conclude that $x\in A-(B\cup C)$. Thus $(A-B)-C \subseteq A-(B\cup C)$.\\

\item Consider the claim that $A-(B\cup C)\subseteq(A-B)-C$.\\

Let $x\in A-(B\cup C)$. This means that $x\in A$ and $x\notin B\cup C$. Since $x\notin B\cup C$, it must be the case that $x$ is not in either $B$ or $C$. So $x\notin B$ and $x\notin C$. Since $x\in A$ and $x\notin B$, we know that $x\in A-B$. But now since $x\in A-B$ and $x\notin C$, we can conclude that $x\in (A-B)-C$. Thus $A-(B\cup C)\subseteq(A-B)-C$.\\
\end{itemize}

We have proved double containment, and therefore $(A-B)-C = A-(B\cup C)$.\\
\end{enumerate}

\end{document}