\documentstyle[twoside,6044]{handout}
\begin{document}

\newcommand{\successor}{\operatorname{succ}}
\newcommand{\addtwo}{\operatorname{add2}}

\handout{diagnostic-quiz-soln}{Diagnostic Quiz Solutions}{13 September 1995}

\problem ...qualifications...

\problem Let $\successor$ be the successor function on integers:
\begin{eqnarray*}
  \successor(x) & = & x + 1
\end{eqnarray*}
Describe the function ($\successor \circ \successor$), that is, the
composition of $\successor$ with itself.
\begin{quotation}
  The composition of $\successor$ with itself is the ``add two''
  function, $\addtwo$:
\begin{eqnarray*}
  \addtwo(x) & = & x + 2
\end{eqnarray*}
because
\begin{eqnarray*}
(\successor\compose\successor)(x)
            &=& \successor(\successor(x))\\
            &=& \successor(x+1)\\
            &=& (x+1)+1\\
            &=& x+2\\
            &=& \addtwo(x)
\end{eqnarray*}
\end{quotation}

\problem How many strings of length 4 are there over the
alphabet~$\set{a,b,c}$?
\begin{quotation}
With three possibilities in each of four positions, there are $3^4=81$
possible strings.
\end{quotation}

\problem Define $\preceq$ to be the binary relation between sets
such that $A \preceq B$ if and only if the cardinality of~$A$ is less
than or equal to the cardinality of~$B$.
\begin{subproblems}
\item What is the definition of ``uncountable set''?  Now express the
definition in terms of $\preceq$.  Give an example of an uncountable
set.

\begin{quotation}
A set $A$ is uncountable iff there is no one-to-one mapping from $A$ into
the integers.  Thus, if $\Int$ is the set of integers, then an uncountable
set is any set~$A$ such that $A\npreceq\Int$.  The real numbers,~$\Real$,
are a well-known example of an uncountable set, as is the powerset of any
infinite set.
\end{quotation}

\item
For each of the following properties, state whether the
relation~$\preceq$ has the property, and if not, give a simple
counterexample.
\begin{enumerate}
\item reflexivity
\item symmetricity
\item transitivity
\end{enumerate}
\begin{quotation}
The relation $\preceq$ is reflexive ($A\preceq A$ for all sets $A$)
and transitive (if $A\preceq B$ and $B\preceq C$ then $A\preceq C$),
but not symmetric (there are sets $A$ and~$B$ with $A\preceq B$ but
$B\npreceq A$, for example $\Int$ and~$\Real$).
\end{quotation}
\end{subproblems}

\problem
For any set,~$A$, let $\pow{A}$ be the powerset of~$A$, namely, the set
of all subsets of $A$.  Exhibit the members
of~$\pow{\pow{\pow\emptyset}}$.
\begin{quotation}
Given the empty set, $\emptyset$, with no members, the only subset is
the (non-proper) subset $\emptyset$.  Thus, if $\pow\emptyset$ is the
set of all subsets of $\emptyset$, then
\[\pow\emptyset=\set\emptyset.
\]
Moving along, the subsets of $\pow\emptyset$ are $\emptyset$ and
$\set\emptyset$, so
\[\pow{\pow\emptyset}=\set{\emptyset,\set\emptyset}.
\]
Then, $\pow{\pow\emptyset}$ has subsets $\emptyset$, $\set\emptyset$,
$\set{\set\emptyset}$, and $\set{\emptyset,\set\emptyset}$, so
\[\pow{\pow{\pow\emptyset}}=
\set{\emptyset,\set\emptyset,\set{\set\emptyset},\set{\emptyset,\set\emptyset}}
\]
\end{quotation}

\problem Two Boolean formulas $F_1(x_1,\ldots,x_n)$
and~$F_2(x_1,\ldots,x_n)$ are
{\em equivalent\/} iff they yield the same truth value for all truth
assignments to the variables $x_1,\ldots,x_n$.

\begin{subproblems}
\item  ... Describe a Boolean
binary operation which is not commutative.

\begin{quotation}
The ``implies'' operation, often written $\Rightarrow$, is
non-com\-mu\-ta\-tive: $\False\Rightarrow\True$, but
$\True\nRightarrow\False$, so $x_1\Rightarrow x_2$ and $x_2\Rightarrow
x_1$ are not equivalent.
\end{quotation}

\item Describe an infinite set of equivalent Boolean formulas.
\begin{quotation}
Define the formulas $F_i$ as $F_0\eqdef x_0$ and
$F_{i+1}\eqdef(F_i\conj x_0)$ for all $i\ge0$.  These formulas are all
equivalent, since for any truth assignment they all have the same
truth value as $x_0$.
\end{quotation}

