\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{amsmath}


%%  Common macros for the course CSC165H1F,
%%  on the St. George Campus at the University of Toronto.
%%
%%  Copyright (c) 2009-2011 Francois Pitt <fpitt@cs.utoronto.ca>
%%
%%  This work may be distributed and/or modified under the conditions of
%%  the LaTeX Project Public License, either version 1.3 of this license
%%  or (at your option) any later version.
%%  The latest version of this license is in
%%      http://www.latex-project.org/lppl.txt
%%  and version 1.3 or later is part of all distributions of LaTeX
%%  version 2003/12/01 or later.
%%
%%  This work has the LPPL maintenance status "author-maintained".
%%
%%  The Current Maintainer of this work is
%%  Francois Pitt <fpitt@cs.utoronto.ca>.
%%
%%  This work consists of the file macros-165.tex.

% Trick so that math symbols are bold when text is.
\let\seiresfb\bfseries\def\bfseries{\boldmath\seiresfb}
\let\seiresdm\mdseries\def\mdseries{\unboldmath\seiresdm}

% Centered version of \llap and \rlap.
\newcommand*{\clap}[1]{\hbox to 0pt{\hss#1\hss}}

% Spacing macros with default argument.
\newcommand*{\vstretch}[1][1]{\vspace*{\stretch{#1}}}
\newcommand*{\hstretch}[1][1]{\hspace*{\stretch{#1}}}

% General fonts and characters.
\let\altemph\textsl  % alternate way to emphasize
\let\strong\textbf  % strong emphasis
\let\latinabb\emph  % abbreviations of latin phrases
\let\code\texttt  % code fragments
\let\const\textsf  % constants
\let\term\textbf  % newly-introduced (or defined) words
\let\var\mathrm  % multi-letter variables (or constants)
\let\pred\mathbf  % predicates
\newcommand*{\txtbksl} {\symbol{"5C}}% \
\newcommand*{\txtcaret}{\symbol{"5E}}% ^
\newcommand*{\txtunder}{\symbol{"5F}}% _
\newcommand*{\txtlcurl}{\symbol{"7B}}% {
\newcommand*{\txtrcurl}{\symbol{"7D}}% }
\newcommand*{\txttilde}{\symbol{"7E}}% ~
\newcommand*{\N}{\ensuremath{\mathbb{N}}}  % requires amssymb
\newcommand*{\Z}{\ensuremath{\mathbb{Z}}}  % requires amssymb
\newcommand*{\Q}{\ensuremath{\mathbb{Q}}}  % requires amssymb
\newcommand*{\R}{\ensuremath{\mathbb{R}}}  % requires amssymb
\newcommand*{\bigOh}{\mathcal{O}}
\newcommand*{\onehalf}{\ensuremath{{}^1\!\!/\!_2}}

% Abbreviations of latin phrases.
\newcommand*{\ie}{\latinabb{i.e.}}
\newcommand*{\eg}{\latinabb{e.g.}}
\newcommand*{\etc}{\latinabb{etc}}
\newcommand*{\vs}{\latinabb{vs}}

% General math macros.
\newcommand*{\comp}[1]{\overline{#1}}  % set complement
\newcommand*{\emptystr}{\varepsilon}  % empty string
\newcommand*{\lequiv}{\mathrel{\ \Longleftrightarrow\ }}  % equivalence
\newcommand*{\lxor}{\oplus}  % exclusive or
\newcommand*{\cat}{\cdot}  % string concatenation
\newcommand*{\invisible}[1]{\mathrel{\hphantom{#1}}}
% floors and ceilings, with optional size-changing command,
% e.g., \floor[\Big]{x/2} generates '\Big\lfloor{x/2}\Big\rfloor'
\newcommand*{\floor}[2][]{{#1\lfloor}{#2}{#1\rfloor}}
\newcommand*{\ceil}[2][]{{#1\lceil}{#2}{#1\rceil}}
\newcommand*{\lcm}{\operatorname{lcm}}  % requires amsmath
\newcommand*{\size}{\operatorname{size}}  % requires amsmath

% Redefined symbols from amssymb.
\renewcommand*{\emptyset}{\varnothing}  % rounder than default
\let\bigiff\iff
\renewcommand*{\iff}{\mathrel{\Leftrightarrow}}  % smaller than default
\let\bigimplies\implies
\renewcommand*{\implies}{\mathrel{\Rightarrow}}  % smaller than default
\renewcommand*{\ge}{\geqslant}  % with slanted line under the > sign
\renewcommand*{\le}{\leqslant}  % with slanted line under the < sign

% For algorithms, in Python.
\let\kw\textbf  % keywords
\let\proc\textsc  % function names
\newcommand*{\opgets}[1]{\mathrel{#1=}}
\newcommand*{\eq}{\mathrel{==}}
\newcommand*{\True}{\const{True}}
\newcommand*{\False}{\const{False}}
\newcommand*{\None}{\const{None}}
\newcommand*{\cmod}{\mathbin{\%}}
\newcommand*{\len}{\operatorname{len}}  % requires amsmath

% Like {itemize} but using less vertical space.
\newenvironment*{points}
 {\ifvmode\else\unskip\par\fi\begin{list}{$\bullet$}
   {\setlength{\topsep}{.25ex plus .125ex minus .1825ex}
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}
    \setlength{\labelwidth}{1.75em}}\ignorespaces}
 {\ifvmode\else\unskip\fi\end{list}\ignorespaces}

% Checkboxes and checklists.
\newcommand*{\cbox}[1]{{\fboxrule.125ex\fboxsep0ex
    \framebox[2.75ex]{\rule[-.75ex]{0ex}{2.75ex}\smash{#1}}}}
\newcommand*{\cmark}{\raisebox{.0625ex}{$\surd$\kern.125ex}}
\newcommand*{\xmark}{\raisebox{-.1875ex}{\kern.0625ex{X}}}
\newcommand*{\checkbox}{{\sf\cbox{}}}
\newcommand*{\checkedbox}{{\sf\cbox{\cmark}}}
\newcommand*{\markedbox}{{\sf\cbox{\xmark}}}
\newenvironment{checklist}{\begin{list}{\checkbox}{}}{\end{list}}
\newcommand*{\checkeditem}{\item[\checkedbox]}
\newcommand*{\markeditem}{\item[\markedbox]}

% Proof-related environments and macros.
\newcommand*{\just}{{\quad\#\ }}  % justification for a proof step
\newenvironment*{pindent}
   {\begin{list}{}
       {\topsep 0pt
        \partopsep 0pt
        \itemsep 0pt
        \parsep 0pt
        \parskip 0pt}\item\relax}
   {\unskip\end{list}\ignorespaces}
% Usage: \begin{assumption}[<pre-text>]{<assumption>}
%          ...body...
%        \end{assumption}{<conclusion>}
% is formatted as
%    <pre-text> assume <assumption>
%        ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Assume <assumption>
%        ...body...
%    <conclusion>
\newenvironment*{assumption}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{a}ssume {#2}
    \begin{pindent}}
   {\end{pindent}}
% Usage: \begin{pickavalue}[<pre-text>]{<names>}
%          ...body...
%        \end{pickavalue}{<conclusion>}
% is formatted as
%    <pre-text> let <names>
%    ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Let <names>
%    ...body...
%    <conclusion>
\newenvironment*{pickavalue}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{l}et {#2}
    \par\ignorespaces}
   {\unskip\par\ignorespaces}


\title{CSC165, Summer 2014\\
Assignment 3\\
Solutions}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}



\begin{document}
\maketitle

\begin{enumerate}

\item 
\begin{enumerate} 
\item (4 pts.) Prove or disprove that, for any universal set $U$ and predicates $P$ and $Q$,
$$	
	 [\exists x \in U, P(x) \land Q(x)] 	 \Rightarrow [\exists x \in U, P(x)) \land (\exists x \in U, Q(x))]
$$
{\bf Solution:}
The statement is \textbf{true}.

Proof:

\begin{pindent}
  \begin{assumption}{$\exists x \in U, P(x) \land Q(x)$}
    Let $x_0 \in U$ be such that $P(x_0) \land Q(x_0)$		\just{naming it $x_0$}\\
    Then $P(x_0)$				\just{$P(x_0) \land Q(x_0) \implies P(x_0)$ since $R\land S\implies R$}\\
    Then $\exists x \in U, P(x)$		\just{$x_0$ is such an $x$}\\
    Then $Q(x_0)$				\just{$P(x_0) \land Q(x_0) \implies Q(x_o)$ since $R\land S\implies S$}\\
    Then $\exists x \in U, Q(x)$		\just{$x_0$ is such an $x$}\\
    Then $(\exists x \in U, P(x)) \land (\exists x \in U, Q(x))$	\just{conjunction of two true statements above}
  \end{assumption}{Then $[\exists x \in U, P(x) \land Q(x)] \Rightarrow [(\exists x \in U, P(x)) \land (\exists x \in U, Q(x))]$} \just{introduce implication}
   \hspace*{13.5cm} $\blacksquare$
\end{pindent}


\item (4 pts.) Prove or disprove that, for any universal set $U$ and predicates $P$ and $Q$,
$$	
	[\exists x \in U, P(x)) \land (\exists x \in U, Q(x))] \Rightarrow [\exists x \in U, P(x) \land Q(x)]
$$
{\bf Solution:}\\
The statement is \textbf{false}. We prove its negation $$\lnot [[\exists x \in U, P(x)) \land (\exists x \in U, Q(x))] \Rightarrow [\exists x \in U, P(x) \land Q(x)]].$$

Proof:

\begin{pindent}
\begin{pickavalue}{$U = \{1,10\}$, $P(x) : x < 5$,  $Q(x) : x > 7$}
	Then $P(1)$  \just{$1 < 5$} \\
	Then $\exists x \in U, P(x)$ \just{$1 \in U$ is such an $x$} \\
	\\
	Then $Q(10)$  \just{$10 < 7$} \\
	Then $\exists x \in U, Q(x)$ \just{$10 \in U$ is such an $x$} \\
	\\
	Then $[\exists x \in U, P(x)) \land (\exists x \in U, Q(x))]$ \just{conjunction of two true statements} \\
	\\
	Then $\lnot [P(1) \land Q(1)]$ \just{$Q(1)$ is false} \\
	Then $\lnot [P(10) \land Q(10)]$ \just{$P(10)$ is false} \\
	Then $\forall x \in U, \lnot [P(x) \land Q(x)]$ \just{we enumerated all the cases for $x \in U$}\\
	Then $\lnot [\exists x \in U, P(x) \land Q(x)]$ \just{quantifier negation}\\
	Then $[[\exists x \in U, P(x)] \land [\exists x \in U, Q(x)]]\land\lnot [\exists x \in U, P(x) \land Q(x)]$ \just{conjunction}\\
\end{pickavalue}{Then $\lnot [[\exists x \in U, P(x)) \land (\exists x \in U, Q(x))] \Rightarrow [\exists x \in U, P(x) \land Q(x)]] 	$\just{implication negation}}
   \hspace*{13.8cm} $\heartsuit$
\end{pindent}



\item (4 pts.) Prove or disprove that, for any universal set U and predicate $P$
$$
	[\exists x \in U, P(x)]  \Rightarrow [\forall x \in U, P(x)]
$$
{\bf Solution:}\\
The statement is \textbf{false}. We prove its negation $$\lnot [[\exists x \in U, P(x)]  \Rightarrow [\forall x \in U, P(x)]].$$

Proof:

\begin{pindent}
\begin{pickavalue}{$U = \{1,10\}$, $P(x) : x < 5$}
	Then $P(1)$  \just{$1 < 5$} \\
	Then $\exists x \in U, P(x)$ \just{$1 \in U$ is such an $x$} \\
	\\
	Then $\lnot P(10)$  \just{$10 \ge 7$} \\
	Then $\exists x \in U, \lnot P(x)$ \just{$10 \in U$ is such an $x$} \\
	Then $\lnot [\forall x \in U, P(x)]$ \just{negation of universal} \\
	\\
	Then $[\exists x \in U, P(x)] \land [\lnot [\forall x \in U, P(x)]] $ \just{conjunction}\\
\end{pickavalue}{Then $\lnot 	[\exists x \in U, Q(x)] \Rightarrow [\exists x \in U, P(x) \land Q(x)]$\just{implication negation}} \\
QED
\end{pindent}






\item (4 pts.) Prove or disprove that,  for any universal set U and predicate $P$
$$
	[\forall x \in U, P(x)]  \Rightarrow [\exists x \in U, P(x)]
$$
{\bf Solution:}\\
The statement is \textbf{false}. We prove its negation $$\lnot [[\forall x \in U, P(x)]  \Rightarrow [\exists x \in U, P(x)]].$$

Proof:

\begin{pindent}
\begin{pickavalue}{$U = \emptyset$, $P(x) = true$}
	Then $\forall x \in U, P(x)$  \just{elements in the empty set have all properties} \\
	\\
	Then $\lnot \exists x \in U, P(x)$ \just{$U$ is empty} \\
	\\
	Then $[\forall x \in U, P(x)] \land [\lnot \exists x \in U, P(x)]$  \just{conjunction} \\
\end{pickavalue}{Then $\lnot [[\forall x \in U, P(x)]  \Rightarrow [\exists x \in U, P(x)]]$\just{implication negation}} \\
   \hspace*{10cm} $\blacksquare$
\end{pindent}



\end{enumerate}

\newpage
\item For this question, you will prove that the roots of $x^2+6x+8.5$ are irrational. In other words, that 
$$
	\forall x \in \mathbb{R}, x^2+6x+8.5=0 \Rightarrow x \not \in \mathbb{Q}.
$$
You may use, without proof, the quadratic formula. In other words, you may use the fact that for all real $a$, $b$, and $c$, 
$$
	\forall x \in \mathbb{R},  (ax^2+bx+c = 0)\land(b^2-4ac \geq 0) \Rightarrow (x = \frac{-b-\sqrt{b^2-4ac}}{2a}) \lor (x = \frac{-b+\sqrt{b^2-4ac}}{2a})
$$
Please write complete proofs in each subquestion, without referring back to earlier subquestions.
\begin{enumerate}
	\item (4 pts.) Prove that $\forall x \in \mathbb{R}, x \in \mathbb{Q} \Rightarrow (x+1) \in \mathbb{Q}$. \textit{Hint: go back to the definition of $\mathbb{Q}$, and show that if $x$ satisfies that definition, then so does $(x+1)$.} \label{qq}\\
        {\bf Solution:}

        \begin{assumption}{$x \in \mathbb{R}$}
          \begin{assumption}{$x \in \mathbb{Q}$}
            Then $x = \frac{p}{q}$, for $p \in \mathbb{Z}, q \in \mathbb{Z}^*$ \just{definition of rational numbers}\\
            Then $x + 1 = \frac{p}{q} + \frac{q}{q} = \frac{p + q}{q}$ \just{algebra}\\
	 $p + q \in \mathbb{Z}$ \just{integers are closed under addition}\\
	 Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}, x+1 = \frac{p'}{q'}$ \just{$p+q$ and $q$ are such $p'$ and $q'$}\\
            Then $x + 1 \in \mathbb{Q}$ \just{definition of $\mathbb{Q}$}
          \end{assumption}{Then $x \in \mathbb{Q} \Rightarrow (x + 1) \in \mathbb{Q}$} \just{introduce implication}
        \end{assumption}{Then $\forall x \in \mathbb{R}, x \in \mathbb{Q} \Rightarrow (x + 1) \in \mathbb{Q}$} \just{introduce universal} \\
        QED



	\item (4 pts.) Prove that $\forall x \in \mathbb{R}, x \not \in \mathbb{Q} \Rightarrow (x+1) \not \in \mathbb{Q}$. \textit{Hint: can you prove the contrapositive of this statement?} \label{nqnq}\\
        {\bf Solution:}\\
        We prove the contrapositive first.
        \begin{assumption}{$x \in \mathbb{R}$}
          \begin{assumption}{$(x + 1) \in \mathbb{Q}$}
            Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}^*, x + 1 = \frac{p'}{q'}$,\just{definition of $\mathbb{Q}$}\\
	 Let $p$ and $q$ be such that $x+1 = \frac{p}{q}$\just{instantiation}\\
            Then $x = \frac{p}{q}-\frac{q}{q} = \frac{p-q}{q}$  \just{algebra}\\
	 $p - q \in \mathbb{Z}$ \just{integers are closed under subtraction}\\
	 Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}, x = \frac{p'}{q'}$ \just{$p-q$ and $q$ are such $p'$ and $q'$}\\
            Then $x \in \mathbb{Q}$ \just{by definition of $\mathbb{Q}$}
          \end{assumption}{Then $(x + 1) \in \mathbb{Q} \Rightarrow x \in \mathbb{Q}$} \just{introduce implication}
        \end{assumption}{Then $\forall x \in \mathbb{R}, (x + 1) \in \mathbb{Q} \Rightarrow x \in \mathbb{Q}$} \just{introduce universal} \\
        Then $\forall x \in \mathbb{R}, x \not \in \mathbb{Q} \Rightarrow (x+1) \not \in \mathbb{Q}$ \just{contrapositive} \\	
        \hspace*{10cm} $\heartsuit$
\newpage

	\item (16 pts.) Prove that $\forall x \in \mathbb{R}, x^2+6x+8.5=0 \Rightarrow x \not \in \mathbb{Q}$. \textit{Hint: you may want to use results that are similar to \ref{qq} and \ref{nqnq}}.\\
        {\bf Solution:}\\
      We first prove that adding a whole number to an irrational number results in an irrational number, and that dividing an irrational number by a whole number results in an irrational number.\\



Adding a whole number to an irrational number results in an irrational number:
        \begin{assumption}{$x \in \mathbb{R}$}
          \begin{assumption}{$(x + n) \in \mathbb{Q}, n \in \mathbb{Z}$}
            Then $x + n = \frac{p}{q}$, for $p \in \mathbb{Z}, q \in \mathbb{Z}^*$ \just{definition of $\mathbb{Q}$}\\
            Then $x = \frac{p}{q}-\frac{nq}{q} = \frac{p-nq}{q}$  \just{algebra}\\
	 $p - nq \in \mathbb{Z}$ \just{integers are closed under  subtraction and multiplication}\\
	 Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}, x = \frac{p'}{q'}$ \just{$p-nq$ and $q$ are such $p'$ and $q'$}\\
            Then $x \in \mathbb{Q}$ \just{by definition of $\mathbb{Q}$}
          \end{assumption}{Then $(x + n) \in \mathbb{Q} \Rightarrow x \in \mathbb{Q}$} \just{introduce implication}
        \end{assumption}{Then $\forall x \in \mathbb{R}, \forall n \in \mathbb{Z}, (x + n) \in \mathbb{Q} \Rightarrow x \in \mathbb{Q}$} \just{introduce universal} \\
        Then \textbf{$\forall x \in \mathbb{R}, \forall n \in \mathbb{Z}, x \not \in \mathbb{Q} \Rightarrow (x+n) \not \in \mathbb{Q}$} \just{contrapositive}\\



Multiplying an irrational number by a whole number results in an irrational number:
        \begin{assumption}{$x \in \mathbb{R}$}
          \begin{assumption}{$(x/n) \in \mathbb{Q}, n \in \mathbb{Z}$}
            Then $x/n = \frac{p}{q}$, for $p \in \mathbb{Z}, q \in \mathbb{Z}^*$ \just{definition of $\mathbb{Q}$}\\
            Then $x = \frac{np}{q}$  \just{algebra}\\
	 $np \in \mathbb{Z}$ \just{integers are closed under  multiplication}\\
	 Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}, x = \frac{p'}{q'}$ \just{$np$ and $q$ are such $p'$ and $q'$}\\
            Then $x \in \mathbb{Q}$ \just{by definition of $\mathbb{Q}$}
          \end{assumption}{Then $(x/n) \in \mathbb{Q} \Rightarrow x \in \mathbb{Q}$} \just{introduce implication}
        \end{assumption}{Then $\forall x \in \mathbb{R}, \forall n \in \mathbb{Z}, (x/n) \in \mathbb{Q} \Rightarrow x \in \mathbb{Q}$} \just{introduce universal} \\
        Then \textbf{$\forall x \in \mathbb{R}, \forall n \in \mathbb{Z}, x \not \in \mathbb{Q} \Rightarrow (x/n) \not \in \mathbb{Q}$} \just{contrapositive}\\


We now prove the main result.
        \begin{assumption}{$x \in \mathbb{R}$}
          \begin{assumption}{$x^2+6x+8.5=0$}
            Then $6^2 - 4(1)(8.5) = 2 \geq 0$ \just{algebra}\\
            Then $\left(x = \frac{-6 - \sqrt{2}}{2}\right) \lor \left(x = \frac{-6 + \sqrt{2}}{2}\right)$ \just{using the quadratic formula}\\
	 {\bf Case 1:} $x = \frac{-6 - \sqrt{2}}{2}$\\
            $-\sqrt{2} \not \in {Q}$ \just{Dividing $\sqrt{2} \not \in \mathbb{Q}$ by $-1 \in \mathbb{Z}$}\\
	 $-6-\sqrt{2} \not \in {Q}$\just{Adding $\sqrt{2} \not \in \mathbb{Q}$ and $-6 \in \mathbb{Z}$}\\
	 Then $\frac{-6 - \sqrt{2}}{2} \not \in \mathbb{Q}$\just{dividing   $(-6 - \sqrt{2}) \not \in \mathbb{Q}$ by $2 \in \mathbb{Z}$}\\
	Then $x \not \in \mathbb{Q}$\just{substituting x}\\
            {\bf Case 2:} $x = \frac{-6 + \sqrt{2}}{2}$\\
             $-6+\sqrt{2} \not \in {Q}$\just{Adding $\sqrt{2} \not \in \mathbb{Q}$ and $-6 \in \mathbb{Z}$}\\
	 Then $\frac{-6 - \sqrt{2}}{2} \not \in \mathbb{Q}$\just{dividing   $(-6 - \sqrt{2}) \not \in \mathbb{Q}$ by $2 \in \mathbb{Z}$}\\
	Then $x \not \in \mathbb{Q}$\just{substituting x}\\
	\\
	Then $x \not \in \mathbb{Q}$\just{this holds in both of the two cases}\\
          \end{assumption}{Then $x^2+6x+8.5=0 \Rightarrow x \notin \mathbb{Q}$} \just{introduce implication}
        \end{assumption}{Then $x \in \mathbb{R}, x^2+6x+8.5=0 \Rightarrow x \notin \mathbb{Q}$} \just{introduce universal}



Here's an alternative proof (due to E.W., a student in the class):
\begin{assumption}{$x \in \mathbb{R}$}
        	\begin{assumption}{$x^2+6x+8.5=0$}
		Then $6^2 - 4(1)(8.5) = 2 \geq 0$ \just{algebra}\\
		Then $\left(x = \frac{-6 - \sqrt{2}}{2}\right) \lor \left(x = \frac{-6 + \sqrt{2}}{2}\right)$ \just{using the quadratic formula}\\
		{\bf Case 1:} $x = \frac{-6 - \sqrt{2}}{2}$\\
		\begin{assumption}{$x \in \mathbb{Q}$}
			Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}, x = p/q$ \just{definition of $\mathbb{Q}$} 
			\begin{pickavalue}{$x = p/q, p \in \mathbb{Z}, q \in \mathbb{Z}$  \just{pick such $p$ and $q$}}
				Then $p/q = \frac{-6 -\sqrt{2}}{2}$ \just{substitution} \\
				Then $\sqrt{2} = \frac{-6q-2p}{q}$ \just{algebra} \\
				Then $\exists p'', \exists q'', \sqrt{2} = p''/q''$ \just{$-6q-2p$ and $q$ are such $p''$ and $q''$, integers closed under addition/multiplication} \\
				Then $\sqrt{2} \in \mathbb{Q}$ \just{definition of $\mathbb{Q}$}  \\
				Contradiction! \just{$\sqrt{2} \not \in \mathbb{Q}$}
			\end{pickavalue}
		\end{assumption}{Then $x \notin \mathbb{Q}$ \just{assuming $x \in \mathbb{Q}$ leads to a contradiction}} \\\\\\

		{\bf Case 2:} $x = \frac{-6 + \sqrt{2}}{2}$\\
		\begin{assumption}{$x \in \mathbb{Q}$}
			Then $\exists p' \in \mathbb{Z}, \exists q' \in \mathbb{Z}, x = p/q$ \just{definition of $\mathbb{Q}$} 
			\begin{pickavalue}{$x = p/q, p \in \mathbb{Z}, q \in \mathbb{Z}$  \just{pick such $p$ and $q$}}
				Then $p/q = \frac{-6 +\sqrt{2}}{2}$ \just{substitution} \\
				Then $\sqrt{2} = \frac{6q+2p}{q}$ \just{algebra} \\
				Then $\exists p'', \exists q'', \sqrt{2} = p''/q''$ \just{$6q+2p$ and $q$ are such $p''$ and $q''$, integers closed under addition/multiplication} \\
				Then $\sqrt{2} \in \mathbb{Q}$ \just{definition of $\mathbb{Q}$}  \\
				Contradiction! \just{$\sqrt{2} \not \in \mathbb{Q}$}
			\end{pickavalue}
		\end{assumption}{Then $x \notin \mathbb{Q}$ \just{assuming $x \in \mathbb{Q}$ leads to a contradiction}} \\\\\

		Then $x \not \in \mathbb{Q}$\just{this holds in both of the two cases}\\
	\end{assumption}{Then $x^2+6x+8.5=0 \Rightarrow x \notin \mathbb{Q}$} \just{introduce implication}
\end{assumption}{Then $x \in \mathbb{R}, x^2+6x+8.5=0 \Rightarrow x \notin \mathbb{Q}$} \just{introduce universal}\\
\hspace*{13.5cm} $\blacksquare$


\end{enumerate}

\newpage

\item     An ``interpretation'' for a logical statement consists of   a domain $D$ (any non-empty set of elements)    and a meaning for each predicate symbol.    For example, $D = \{1,2\}$ and $P(x)$: ``$x > 0$''    is an interpretation for the statement $\forall x \in D, P(x)$    (in this case, one that happens to make the statement true).    For each statement below,    provide one interpretation under which the statement is true and    another interpretation under which the statement is false\,---\,    if either case is not possible, explain why clearly and concisely. You may reuse examples if you wish.
    \begin{enumerate}
	\item (4 pts.) $\exists x \in D, \forall y \in D, P(x, y) \implies P(y, x)$\\
        {\bf Solution:}\\
        To make the statement true, let $D = \{1\}$ and define $P(x, y) : x = y$. Then, $P(x,y)$ is true for any choice of $x,y \in D$.

 To make the statement false, we have to find an interpretation for which $\forall x \in D, \exists y \in D, P(x, y) \land \lnot P(y, x)$. Let $D = \N$ and $P(x, y) : x < y$. Then, this statement amounts to saying ``for every natural number $x$, you can always find another natural number that is larger than $x$,'' which is false.
	\item (4 pts.) $[\forall x \in D, \forall y \in D, P(x, y) \implies P(y, x)] \land [\forall x \in D, \forall y \in D, \lnot P(x, y)]$\\
        {\bf Solution:}\\
        Let $D = \{1\}$ and let $P(x,y) : x \neq y$. Then, this interpretation makes the statement true. The first part of the conjunction is vacuously true and clearly, $\lnot P(1, 1)$.

 To make the statement false, let $D = \{1, 2\}$ and $P(x, y) : x < y$. Then, $P(1, 2)$ is true, but $P(2, 1)$ is false. This makes the first part of the conjunction false, which makes the entire conjunction false.

	\item (4 pts.) $[\exists x \in D, Q(x)] \implies [\forall x \in D, P(x)]$\\
        {\bf Solution:}\\
        For an interpretation that makes the statement true, let $D = \{1\}$, $Q(x) : x = x$ and $P(x) : x = 1$. To make the statement false, we need to find an interpretation for which $[\exists x \in D, Q(x)] \land [\exists x \in D, \lnot P(x)]$ is true. Let $D = \{1\}$, $Q(x) : x = 1$, and $P(x) : x = 2$. 
    \end{enumerate}


\item     For each equivalence below,
    either provide a derivation
    from one side of the equivalence to the other
    (justify each step of your derivation with a brief explanation\,---\,
    for example, by naming one of the equivalences (See Tutorial 4),
    or show that the equivalence does not hold
    (warning: you cannot use a derivation to show non-equivalence\,---\,
    instead, think carefully about what an equivalence means,
    and how you can disprove it).
\begin{enumerate}
	\item (4 pts.) $\lnot Q \lor (P \land \lnot Q) \iff (\lnot P \lor Q) \land \lnot Q$\\
        {\bf Solution:}\\
        The equivalence does not hold. To see this, consider when $Q = F$ and $P = T$. On the LHS, we get $T$, but on the RHS, we get $F$.
	\item (4 pts.) $((P \lor Q) \implies R) \iff (P \implies (Q \lor R))$\\
        {\bf Solution:}\\
        The equivalence does not hold. To see this, consider when $P = F$, $Q = T$, and $R = F$. Then, the LHS is $F$, but the RHS is $T$.
\end{enumerate}

\newpage

\item (4 pts.) Use a truth table to prove that $(P \iff Q) \iff ((P \land Q) \lor (\lnot P \land \lnot Q))$.\\
{\bf Solution:}

The truth table is as follows (omitting $\lnot P$ and $\lnot Q$):

\[\begin{array}{c|c|c|c|c|c|c}
P 	&Q	&P \iff Q	&P \land Q	&\lnot P \land \lnot Q	&((P \land Q) \lor (\lnot P \land \lnot Q))		&(P \iff Q) \iff ((P \land Q) \lor (\lnot P \land \lnot Q)) \\ \hline
F 	&F 	&T 		&F		&T  				&T 							&T 								\\
F 	&T 	&F 		&F		&F				& F 							& T 								\\
T 	&F 	&F 		&F		&F				& F 							& T 								\\
T 	&T 	&T 		&T		&F				& T 							& T 								\\
\end{array}\]

There are two boolean variables in the equivalence, and hence there must be $2*2=4$ different rows (since each of $P$ and $Q$ holds two possible values. The equivalence is true in all cases.\\
   \hspace*{15cm} $\blacksquare$
\end{enumerate}





\end{document}


