\documentclass[10pt]{article}
\usepackage[margin=0.7in,top=0.5in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\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}}
\newpagestyle{main}[\small]{
\headrule
\sethead[\usepage][][]
{}{}{\usepage}
}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 2100 / 2105 / 2350 -- Homework 6 (last one!!!)}
\author{due Wednesday, May 1, at the beginning of class}
\date{}
\begin{document}
\maketitle
\pagestyle{main}
\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. \textbf{Staple your work} together (do not just fold over the corner). Please write the questions in the correct order. If I cannot read your handwriting, you won't receive credit. Explain all reasoning.
\begin{enumerate}
\item Let $f : \PP(\{1,2,3,4\}) \to \PP(\{1,2,3\})$ be defined by $f(A) = A \smallsetminus \{4\}$. 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).
\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).
\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 arrow diagram.
\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 $h : [2, \infty) \to (0,1]$ be the function with the rule $h(x) = \ds\frac{1}{x-1}$. Prove that $h$ is a bijection by proving it is injective and surjective. Then compute $h^{-1}(x)$ and give its domain, codomain, and range.
\item Consider the set $S = \PP(\{1,2,3,4\})$. Define $\Sigma(T)$ to be the sum of the elements in $T$. For example $\Sigma(\{1,3,4\}) = 8$. Define the relation $R = \{(A,B) \in S \times S : \Sigma(A) < \Sigma(B)\}$. Answer the following questions.
\begin{enumerate}
\item Is $R$ reflexive?
\item Is $R$ irreflexive?
\item Is $R$ symmetric?
\item Is $R$ antisymmetric?
\item Is $R$ transitive?
\item Is $R$ a partial order? If so, draw the Hasse diagram.
\end{enumerate}
\item Let $S = [0, 4\pi)$ and define the relation $R = \{(a,b) \in S \times S : \sin(a) = \sin(b)\}$. Answer questions (a) -- (f) from Question 6.
\item Let $A = \{1, 4, 7\}$. Give an example of a relation $R$ on $A$ that is
\begin{enumerate}
\item Transitive and reflexive but not antisymmetric.
\item Antisymmetric and reflexive but not transitive.
\item Antisymmetric and transitive but not reflexive.
\end{enumerate}
\end{enumerate}
\end{document}