\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{4, Mon.}                    % !! start the paper

\section*{Problems}
\begin{problem}

Verify that each of the following relations is an equivalence relation by
describing a function, $f$, such that the relation is defined by $f$
according to the Definition~\ref{deqv} in the Appendix.

\bparts

\ppart The ``has the same initials'' relation on English names.

\solution{Define
\[
f(\ang{\text{name}}) \eqdef\text{ the initials of }
\ang{\text{name}}.
\]
For example, $f(\text{``Albert R. Meyer''}) = \text{``ARM''}$.}

\ppart  $\equiv \pmod 4$ on $\integers$.

\solution{Let $f \eqdef \remainder_4$, the remainder on division by 4
function.}

\ppart Equality on a set, $A$.

\solution{Letting $f \eqdef \ident{A}$ is the simplest example, but any
\emph{injection} with domain $A$ will work.}

\ppart Propositional equivalence on propositional formulas.

\solution{Two propositional formulas are equivalent iff they have the
same truth table, so let $f(\ang{\text{expr}}) \eqdef \text{the truth
table for} \ang{\text{expr}}$.

For this to be completely accurate, we should specify the order in which
the rows for the different truth assignments are supposed to occur in the
table.  There's also a minor technical problem: $(p \lor \bar{p})
\land q$ and $q$ are propositionally equivalent, but have different truth
tables.  One fix is to agree to omit from the truth table variables like
$p$ above that don't affect the truth value of the formula.}

\iffalse

\ppart $R$ is the relation ``defines the same polynomial'' relation on
arithmetic expressions, that is, on expressions involving the operations
of $+$, $-$, and $\times$, integer constants, and variables ranging over
the integers.  For example,
\begin{equation}\label{pid}
(x+1)(3-yz) = -xyz - yz + 3x +3
\end{equation}
is a valid arithmetic equation, so we have
\[
\mathtt{(x + 1) \times (3 - (y \times z))} \ R\ \mathtt{(-1 \times (x
\times y \times z)) - (y \times z) + (3\times x) + 3}.
\]

\solution{
Every integer polynomial expression can be written in standard form as in
the lefthand side of equation~(\ref{pid}).  That is, a \emph{standard form}
is a sum of monomials with integer coefficients, with the variables in
each monomial in alphabetic order, and the monomials in the sum listed in
order of decreasing degree and in alphabetical order among monomials of
the same degree.  So define
\[
f(\ang{\text{expr}}) \eqdef \text{standard-form}(\ang{\text{expr}}.
\]
}
\fi

\eparts

\end{problem}

\begin{problem}
Give a helpful description (more than just the definition) of the
equivalence classes (blocks of the partition) associated with each of the
following equivalence relations.

\bparts

\ppart $\equiv \pmod 4$  on $\integers$.

\solution{
\[\begin{array}{l}
\set{0, 4, -4, 8, -8, 12,\dots}\\
\set{1, -3, 5, -7, 9, -11,\dots}\\
\set{2, -2, 6, -6, 10, -10,\dots}\\
\set{3, -1, 7, -5, 11, -9,\dots}.
\end{array}
\]}

\ppart The equivalence relation on $\reals$ defined by ceiling function,
$f(r) \eqdef \ceil{r}$, the smallest integer $\ge r$.

\solution{
The partition is $\set{B_n \suchthat n\in \integers}$ where
\[
B_n \eqdef \set{r \in \reals \suchthat n-1 < r \le n}
\]
}

\ppart Propositional equivalence on propositional formulas.

\solution{This is harder to explain.  The best we can think of is to say
that the blocks correspond to all the possible truth tables, with the
block corresponding to a truth table consisting of all the formulas with
that truth table.}

\eparts

\end{problem}


\begin{problem} 

\begin{falseclm*}
Suppose $R$ is a relation on $A$. If $R$ is symmetric and transitive, 
then $R$ is reflexive.
\end{falseclm*}

\bparts
\ppart Give a counter-example to the claim.

\solution{The simplest counterexample is to let $R$ be the empty relation
on some nonempty set $A$.  This $R$ is vacuously, symmetric and
transitive, but obviously not reflexive.

A slightly less trivial example is
\[
R \eqdef \set{(a,a),(a,b),(b,a),(b,b)}
\]
on the set $A \eqdef \set{a,b,c}$.  It is not reflexive because $(c,c)$ is
not in $R$.}

\ppart Find the flaw in the following proof of the claim:

\begin{falseproof}
Let $x$ be an arbitrary element of $A$.  Let $y$ be any element of $A$
such that $xRy$.  Since $R$ is symmetric, it follows that $yRx$.  Then
since $xRy$ and $yRx$, we conclude by transitivity that $xRx$.  Since
$x$ was arbitrary, we have shown that $\forall x \in A\; (xRx)$, so
$R$ is reflexive.
\end{falseproof}

\solution{
The flaw is assuming that $y$ exists.  It is possible that there is an
$x \in A$ that is not related by $R$ to anything.  No such $R$ will be
reflexive.

Note that the theorem can be fixed: $R$ restricted to its domain of
definition is reflexive, and hence an equivalence relation.}
\eparts
\end{problem}

\instatements{\newpage}
\begin{problem}
Verify that each of the following relations is a partial order by
describing a function, $g$, such that the relation is defined by $g$
according to the Definition~\ref{po-def} in the Appendix.

\bparts

\ppart The relation, $<$, on $\reals$.

\solution{Define $g(r) \eqdef \set{t \in \reals \suchthat t<r}$.  It
follows that
\[
r_1 < r_2 \qiff g(r_1) \subset g(r_2)
\]
so $<$ satisfies the condition~(\ref{po-eqn}) on $R$ that defines partial
orders.  Likewise, the relation, $\le$, is a partial order because
\[
r_1 \le r_2 \qiff r_1 < r_2,
\]
for all reals $r_1 \neq r_2$.
}

\ppart The superset relation, $\supseteq$, on $\power(B)$ for a set, $B$.

\solution{Define $g(a) \eqdef \bar{a} \eqdef B - a$, and note that
for $a_1 \neq a_2 \in \power(B)$,
\begin{align*}
a_1 \supseteq a_2 &\qiff a_1 \supset a_2 & \text{(since $a_1 \neq a_2$)}\\
&\qiff \bar{a_1} \subset \bar{a_2} & \text{(basic set theory)}\\
& \qiff g(a_1) \subset g(a_2) & \text{(def of $g$)}.
\end{align*}
}

\ppart The ``divides'' relation on natural numbers.
\solution{
Let $g(a) \eqdef\text{ the set of natural number  that divide } a$.
}

\eparts

\end{problem}


\begin{problem}
Show that none of the following relations is an equivalence by identifying
a relevant relational property it does not have.  Which ones are partial
orders?

\bparts

\ppart The relation, $\le$, on $\naturals$.

\solution{It's transitive (since [$j\le k$ and $k\le l$] implies $j\le
l$), and reflexive (since $r\le r$), but not symmetric (since $0\le 1$ but
not $1 \le 0$).}

\ppart The ``implies'' relation on propositional formulas.

\solution{
This relation is reflexive since $p \implies p$.  It is also transitive,
since if $p \implies q$ and $q \implies r$, then $p \implies r$.  However,
it isn't symmetric, since, for example, $\texttt{false} \implies
\texttt{true}$, but not $\texttt{true} \implies \texttt{false}$.
}

\ppart The relation, $R$, on sets of natural numbers such that $C\,
R\, D$ iff $C \intersect D$ is finite.

\solution{
$R$ is symmetric, but not
reflexive (for example $\naturals\, R\, \naturals$ is not true).
$R$ is also not transitive:
let $C$ be the even numbers, $D$ the odd numbers and $E$ the
multiples of 4.  So $C\, R\, D$, and $D\, R\, E$ but not $C\, R\, E$.}

\eparts

\end{problem}

\instatements{\newpage}
\section*{Appendix}

\subsection*{Equivalence}
\begin{definition}\label{deqv}
A binary relation, $R$, on a set, $A$, is an \emph{equivalence relation}
iff there is a function, $f$, with domain $A$, such that
\begin{equation}\label{Rf}
a_1\, R\, a_2 \qiff f(a_1) = f(a_2)
\end{equation}
for all $a_1,a_2 \in A$.
\end{definition}

\begin{theorem*}
A relation is an equivalence iff it is reflexive, symmetric and transitive.
\end{theorem*}

\subsection*{Partial Order}

\begin{definition}\label{po-def}
A relation, $R$, on a set, $A$, is a \emph{partial order} providing there
is a function, $g$, from $A$ to some collection of sets such that
\begin{equation}\label{po-eqn}
a_1\, R\, a_2 \qiff g(a_1) \subset g(a_2),
\end{equation}
for all $a_1 \neq a_2 \in A$.
\end{definition}

\begin{theorem*}
A relation is a partial order iff it is transitive and antisymmetric.
\end{theorem*}


\subsection*{Relational Properties}
A binary relation, $R$, on a set, $A$, is
\begin{itemize}

\item \emph{reflexive} if $a R a$ for every $a \in A$,

\item \emph{irreflexive} if $a R a$ holds for no $a \in A$,

\item \emph{symmetric} if for every $a,b\in A$, $aR b$ implies
    $bR a$,

\item \emph{antisymmetric} if for every $a \neq b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{asymmetric} if for every $a,b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{transitive} if for every $a,b,c\in A$, $aR b$ and
    $bR c$ implies $aR c$.

\end{itemize}

\end{document}
