\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} 
\subsection*{Week 9 at a glance}

\subsubsection*{We will be learning and practicing to:}
\begin{itemize}

\item Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
\begin{itemize}
    \item Defining important sets of numbers, e.g. set of integers, set of rational numbers
    \item Classifying sets into: finite sets, countably infinite sets, uncountable sets
    \item Defining functions, predicates, and binary relations using multiple representations
    \item Determining whether a given binary relation is symmetric, antisymmetric, reflexive, and/or transitive
    \item Determining whether a given binary relation is an equivalence relation and/or a partial order
\end{itemize}

\item Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
\begin{itemize}
    \item Using the definitions of the div and mod operators on integers
    \item Using divisibility and primality predicates
    \item Applying the definition of congruence modulo n and modular arithmetic
\end{itemize}

\item Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
\begin{itemize}
    \item Using proofs as knowledge discovery tools to decide whether a statement is true or false
\end{itemize}
\end{itemize}

\subsubsection*{TODO:}
\begin{list}
   {\itemsep2pt}
    \item Review quiz based on Week 8 class material (due Monday 03/02/2026)
    \item Test 2 Attempt 1 in the CBTF this week at your scheduled time.
    \item Review quiz based on Week 9 class material (due Monday 03/09/2026)

\end{list}

\newpage
\section*{Week 9 Monday: Cardlinality and binary relations}

\subsection*{Cardinality of sets: recap}



The set of positive integers $\mathbb{Z}^{+}$ is countably infinite.

The set of integers $\mathbb{Z}$ is countably infinite and is a proper superset of $\mathbb{Z}^{+}$. 
In fact, the set difference 
$$\mathbb{Z} \setminus \mathbb{Z}^{+} = \{ x \in \mathbb{Z} \mid x \notin \mathbb{Z}^+\} 
= \{ x \in \mathbb{Z} \mid x \leq 0 \}$$ is countably infinite.

The set of rationals 
$\mathbb{Q} = \left\{ \frac{p}{q} \mid p \in \mathbb{Z}  \text{ and  } 
q  \in \mathbb{Z} \text{ and } q \neq  0 \right\}$ is countably infinite.


The set of real numbers $\mathbb{R}$ is uncountable. In fact, the closed 
interval $\{x \in \mathbb{R} ~|~ 0 \leq x \leq 1\}$, 
any other nonempty closed interval of real numbers whose endpoints are 
unequal, as well as the related intervals that exclude one or both of the endpoints are
each uncountable.
The set of {\bf irrational} numbers $\overline{\mathbb{Q}} = \mathbb{R} - \mathbb{Q}
= \{ x \in \mathbb{R} \mid x \notin \mathbb{Q} \}$ is uncountable.

\vfill

We can classify any set as 
\begin{itemize}
\item {\bf Finite} size. Fact: For each positive number $n$, for any sets $X$ and $Y$ each 
size $n$, there is a bijection between $X$ and $Y$.
\item {\bf Countably Infinite}. Fact: for any countably infinite sets $X$ and $Y$, there is a bijection
between $X$ and $Y$.
\item {\bf Uncountable}. Examples: $\mathcal{P}(\mathbb{N})$, the power set of any infinite set, 
the set of real numbers, any nonempty interval of real numbers. Fact: there are (many) examples 
of uncountable sets that do not have a bijection between them.
\end{itemize} \newpage


{\bf True or False}?  For all sets $A$ and $B$ where  $A \subseteq B$, 
if $A$ is infinite then $B$ is finite.

\vfill

{\bf True or False}?   For all sets $A$ and $B$ where  $A \subseteq B$, 
if $A$ is countable then $B$ is countable.

\vfill

{\bf True or False}?   For all sets $A$ and $B$ where  $A \subseteq B$, 
if $B$ is infinite then $A$ is finite.

\vfill

{\bf True or False}?   For all sets $A$ and $B$ where  $A \subseteq B$, 
if $B$ is uncountable then $A$ is countable.

\vfill \newpage

\newpage
\subsection*{Binary relations}


{\bf Definition}: When $A$ and $B$ are sets, we say any subset of $A \times B$ is a {\bf binary relation}. 
A relation $R$ can also be represented as

\begin{itemize}
\item A function $f_{TF} : A \times B \to \{T, F\}$
where, for $a \in A$ and $b \in B$, $f_{TF}(~(a,b)~) = 
\begin{cases} 
    T \qquad&\text{when } (a,b) \in R \\
    F \qquad&\text{when } (a,b) \notin R
\end{cases}$
\item A function $f_{\mathcal{P}} : A   \to \mathcal{P}(B)$ where, for $a \in A$, 
$f_{\mathcal{P}}( a ) = \{ b \in B ~|~ (a,b) \in R \}$
\end{itemize}

