% !TEX program = pdflatex
% ---------------------------------------------------------------------------
\documentclass[10pt,a4paper,english]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{bbm}
\usepackage{mathtools}
\usepackage{physics}
\usepackage{enumitem}
\usepackage{tikz}
\usepackage{xcolor}
\usepackage{fancyvrb}
\usepackage{nth}
\usepackage{multicol}
\usepackage{soul}
\makeatletter
\newcommand*{\rom}[1]{\expandafter\@slowromancap\romannumeral #1@}
\renewcommand{\imath}[0]{ i }
\newcommand{\Natural}[0]{\mathbbm{N}}
\newcommand{\Integer}[0]{\mathbbm{Z}}
\newcommand{\Real}[0]{\mathbbm{R}}
\newcommand{\Rational}[0]{\mathbbm{Q}}
\newcommand{\Complex}[0]{\mathbbm{C}}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\title{CS40 Winter 2021 Homework \#6}
\begin{document}
\maketitle
\paragraph{Notes}
\begin{itemize}
\item
You may work with a partner in order to understand the problems and discuss how to approach them.
If you do so, write clearly on your assignment the name of the student you collaborated with.
\item
Justify your answers!
\item
Please re-read the ``Conduct'' section in the class syllabus.
\item
No late submissions! Turn-in what you have by the deadline.
\end{itemize}
\hrulefill
\paragraph{Definitions}
Given a set $D$ and a set of sets $P=\{A_1,A_2,\ldots\}$ (finite or infinite).
If following conditions hold
\begin{enumerate}[label=\roman*]
\item $P$ is a set of subsets of $D$: $P\subseteq\mathcal{P}(D)$, where $\mathcal{P}(D)$ is the powerset.
\item The partitioning sets are \ul{pair-wise disjoint}: \\$\forall X,Y\in P\; (X\neq Y \to X\cap Y=\emptyset)$.
\item Every element in $D$ must be in some set of the partition: \\$\bigcup\limits_{A\in P} A = A_1\cup A_2\cup\ldots = D$.
\end{enumerate}
then $P$ is a called \ul{partition} of $D$. \\
In other words, a partition is a set of subsets such that all the sets are pair-wise disjoint and their union is $D$.
\paragraph{}
A partition can also be infinite, in which case we define:
\begin{itemize}
\item
An \ul{infinite partition} is a partition with infinitely (countable or uncountable) many sets.
\item
An \ul{infinite partition that consists of infinite sets} is a partition with infinitely (countable or uncountable) many
sets where each set is also infinite (countable or uncountable).
\end{itemize}
Note that when the partition is uncountable, we can not index the sets in the partition using integers!
\dotfill
\pagebreak
\begin{enumerate}
\item
\begin{enumerate}
\item Find $d=\gcd\qty(36,55)$ by the Euclidean algorithm.
\item Use your work in part (a) to find $r,s\in\Integer$ such that $d = 36r+55s$.
\item Use your work in part (b) to solve the equation $36x \equiv 9 \pmod{55}$.
\end{enumerate}
\item
Find the sequence of pseudorandom numbers generated by the linear congruential method with modulus $m = 9$, multiplier $a = 2$, increment $c = 4$, and seed $x_0 = 3$.
\item
State whether each of the following sets is finite, countably infinite, or uncountable.
If countably infinite, give a one-to-one correspondence between the set of positive integers and the given set.
\begin{enumerate}
\item $\{ x \in\Integer : x < 20 \}$.
\item $\{ x \in\Integer : |x| < 20 \}$.
\item The odd negative integers.
\item $\{ x \in\Real : 0 < x < 2 \}$
\item $S = A \times \Integer^+$, where $A = \{ 1, 2 \}$.
\item The set of complex numbers $\Complex$.
\end{enumerate}
\item
Let $d\in\Integer^+$.
The ordered $d$-tuple $(n_1, n_2, \ldots, n_d)$ is called a \emph{lattice point} when
$n_1,n_2,\ldots,n_d$ are all integers ($\in\Integer$).
Show that the set of all lattice points (for the given $d$) is countable.
\item
Prove or disprove
\begin{enumerate}
\item
The set of all finite subsets of $\Integer^+$ is countable.
\item
The set of all finite subsets of $\Real^+$ is countable.
\item
The set of all infinite subsets of $\Integer^+$ is countable.
\item
The set of all functions $f : \Integer^+\to\{0,1\}$ is uncountable.
\end{enumerate}
\item
Show a construction of:
\begin{enumerate}
\item
Three infinite pair-wise disjoint subsets of $\Integer^+$.
\item
An infinite partition of $\Integer^+$ consisting of infinite sets.
\item
A uncountably infinite partition of $\Real$ consisting of countably infinite sets.
[Hint: Consider $\Integer$...]
\end{enumerate}
\item
Does there exist a partition of $\Real$ that is an uncountably infinite partition that consists of uncountably infinite sets?
If so, clearly explain how to construct such a partition, otherwise prove that such a partition can not exist.
\item
In this question you will prove an equivalent (and far cleaner!) definition of infinity: \\
\emph{A set $C$ is infinite iff there exists a bijection from $C$ onto a proper subset of itself, $B\subset C$.}
\begin{enumerate}
\item
Prove one direction: If there exists a bijection from $C$ onto $B\subset C$, then $C$ is infinite.
\item
Prove the converse: If $C$ is infinite, then there exists a bijection from $C$ onto a proper subset of itself.
[Hint: Show that there exists a set $T\subset C$ such that $T$ is countable.
Define a bijection $f:\Natural\to T$ and use $f$ to build a bijection from $C$ to $C\setminus\{a\}$ where $a\in C$.]
\end{enumerate}
\end{enumerate}
\end{document}