\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage{enumitem}


\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 2350 -- Homework 6}
\author{
	Fall 2025\\[10pt]
	due Wednesday, \textbf{December 3}, \underline{at the beginning of class}\\[10pt]
	Sections 3.3, 4.1, 4.2
}
\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 at the \emph{beginning} of class. It may be handwritten (as long as I can read it) or typed with software such as Word or Latex. Please write the questions in the correct order. Explain all reasoning.

\hrulefill

\underline{You are no longer required to show your scratch work. However, doing scratch work on another paper}\\ \underline{before trying to write your proof is still the way to succeed on these problems!}

\begin{enumerate}
	
	\item Prove the following set inequality:
	\[
		(\{n^2 - 1 : n \in \Z\} \cap \{2k : k \in \N\}) \subseteq \{4m:m\in\Z\}.
	\]
	
	\item Prove the following set inequality:
	\[
		(\{6k + 1 : k \in \Z\} \cup \{6m - 1: m \in \Z\}) \subseteq \{2n+1 : n \in \Z\}.
	\]
	
	\item Prove that $\PP(A \cap B) \subseteq \PP(A) \cap \PP(B)$.

	\item Prove that $(A \cup B) \times C = (A \times C) \cup (B \times C)$.
	
%	\item  Use induction to prove that for all $n \geq 0$, if $A$ is a set of size $n$, then the number of subsets of $A$ is $2^n$. (In other words, $|\PP(A)| = 2^{|A|}$.)	

	\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 \begin{enumerate}
		\item Suppose $f : Q \to R$ and $g : R \to S$ are both injective (one-to-one) functions. Prove that $g \circ f : Q \to S$ is injective.
		\item Suppose $f : Q \to R$ and $g : R \to S$ are both surjective (onto) functions. Prove that $g \circ f : Q \to S$ is surjective.
		\item Suppose $f : Q \to R$ and $g : R \to S$ are both bijective functions. Prove that $g \circ f : Q \to S$ is bijective.
	\end{enumerate}
	
	
	
	\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}


