\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{utf8}
\usepackage{tikz}
\usepackage{url}

% Note: the following tikz sudoku code borrowed from the tikz examples:
% Sudoku
% Author: Roberto Bonvallet
\newcounter{row}
\newcounter{col}

\newcommand\setrow[9]{
  \setcounter{col}{1}
  \foreach \n in {#1, #2, #3, #4, #5, #6, #7, #8, #9} {
    \edef\x{\value{col} - 0.5}
    \edef\y{9.5 - \value{row}}
    \node[anchor=center] at (\x, \y) {\n};
    \stepcounter{col}
  }
  \stepcounter{row}
}
% end sudoku snippet


\newcommand{\TODO}[1][fix]{\textbf{[TODO: #1]}}

\topic{Logic and Proofs}
\homework{1}

\begin{document}
\maketitle

\begin{exercises}
\item Recall that we defined a valid sudoku solution as a set of numbers $x_{ij}$
satisfying the following rules: \begin{description}
  \item[rule 1] Each cell contains a number from 1 to 9 (formally, $x_{ij} \in \{1, 2, \dots 9\}$)
  \item[rule 2] Each row contains all the numbers from 1 to 9 (formally, $\{x_{i1}, x_{i2}, \dots, x_{i9}\} = \{1, 2, \dots, 9\}$)
  \item[rule 3] Each column contains all the numbers from 1 to 9 (formally, $\{x_{1j}, x_{2j}, \dots, x_{9j}\} = \{1, 2, \dots, 9\}$)
  \item[rule 4] No big square contains the same number twice (formally, for distinct $(i, j)$ and $(k, ℓ)$, if $square(i,j) = square(k,ℓ)$, then \mbox{$x_{ij} \neq x_{kℓ}$})
\end{description}
Here, $i$, $j$, $k$ and $ℓ$ are implicitly numbers between $1$ and $9$;
$x_{ij}$ refers to the entry in the $i^\textrm{th}$ row and the $j^\textrm{th}$ column.
$square(i,j)$ refers to the large square that contains the $ij$ entry.  You may
use clearly stated facts about the $square$ function without
proof (but they should be true!).

\begin{enumerate}
\item For each of the following arguments, decide whether the logic is valid or
invalid.  If the logic is invalid, explain why.\begin{enumerate}
  \item \textbf{Claim:} if $x$ is a valid solution and is compatible with the following board:
  \begin{center}
  \begin{tikzpicture}[scale=.5]
    \begin{scope}
      \draw (0, 0) grid (9, 9);
      \draw[very thick, scale=3] (0, 0) grid (3, 3);

      \setcounter{row}{1}
      \setrow { }{8}{3}  {7}{ }{4}  {6}{2}{1}
      \setrow { }{6}{5}  {1}{2}{9}  {8}{3}{4}
      \setrow {2}{4}{1}  { }{ }{ }  {9}{5}{7}

      \setrow { }{2}{4}  {8}{9}{ }  {3}{6}{5}
      \setrow { }{ }{9}  {4}{3}{ }  { }{1}{2}
      \setrow { }{7}{6}  {2}{1}{ }  {4}{8}{9}

      \setrow {5}{9}{8}  {6}{7}{2}  {1}{4}{3}
      \setrow {6}{3}{2}  {9}{4}{1}  {5}{7}{8}
      \setrow {4}{1}{7}  {5}{8}{3}  {2}{9}{6}

    \end{scope}
  \end{tikzpicture}
  \end{center}
  (that is, if $x_{12} = 8$, $x_{13} = 3$, $x_{22} = 6$ and so on), then $x_{11} = 9$.

  \textbf{Proof:} Suppose $x_{11} = 9$.  Then since
  $square(1,1) = square(2,1) = square(2,2) = square(2,3)$, rule 4 tells us that
  none of $x_{21}$, $x_{22}$, nor $x_{23}$ can be $9$.  Similarly, since
  $x_{37} = 9$, none of $x_{27}$, $x_{28}$, nor $x_{29}$ can be $9$.  Thus by
  rule 2 (with $i = 2$), one of $x_{24}$, $x_{25}$, or $x_{26}$ must be $9$.  But
  we are given that $x_{26} = 9$, so the conclusion that one of $x_{24}$,
  $x_{25}$, and $x_{26}$ is 9 holds.  Thus our original assumption that $x_{11} = 9$
  is correct.

  \item \textbf{Claim:} if $x$ is a valid solution and is compatible with the
  board from part (i), then $x_{56} = 6$.

  \textbf{Proof:} Assume that $x_{56} \neq 6$.  By rule 4, there
  are two remaining possible values of $x_{56}$: it could be either 5 or
  7.  Let us consider these cases separately:
  \begin{itemize}
   \item If $x_{56} = 5$, then $x_{66} \neq 5$, by rule 4.  By
         rule 2, we see that this means $x_{61} = 5$ (since none of the other
         cells in row 6 can contain 5).  Note that none of the cells in $square(6,1)$
         can contain 3: each of $x_{42}$, $x_{43}$, $x_{53}$, $x_{62}$, and $x_{63}$
         were given other values; we just showed that $x_{61} = 5$, and none of $x_{41}$,
         $x_{51}$ or $x_{52}$ can be 3 because of rule 2.

         Now, the nine cells of $square(6,1)$ must be elements of $\{1, 2, \dots, 9\}$
         by rule 1.  Moreover, they must be distinct by rule 4.  Thus one of them
         must be 3.  However we just showed that none of them are 3, so our
         assumption that $x_{56} = 5$ must be false.

   \item If $x_{56} = 7$, then by rule 4, $x_{46} \neq 7$.  Moreover, rule 4
         shows that $x_{41} \neq 7$.  All the other cells of row 4 have already been assigned values other than 7. So 7 does not appear in row 4, but this contradicts rule 2.  Thus our premise that $x_{56} = 7$ must be false.
  \end{itemize}

  We have concluded that $x_{56} \neq 6$, $x_{56} \neq 5$, and $x_{56} \neq 7$.
  This contradicts rule 1, and thus the initial premise that $x_{56} \neq 6$ must
  be false.  Therefore $x_{56} = 6$, as claimed.

  \item \textbf{Claim:} if $x$ is a valid solution and is compatible with the
  board from part (i), then $x_{51} = 8$.

  \textbf{Proof:} The following is a complete solution that is compatible with
  the board from part (i):
  \begin{center}
  \begin{tikzpicture}[scale=.5]
    \begin{scope}
      \draw[thin] (0, 0) grid (9, 9);
      \draw[very thick, scale=3] (0, 0) grid (3, 3);

      \setcounter{row}{1}
      \setrow {9}{8}{3}  {7}{5}{4}  {6}{2}{1}
      \setrow {7}{6}{5}  {1}{2}{9}  {8}{3}{4}
      \setrow {2}{4}{1}  {3}{6}{8}  {9}{5}{7}

      \setrow {1}{2}{4}  {8}{9}{7}  {3}{6}{5}
      \setrow {8}{5}{9}  {4}{3}{6}  {7}{1}{2}
      \setrow {3}{7}{6}  {2}{1}{5}  {4}{8}{9}

      \setrow {5}{9}{8}  {6}{7}{2}  {1}{4}{3}
      \setrow {6}{3}{2}  {9}{4}{1}  {5}{7}{8}
      \setrow {4}{1}{7}  {5}{8}{3}  {2}{9}{6}

    \end{scope}
  \end{tikzpicture}
  \end{center}
  Since each sudoku puzzle only has a single valid
  solution, $x_{51}$ must be $8$.
  \end{enumerate}

\item State clearly what it means for a board \emph{not} to satisfy rule 1.
Similarly, carefully state what it means for a board to fail to satisfy rules 2,
3 and 4.  Be sure to specify whether your statements are for all $i$ and $j$ or
for any $i$ and $j$.  Clearly state what it means for a board \emph{not} to be
a valid sudoku solution.

Using your definitions, prove that the following board is not a valid sudoku solution:
\begin{center}
\begin{tikzpicture}[scale=.5]
  \begin{scope}
    \draw (0, 0) grid (9, 9);
    \draw[very thick, scale=3] (0, 0) grid (3, 3);

    \setcounter{row}{1}
    \setrow {7}{6}{4}  {9}{5}{2}  {1}{3}{8}
    \setrow {1}{8}{5}  {6}{3}{7}  {9}{2}{4}
    \setrow {2}{9}{3}  {4}{1}{8}  {7}{6}{9}

    \setrow {5}{2}{9}  {3}{8}{1}  {4}{7}{6}
    \setrow {3}{7}{6}  {2}{9}{4}  {8}{5}{1}
    \setrow {8}{4}{1}  {5}{7}{6}  {2}{9}{3}

    \setrow {4}{5}{8}  {7}{6}{9}  {3}{1}{2}
    \setrow {9}{3}{2}  {1}{4}{5}  {6}{8}{7}
    \setrow {6}{1}{7}  {8}{2}{3}  {5}{4}{9}
  \end{scope}
\end{tikzpicture}
\end{center}

\item Suppose that $x$ is a valid sudoku solution.  Define another solution $y$
by $y_{ij} = x_{ji}$.  Prove that $y$ is a valid sudoku solution.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Briefly and clearly identify the error in this proof:

{\bf Proof that 1 is the largest natural number:} Let $n$ be the largest natural number. Then $n^2$, being a natural number, is less than or equal to $n$. Therefore $n^2 - n = n (n - 1) \leq 0$. Hence $0 \leq n \leq 1$. Therefore $n = 1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Here is a proof that is technically correct, but stylistically atrocious. It is a proof of the irrationality of $\sqrt 2$. Rewrite this proof in English, using good mathematical writing style. See the Sample Proofs at the end of Chapter Three of {\em Bridge to Higher Mathematics} (\url{http://myslu.stlawu.edu/~svanderv/chapthree.pdf}) for some models.

PS: Nicely written versions of this proof are of course widely available online. Please try not to look at them before you write up your answer!

\noindent {\bf Proof (by contradiction):}
\begin{align*}
& \mathbb{Z} = \textrm{Integers } \{ \dots, -2, -1, 0, 1, 2, \dots \} ,~ \mid ~ = \textrm{``divides''} \\
& \textrm{Define } R(x) = \textrm{``$x$ is rational''} = \left( \exists p, q \in \mathbb{Z}, q \neq 0 \wedge x = \frac{p}{q} \wedge \left( \neg \exists r \in \mathbb{Z}, (r > 1) \wedge (r \mid p) \wedge (r \mid q) \right) \right) \\
& R(\sqrt 2) \\
& \exists p, q \textrm{ as above} \\
& \sqrt 2 = \frac{p}{q} \\
& 2 = \frac{p^2}{q^2} \\
& p^2 = 2 q^2 \\
& 2 | p^2 \\
& 2 | p \\
& 4 | p^2 \\
& 4 | 2 q^2 \\
& 2 | q^2 \\
& 2 | q \\
& \exists r = 2 \in \mathbb{Z}, (r > 1) \wedge (r \mid p) \wedge (r \mid q) \\
& \textrm{contra!}
\end{align*}
Qed.

\end{exercises}

\end{document}