When $A$ is a set, we say any subset of $A \times A$ is a (binary) {\bf relation} on $A$.

 \vfill


For relation $R$ on a set $A$, we can represent this relation as a
{\bf graph}: a collection of nodes (vertices) and edges (arrows). The 
nodes of the graph are the elements of $A$ and 
there is an edge from $a$ to $b$ exactly when $(a,b) \in R$.
 \vfill
\newpage


{\it Example}: For $A = \mathcal{P}(\mathbb{R})$, we can define the relation $EQ_{\mathbb{R}}$ on $A$ as 
\[
\{ (X_1, X_2 ) \in\mathcal{P}(\mathbb{R})  \times \mathcal{P}(\mathbb{R}) ~|~ |X_1| = |X_2| \}
\]

\vfill

{\it Example}: Let $R_{(\textbf{mod } n)}$ be the set of all pairs of integers $(a, b)$ such that $(a \textbf{ mod } n = b \textbf{ mod } n)$.
Then $a$ is {\bf congruent to} $b$ \textbf{mod} $n$ means $(a, b) \in R_{(\textbf{mod } n)}$. A common notation is to write this as $a \equiv b (\textbf{mod } n)$.


$R_{(\textbf{mod } n)}$ is a relation on the set $\underline{\phantom{\mathbb{Z}}\hspace{20em}}$


Some example elements of $R_{(\textbf{mod } 4)}$ are: 

\vfill \newpage
\section*{Week 9 Wednesday: Binary relations definitions and representations}
\subsection*{Properties of binary relations}


A relation $R$ on a set $A$ is called {\bf reflexive} 
means $(a, a) \in R$ for every element $a \in A$. 
 

{\it Informally}, every element is related to itself.

{\it Graphically}, there are self-loops (edge from a node back to itself) at 
every node. \vfill


A relation $R$ on a set $A$ is called {\bf symmetric} means 
$(b, a) \in R$ whenever $(a, b) \in R$, for all $a, b \in A$. 
 

{\it Informally}, order doesn't matter for this relation.

{\it Graphically}, every edge has a paired ``backwards'' edge so we might
as well drop the arrows and think of edges as undirected. \vfill


A relation $R$ on a set $A$ is called {\bf transitive} means 
whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$, for all $a, b, c \in A$.
 

{\it Informally}, chains of relations collapse.

{\it Graphically}, there's a shortcut between any endpoints of a chain of 
edges. \vfill


A relation $R$ on a set $A$ is called {\bf antisymmetric} means 
$\forall a \in A ~\forall b \in A~\left(~\left( ~(a,b) \in R \land (b,a) \in R ~\right) \to a=b~\right)$
 

{\it Informally}, the relation has directionality.

{\it Graphically}, can organize the nodes of the graph so that 
all non-self loop edges go up. \vfill
\newpage



When the domain is $\{ a,b,c,d,e,f,g,h\}$ define a relation that is {\bf not reflexive} and 
is {\bf not symmetric} and is {\bf not transitive}.

\vfill

When the domain is $\{ a,b,c,d,e,f,g,h\}$ define a relation that is {\bf not reflexive} but 
is {\bf symmetric} and is {\bf transitive}.

\vfill

When the domain is $\{ a,b,c,d,e,f,g,h\}$ define a relation that is {\bf symmetric} and
is {\bf antisymmetric}.

\vfill

Is the relation $EQ_{\mathbb{R}}$ reflexive? symmetric? transitive? antisymmetric?

\vfill

Is the relation $R_{(\textbf{mod } 4)}$ reflexive? symmetric? transitive? antisymmetric?

\vfill
%
 \vfill

\newpage
\subsection*{Definitions and representations}


A relation is an {\bf equivalence relation} means it is reflexive, symmetric, and transitive. 


{\it Example}: For $A = \mathcal{P}(\mathbb{R})$, the relation $EQ_{\mathbb{R}}$ defined on $A$ as 
\[
\{ (X_1, X_2 ) \in\mathcal{P}(\mathbb{R})  \times \mathcal{P}(\mathbb{R}) ~|~ |X_1| = |X_2| \}
\]
is an equivalence relation.

\vfill

{\it Example}: For $A = \mathbb{Z}$, for each positive integer $n$, the relation $R_{(\textbf{mod } n)}$ defined as the set of ordered pairs $(a, b)$ such that $(a \textbf{ mod } n = b \textbf{ mod } n)$ is an equivalence relation.
\vfill 

A relation is a {\bf partial ordering} (or partial order) means 
it is reflexive, antisymmetric, and transitive. {\it Summary}: binary relations can be useful for organizing elements in a domain. 
Some binary relations have special properties that make them act like some familiar relations.
Equivalence relations (reflexive, symmetric, transitive binary relations) ``act like'' equals.
Partial orders (reflexive, antisymmetric, transitive binary relations) ``act like'' less than or equals to.


