\documentclass[11pt]{article} %
\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\newcommand{\cP}{{\cal P}}
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\R}{{\bf R}}
\newcommand{\Q}{{\bf Q}}
\newcommand{\points}[1]{{\it (#1 Points)}}
\newcommand{\tpoints}[1]{{\bf #1 Total points.}}
\begin{document}
\noindent
{\bf Math 214 -- Foundations of Mathematics\hfill
Homework 3}
\begin{enumerate}
\item (5 points) Let $A, B, C$ be sets. Prove that $(A-B)\cup (A-C)=A-(B\cap C)$.
Hint: You may use one of the following three approaches.
\begin{itemize}
\item[a)]
Write
$(A-B) \cup (A-C)
= \{x \in U: p(x)\}$, where $p(x): x \in (A-B) \hbox{ or } x \in (A-C)$,
and
$A-(B\cap C) = \{x \in U: q(x)\}$, where $q(x):
x \in A$ and $x \notin (B\cap C)$,
where $U$ is the universal set.
Show that $p(x)$ and $q(x)$ are logically equivalent.
\item[
b)] Show that if $x \in (A-B) \cup (A-C)$, then $x \in A-(B\cap C)$.
Also, show that if $x \in A - (B\cap C)$, then $x \in (A-B)\cup (A-C)$.
\item[
c)] Use set operations such as $A - X \subseteq A - Y$ if $Y\subseteq X$,
to argue $(A-B)\cup (A-C)\subseteq A-(B\cap C)$ and also
$A-(B\cap C) \subseteq (A-B)\cup (A-C)$.
\end{itemize}
\item (5 points) Let $A, B, C$ and $D$ be sets. Prove that
\[
(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D).
\]
Hint: Show that (a) if $(x,y) \in (A\times B)\cap (C\times D)$, then
$(x,y) \in (A\cap C)\times (B\cap D),$ and
(b) if
$(x,y) \in (A\cap C)\times (B\cap D)$, then $(x,y) \in (A\times B)\cap (C\times D)$.
\item (5 points) For the following, state whether they are true or not. Then, prove your answer.
\begin{enumerate}
\item $\forall x\in \R, \exists y\in \R, xy=1$;
\item $\exists n \in \N, \exists m \in (\N - \{1\}), nm=1$.
\end{enumerate}
Hint: If you want to prove that $P$ is FALSE, you may try to prove $\sim P$ is TRUE.
\item (5 points) Show that for any two positive numbers $a$ and $b$,
$$(a+b)\left(\frac{1}{a} + \frac{1}{b}\right) \ge 4.$$
Hint: Reduce the problem to $(a+b)^2 \ge 4ab$, and use algebra.
\item (5 points) Let $m = 4s+2$ with $s \in \Z$. Show that there are no
integers $x, y$ such that $$x^2 - y^2 = m.$$
Hint: Consider 4 cases according to $x, y$ are even or odd.
\item (5 points) Prove that the product of an irrational number
and a nonzero rational number is irrational.
Hint: Assume that $x$ is irrational and $y$ is nonzero rational.
If $xy$ is rational, then ...
\item (5 points)
Let $S = \{a,b,c\} \subseteq \Z$. For any non-empty subset $X$ of $S$,
let $s(X)$ be the sum of elements in $X$.
Show that there are non-empty subsets $A, B$ of $S$
such that $s(A) - s(B)$ is divisible by 6.
Hint: For each non-empty subset $X$ of $S$,
consider the remainder of $s(X)$ divided by $6$.
\item (Extra Credit, 5 points) Recall that for a given $S \subseteq \R$,
the maximum element of $S$, denoted by $\max S$,
is the number $\alpha \in S$ such that
$\alpha \geq \beta$ for all $\beta \in S$.
Let $A = \{n \in \N: \sqrt{n} \not\in \Q\}$. Show that $\max A$ does not exist.
[Hint: First, use Problem 6 to deduce that $2m^2 \in A$ for any positive integer $m$.
Then use this fact to argue that $A$ has no maximum element.]
\end{enumerate}
\end{document}