\item Explain why ``equivalent'' is actually an equivalence relation
on formulas.
\begin{quotation}
An equivalence relation is a binary relation on a set $A$, that is,
$R\subseteq A\times A$, which is reflexive ($a\mathrel{R}a$ for all
$a\in A$), transitive (if $a\mathrel{R}a'$ and $a'\mathrel{R}a''$ then
$a\mathrel{R}a''$), and symmetric ($a\mathrel{R}a'$ iff
$a'\mathrel{R}a$).

Take any three formulas $F_0$, $F_1$ and $F_2$.  Given any truth
assignment to $x_1,\ldots,x_n$:
\begin{itemize}
\item $F_0$ yields the same truth value as itself, so ``equivalent''
is reflexive.
\item If $F_0$ yields the same truth value as $F_1$, then $F_1$ yields
the same truth value as $F_0$, so ``equivalent'' is symmetric.
\item If $F_0$ yields the same truth value as $F_1$, and $F_1$ yields
the same truth value as $F_2$, then clearly $F_0$ yields the same
truth value as $F_2$, so ``equivalent'' is transitive.
\end{itemize}
Thus, ``equivalent'' is an equivalence relation on formulas.
\end{quotation}

\item Explain why there are only a finite number of equivalence
classes of formulas with (at most) variables $x_1,\ldots,x_n$.

\item How many?

\begin{quotation}
Formulas are equivalent iff their truth tables agree, so there
are as many equivalence classes as there are truth tables.  Given $n$
variables, there are $2^{2^n}$ possible truth tables.  To see this,
think of a truth table as having a row for each possible truth
assignment.  A truth assignment consists of a $\True$ or $\False$
value for each variable, so there are $\hbox{(size of $\TF$)}^n=2^n$
possible truth assignments.  Then, a truth table consists of an
assignment of $\True$ or $\False$ to each truth assignment, so with
$2^n$ truth assignments there are $2^{2^n}$ possible truth tables,
giving us $2^{2^n}$ equivalence classes of formulas.
\end{quotation}
\end{subproblems}

\problem A binary relation $\leq$ is {\em anti-symmetric\/} if $x=y$
whenever $x\leq y$ and $y\leq x$.
A {\em partial order\/} of a set~$D$ is a binary relation~$\leq$ that
is reflexive, transitive, and anti-symmetric on~$D$.
A partial order is {\em total\/} if for every $d_1,d_2\in D$, either
$d_1 \leq d_2$ or $d_2 \leq d_1$.
If $X\subset D$ and $y\leq x$ for every $x\in X$, then $y$
is a {\em lower bound\/} of~$X$.
Similarly, if $x \leq y$ for every $x \in X$, then $y$ is an {\em
  upper bound\/} of~$X$.
If $y$ is a lower bound of $X$, and $z\leq y$ for every lower
bound~$z$ of~$X$, then $y$ is the {\em greatest lower bound\/}
(``glb'' or ``meet'') of~$X$.
If $y$ is an upper bound of $X$, and $y\leq z$ for every upper
bound~$z$ of~$X$, then $y$ is the {\em least upper bound\/} (``lub'')
of~$X$.

Let $A$ be the set~$\set{1,2,3,4,5}$.
\begin{subproblems}
\item Give a total order of $A$.  That is, describe a binary
  relation~$\leq$ on~$A$ that is a total order.
\begin{quotation}
The usual numerical ``less than or equal to'' relation is a total
order.
\end{quotation}

\item Give a partial order of $A$ such that: (1)~every pair of elements
  has a glb; and (2) there is no lub of~$\set{4,5}$.
\begin{quotation}
The ordering in which $3$ is less than or equal to any
other number, but all other numbers are incomparable, is such an
order.  In pictures, we can draw the order as follows:
\begin{center}
\begin{picture}(100,40)
\put(50.5,0){3}
\put(30,30){1}\put(53,8){\line(-1,1){20}}
\put(40,30){2}\put(53,8){\line(-1,2){10}}
\put(60,30){4}\put(53,8){\line(1,2){10}}
\put(71,30){5}\put(53,8){\line(1,1){20}}
\end{picture}
\end{center}
Here we are using a common graphical shorthand for partial orders,
in which an element is ``less than'' another element if we can trace
an upwards path from the first element to the second.  Since there is
an upwards path from 3 to every other number, we have $3\leq x$ for
all $x \in A$.  (There is an upwards path from 3 to 3, namely the
upwards path of length 0).  However, $1\nleq 4$ since there is no
upwards path from 1 to 4, and $4\nleq 1$ since there is no upwards
path from 4 to 1; that is, 1 and 4 are incomparable.

From the diagram, it is clear that every pair of distinct numbers has
a unique lower bound in the ordering, namely~$3$.  Since there is only
one lower bound possible, it is clearly the greatest lower bound.
However, $4$ and~$5$ have no upper bound at all, let alone a least
upper bound.
\end{quotation}

\item Give a partial order of $A$ such that every pair of elements has
  both an lub and a glb, but the order is not total.
\begin{quotation}
A slight variant, in which we leave $3$ as the least element but make
$2$ the greatest, gives us an ordering in which every pair of elements
has both a least upper bound and a greatest lower bound, but the
ordering is still not total.
\begin{center}
\begin{picture}(100,70)
\put(50.5,0){3}
\put(30,30){1}\put(53,8){\line(-1,1){20}}
              \put(33,38){\line(1,1){20}}
\put(50,30){4}\put(53,8){\line(0,1){20}}
              \put(53,38){\line(0,1){20}}
\put(71,30){5}\put(53,8){\line(1,1){20}}
              \put(73,38){\line(-1,1){20}}
\put(50.5,60){2}
\end{picture}
\end{center}
\end{quotation}
\end{subproblems}

\end{document}