For a partial ordering, its {\bf Hasse diagram} is a graph representing the 
relationship between elements in the ordering. The nodes (vertices) of the graph 
are the elements of the 
domain of the binary relation. The edges do not have arrow heads. The
directionality of the partial order is indicated by 
the arrangements of the nodes. The nodes are arranged so that nodes connected to nodes
above them by edges indicate that the relation holds between the 
lower node and the higher node. 
Moreover, the diagram omits self-loops and 
omits edges that are guaranteed by transitivity.
 \vfill


Draw the Hasse diagram of the partial order on the set $\{a,b,c,d,e,f,g\}$ defined as
\begin{align*}
    \{  &(a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (g,g), \\
        &(a,c), (a,d), (d,g), (a,g), (b,f), (b,e), (e,g), (b,g) \}
\end{align*}

\vspace{100pt}

%
 \vfill
\newpage
\section*{Week 9 Friday: Equivalence relations applications}


A {\bf partition} of a set $A$ is a set of non-empty, disjoint subsets 
$A_1, A_2, \cdots, A_n$ such that 
\[
    A = \bigcup_{i=1}^{n} A_i = \{ x \mid \exists i (x \in A_i) \}
\] 

An {\bf equivalence class} of an element $a \in A$ 
with respect to an equivalence relation $R$ on the set $A$ is the set 
\[
    \{s \in A \mid (a, s) \in R \}
\] 
We write $[a]_R$ for this set, which is the equivalence class of $a$ with respect to $R$. 

{\it Recall}: We say $a$ is {\bf congruent to} $b$ \textbf{mod} $n$ 
means $(a, b) \in R_{(\textbf{mod } n)}$. 
A common notation is to write this as $a \equiv b (\textbf{mod } n)$.

We can partition the set of integers using equivalence classes of  $R_{(\textbf{mod } 4)}$

\begin{align*}
    [0]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 0 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 0 \textbf{ mod } 4 = 0 \} = \{ 4c \mid c \in \mathbb{Z}\} }\\
    [1]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 1 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 1 \textbf{ mod } 4 = 1 \} = \{ 4c+1 \mid c \in \mathbb{Z}\} }\\
    [2]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 2 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 2 \textbf{ mod } 4 = 0 \} = \{ 4c+2 \mid c \in \mathbb{Z}\} }\\
    [3]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 3 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 3 \textbf{ mod } 4 = 3 \} = \{ 4c+3 \mid c \in \mathbb{Z}\} }\\
    [4]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 4 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 4 \textbf{ mod } 4 = 0 \} = \{ 4c \mid c \in \mathbb{Z}\} }\\
    [5]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv 5 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = 5 \textbf{ mod } 4 = 1 \} = \{ 4c+1 \mid c \in \mathbb{Z}\} }\\
    [-1]_{R_{(\textbf{mod } 4)}} &= \phantom{ \{ x \in \mathbb{Z} \mid x \equiv -1 ((\textbf{mod } 4)) \} 
    = \{ x \in \mathbb{Z} \mid x \textbf{ mod } 4 = -1 \textbf{ mod } 4 = 3 \} = \{ 4c+3 \mid c \in \mathbb{Z}\} }
\end{align*}
\[
\mathbb{Z} =  [0]_{R_{(\textbf{mod } 4)}}~ \cup ~[1]_{R_{(\textbf{mod } 4)}} ~\cup~[2]_{R_{(\textbf{mod } 4)}}~\cup~
[3]_{R_{(\textbf{mod } 4)}}
\]





 \vfill


Integers are useful because they can be used to encode other objects
and have multiple representations. However, infinite sets are sometimes
expensive to work with computationally. Reducing our attention to 
a {\it partition of the integers} based on congrunce mod $n$, where
each part is represented by a (not too large) integer gives a useful 
compromise where many algebraic properties of the integers are preserved, 
and we also get the benefits of a finite domain. Moreover, modular arithmetic
is well-suited to model any cyclic behavior. \vfill
\newpage

{\bf Fact}: When $R$ is an equivalence relation on a nonempty set $A$, 
the collection of equivalence classes of $R$ is a partition of $A$.

Also, given a partition $P$ of $A$, the relation $R_P$ on $A$ given by 
\[
    R_P = \{ (x,y) \in A \times A ~|~ \text{$x$ and $y$ are in the same part of the partition $P$}\}
\]
is an equivalence relation on $A$. 



{\bf Claim}: For each  $a \in U$, $[a]_{E}  \neq  \emptyset$.

