\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\operatorname{Var}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\PP}{\mathcal{P}}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 2100 / 2350 -- Homework 6 (Last one!)}
\author{
Fall 2020\\[10pt]
due \textbf{\underline{Monday}}, \textbf{November 23},
\underline{on D2L, by the beginning of class}\\[10pt]
$\approx$ Sections 3.3, 4.1, 4.2, 4.3
}
\date{}
\begin{document}
\maketitle
\begin{center}
\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}
\textbf{Instructions:} This assignment is due on D2L at the \emph{beginning} of class. It must be typed in Latex (other formats such as Word are not acceptable). \textbf{You must submit the .pdf file, but you do not have to submit the .tex file unless I ask for it} Any pictures can be drawn by hand and added to the Latex file with the ``$\backslash$includegraphics'' command (see how I do it in this document). Please write the questions in the correct order. Explain all reasoning.
\textbf{Note:} \emph{\underline{You no longer need to include your scratch work with each proof.}}
\begin{enumerate}
\item Prove or disprove: For any two sets $A$ and $B$: $\PP(A) \cup \PP(B) \subseteq \PP(A \cup B)$.
% \item Prove or disprove: For any three sets $A$, $B$, and $C$: $(A \cap B) \times C = (A \times C) \cap (B \times C)$.
\item Prove the following set inequality:
\[
(\{6k + 1 : k \in \Z\} \cup \{6m - 1: m \in \Z\}) \subseteq \{2n+1 : n \in \Z\}.
\]
\item Draw the two-sided arrow diagram for the function $f : \PP(\{4,5,6\}) \to \PP(\{1,2,3\})$ defined by
\[
f(S) = \{x-3:x\in S\} \smallsetminus \{2\}.
\]
\item Prove that the function $h : \N \to \N$ defined by $h(n) = $ [the sum of the digits in $n$ (in base 10)] is surjective. Prove that it's not injective.
\item Let $c : \PP(\{x,y,z\}) \to \PP(\{x,y,z\})$ be the function with the rule $c(A) = \{x,y,z\} \smallsetminus A$, and let $n : \PP(\{x,y,z\}) \to \{0,1,2,3\}$ be the function such that $n(A)$ is the number of elements in the set $A$. Which composition makes sense, $c \circ n$ or $n \circ c$? For the one that is defined, give the domain, codomain, range, and draw the two-sided arrow diagram.
\item Let $A = \{0,1,2,3\}$ and let $B = \{000,001,010,011,100,101,110,111\}$ be the set of binary strings with three digits. Define $g : B \to A$ by $g(s) = $ [the number of $1$s in $s$]. Draw the arrow diagram for the function. Determine whether or not it's injective, surjective, and bijective. Make sure to justify your answers (either with the arrow diagram, or a formal proof).
\end{enumerate}
\end{document}