\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]


\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 7 Solutions}
\begin{document}
\maketitle

Today we'll revisit some basics of set theory. These statements will be simple but it will give us practice with writing proofs. It is also an opportunity to solidify our fundamentals. We can assume all the axioms of logic (i.e. Chapter 2).

\begin{enumerate}

\item [1.] Let $A, B$ be sets. Prove that $(A\cup B)-(A\cap B)=(A-B)\cup (B-A)$.
\vskip 0.2in
{\bf Solution 1:} First we prove that $(A\cup B)-(A\cap B)\subseteq (A-B)\cup (B-A)$. Suppose that $x\in (A\cup B)-(A\cap B)$. Then $x\in A\cup B$ and $x\notin A\cap B$. In particular, $x\in A\cup B$, so either $x\in A$ or $x\in B$. We consider these two cases separately (with the additional stipulation that $x\notin A\cap B$).

Case 1: If $x\in A$ and $x\notin A\cap B$, then
$$\begin{aligned}
(x\in A) \wedge \sim((x\in A)\wedge (x\in B)) &\equiv (x\in A) \wedge (\sim (x\in A) \vee \sim (x\in B))\\
&\equiv ((x\in A) \wedge \sim (x\in A)) \vee ((x\in A) \wedge \sim(x\in B))
\end{aligned}$$
The first clause is a contradiction, and so we are left with $(x\in A) \wedge \sim(x\in B)$, which implies $x\in A-B$.

Case 2: Suppose $x\in B$. This case is similar to the previous one, with the roles of $A$ and $B$ switched.
\vskip 0.4in
{\bf Solution 2:} 
$$\begin{aligned}
x\in (A\cup B)-(A\cap B) &\equiv (x\in A\cup B) \wedge \sim (x\in A\cap B)\\
&\equiv ((x\in A)\vee(x\in B))\wedge \sim ((x\in A)\wedge (x\in B))\\
&\equiv ((x\in A)\vee(x\in B))\wedge (\sim(x\in A)\vee \sim(x\in B))\\
&\equiv ((x\in A)\vee \sim(x\in A)) \wedge ((x\in A)\vee \sim(x\in B))\\
&\wedge ((x\in B)\vee \sim(x\in A)) \wedge ((x\in B)\vee \sim(x\in B))\\
&\equiv ((x\in A)\vee \sim(x\in B))\wedge ((x\in B)\vee \sim(x\in A))\\
&\equiv (x\in A-B) \wedge (x\in B-A)
\end{aligned}$$
\vskip 0.4in
\item [2.] Let $A,B$ be sets. Prove that $A=(A-B) \cup (A\cap B)$. (Hint: Let $x\in A$. Case 1: $x\in B$. Case 2: $x\notin B$.)
\vskip 0.2in
{\bf Solution 1:} First, we prove that $A\subseteq (A-B) \cup (A\cap B)$. For any $x\in A$, either $x \in B$ or $x\notin B$, so let us address these two cases separately.

Case 1: If $x\in A$ and $x\in B$, then $x\in A\cap B$, and so $x\in (A-B) \cup (A\cap B)$.

Case 2: If $x\in A$ and $x\notin B$, then $x\in A-B$, and so $x\in (A-B) \cup (A\cap B)$.
\vskip 0.2in
Now, we show that $A\supseteq (A-B) \cup (A\cap B)$. Suppose that $x\in (A-B) \cup (A\cap B)$. Then either $x\in A-B$ or $x\in A\cap B$.

Case 1: If $x\in A-B$, then $x\in (A-B) \cup (A\cap B)$

Case 2: If $x\in A\cap B$ then $x\in (A-B) \cup (A\cap B)$.