{\bf Proof}: Towards a $\underline{\phantom{\hspace{1.3in}}}$ 
consider an arbitrary element $a$ in $U$. 
We will work to show that $[a]_E \neq \emptyset$, namely that $\exists x \in [a]_E$.
By definition of equivalence classes, we can rewrite this goal as 
$$\exists x \in U ~( ~(a,x) \in E~)$$ 
Towards a $\underline{\phantom{\hspace{1.3in}}}$, consider $x = a$, 
an element of $U$ by definition. By $\underline{\phantom{\hspace{1.3in}}}$ of $E$, 
we know that $(a,a) \in E$  and thus the existential quantification has been proved.\\


{\bf Claim}: For each $a \in U$, there is some $b \in U$  such that $a \in [b]_{E}$.

Towards a $\underline{\phantom{\hspace{1.3in}}}$ 
consider an arbitrary element $a$ in $U$. By definition of equivalence classes, 
we can rewrite the goal as 
$$\exists b \in U ~( ~(b,a) \in E~)$$
Towards a $\underline{\phantom{\hspace{1.3in}}}$, consider $b = a$, 
an element of $U$ by definition. By $\underline{\phantom{\hspace{1.3in}}}$  of $E$, 
we know that $(a,a) \in E$  and thus the existential quantification has been proved. \\
 
{\bf Claim}: For each  $a,b  \in U$ , $(~(a,b)  \in  E ~\to ~ [a]_{E}  = [b]_{E}~)$
and  $(~(a,b)  \notin  E ~\to ~ [a]_{E} \cap[b]_{E} = \emptyset~)$

\phantom{Let $a,b$ be arbitrary. For first goal, assume towards
direct proof that $(a,b) \in E$. To show $[a]_E = [b]_E$ 
first consider arbitrary element $x$ in $[a]_E$. By definition
$(a,x) \in E$ so by symmetry, $(x,a) \in E$ and by 
transitivity with assumption, $(x,b)\in E$. Thus, by definition
of equivalence class, $x \in [b]_E$. Similarly, take arbitrary
element $y \in [b]_E$. By definition $(y,b) \in E$ 
and applying symmetry to assumption, we have $(b,a) \in E$
so by transitivity $(y,a) \in E$ and $y \in[a]_E$, as required
to complete the proof of set equality. For the second goal, 
assume (towards a proof by contrapositive) that $[a]_E \cap [b]_E 
\neq \emptyset$. Then there is a witness $w \in [a]_E \cap [b]_E$.
By definition of equivalence classes $(a,w) \in E$ and $(b,w) \in E$.
By symmetry, we have $(w,b) \in E$ so by transitivity $(a,b) \in E$,
as required.}

\vfill

{\bf Corollary}: Given an equivalence relation $E$ on set $U$,  
$\{ [x]_{E} \mid x \in U  \}$ is a partition of $U$.
\vfill 
\newpage


{\bf Modular arithmetic}: 


{\bf Informally}: can bring mod ``inside" and do it first, for addition and for multiplication.

{\bf Claim}: For $a, b, c, d \in \mathbb{Z}$ 
and positive integer $n$, if $a \equiv b ~(\textbf{ mod } n)$ and $c \equiv d ~(\textbf{ mod } n)$ 
then $a+c \equiv b+d ~(\textbf{ mod } n)$ and $ac \equiv bd ~(\textbf{ mod } n)$.

$123456 \times 789012 \textbf{ mod } 1000 = $

\vfill

Smaller examples work too: 

$(102 + 48) \textbf{ mod } 10 = $ 

$(7 \cdot 10) \textbf{ mod } 5 =$

Let's consider exponentiation: 

$(2^5) \textbf{ mod } 3 = $ 

\vfill

To prove the claim: the following lemma is useful. 

{\bf Lemma}: For $a, b \in \mathbb{Z}$ 
and positive integer $n$, $(a,b) \in R_{(\textbf{mod } n)}$ if and only if  $n | a-b$.

{\bf Proof}: 

\phantom{Consider arbitrary integers $a,b$ and arbitrary positive integer $n$.}

\phantom{Assume $a \textbf{ mod } n = b \textbf{ mod } n$. Call this 
remainder $r$ and we have integers $q_1, q_2$ such that $a = q_1 n + r$
and $b = q_2 n + r$. Calculating $a-b = (q_1 n + r) - (q_2n +r) = (q_1 - q_2)n$ 
an integer multiple of $n$, as required.}

\phantom{Assume there is integer $c$ with $a-b = cn$. By long division 
there are integers $q$ and $r$ ($0 \leq r < n$) with $b = qn + r$. Then 
$a = b + cn = qn+r + cn = (q+c)n + r$. Since long division gives a unique remainder,
this means $a \textbf{ mod } n = r = b \textbf{ mod } n$, as required.}

\vspace{200pt} \vfill
\newpage



Compute the last digit of 
\[
    (42)^{2026}
\]

\vfill

{\it Extra} Describe the pattern that helps you perform this computation 
and prove it using mathematical induction and/or modular arithmetic. 
\end{document}