\vskip 0.4in
{\bf Solution 2:}
$$\begin{aligned}
x\in A &\equiv (x\in A) \wedge (x\in B \vee x\notin B)\\
&\equiv (x\in A \wedge x\in B) \vee (x\in A \wedge x\notin B)\\
&\equiv (x\in A\cap B) \vee (x\in A-B)
\end{aligned}$$
\vskip 0.4in
\item [3.] Prove that $A\times (B\cup C)=(A\times B) \cup (A\times C)$.
\vskip 0.2in
{\bf Solution:} 
$$\begin{aligned}(x,y)\in A\times (B\cup C) &\equiv (x\in A) \wedge (y\in B\cup C)\\
&\equiv (x\in A) \wedge ((y\in B) \vee (y\in C))\\
&\equiv ((x\in A)\wedge (y\in B)) \vee ((x\in A)\wedge (y\in C))\\
&\equiv ((x,y)\in A\times B))\vee ((x,y)\in A\times C)\\
&\equiv (x,y) \in A\times (B\cup C)
\end{aligned}$$
\vskip 0.4in
\item [4.] Let $A,B$ be sets.
\begin{enumerate}
\item Prove that if $A=\emptyset$ or $B=\emptyset$, then $A\times B=\emptyset$.
\vskip 0.1in
{\bf Solution:} Note that, for any $x,y$,
$$(x,y) \in A\times B \equiv (x\in A) \wedge (y\in B)$$
First, suppose that $A=\emptyset$. This means that for any $x$, $x\in A$ is false. Thus, $(x\in A) \wedge (y\in B)$ is false for any $x,y$, and so $A\times B$ is empty. Now suppose that $B=\emptyset$. This means that $y\in B$ is false for any $y$. Thus, $(x\in A) \wedge (y\in B)$ is false for any $x,y$, and so $A\times B$ is empty.
\vskip 0.3in
\item Prove that if $A\times B=\emptyset$, then $A=\emptyset$ or $B=\emptyset$.
\vskip 0.1in
{\bf Solution:} Let's prove the contrapositive. Suppose that $A$ and $B$ are both nonempty. Then $\exists x, x\in A$ and $\exists y, y\in B$. Then $(x, y)\in A\times B$. Thus $A\times B$ is nonempty.
\vskip 0.3in
\end{enumerate}
\item [5.] Let $A, B, C, D$ be sets.
\begin{enumerate}
\item Prove that if $A\subseteq C$ and $D\subseteq B$, then $(A\times B)\cap (C\times D)=A\times D$.
\vskip 0.1in
{\bf Solution:} Suppose that $A\subseteq C$ and $D\subseteq B$. Then
$$\begin{aligned}
(x,y)\in (A\times B)\cap (C\times D) &\equiv ((x,y)\in A\times B) \wedge ((x,y)\in C\times D))\\
&\equiv (x\in A) \wedge (y\in B) \wedge (x\in C)\wedge (y\in D)
\end{aligned}$$
Since $A\subseteq C$, $(x\in A) \wedge (x\in C) \equiv (x\in A)$. Similarly, since $D \subset B$, $(y\in B)\wedge (y\in D)\equiv (y\in D)$. So
$$\begin{aligned}
(x\in A) \wedge (y\in B) \wedge (x\in C)\wedge (y\in D)&\equiv (x\in A) \wedge (y\in D)\\
&\equiv ((x,y)\in A\times D)
\end{aligned}$$
\vskip 0.3in
\item Prove that if $(A\times B)\cap (C\times D)=A\times D$ then $A\subseteq C$ and $D\subseteq B$.
\vskip 0.1in
{\bf Solution:} As before,
$$\begin{aligned}
(x,y)\in (A\times B)\cap (C\times D) &\equiv (x\in A) \wedge (y\in B) \wedge (x\in C)\wedge (y\in D)\\
&\equiv (x\in A\cap C) \wedge (y\in B\cap D)\\
&\equiv ((x,y)\in (A\cap C)\times (B\cap D))
\end{aligned}$$
The assumption therefore gives us that $A=A\cap C$ and $D=B\cap D$. This implies that $A\subseteq C$ and $D\subseteq B$.\footnote{This is, given a basic statement about sets which one can prove:
$$A=A\cap C \iff A\subseteq C$$
This is a basic property which you can prove as an exercise, and which we assume going forward.}
\end{enumerate}

\end{enumerate}
\end{document}