\documentclass[10pt,a4paper]{article}
\usepackage{amsmath}
\usepackage[cm]{fullpage}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{tabularx}
\usepackage{listliketab}
\usepackage{graphicx}
\usepackage{color}
\usepackage{enumerate}
\usepackage{tikz}
\usetikzlibrary{arrows}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\begin{document}
\noindent\underline{Homework 7} - MATH 2200 Spring 2017 \\
1. Formula or not? If not, circle the problem.
\begin{enumerate}[(a)]
\item  $(\forall x)(\exists y)(Px \wedge (Gy \rightarrow (\exists z)(Qz)))$ \\
\textit{Solution:} This is a formula. 
\item $(\forall w)(\exists \circled{P}x)(Gpx) \vee (\forall x)(Wx \vee \neg Wx)$ \\
\textit{Solution:} The circled part is a problem because capital letters are reserved for predicates. Notice that our rules for formulas, on pg. 52 (d), says that the only way a quantifier like $\forall$ and $\exists$ may be part of a formula is if it is next to a \textit{variable} -- it does not allow quantification over predicates. \\
\textit{note: this restriction is imposed because we are formalizing ``first-order logic" instead of ``second-order logic"}
\item $(\exists a)(\exists b)(\forall w)(Qw \leftrightarrow (Pab \rightarrow Gbw)) \wedge Px$\\
\textit{Solution:} This is a formula. It may appear strange since the variable $x$ is free, but formulas are allowed to have free variables. \textit{Sentences} are formulas that cannot have free variables (pg. 54 in the text).
\item $(\forall$ \circled{$\exists$}$)(G$\circled{$\exists$}$ \wedge P$\circled{$\forall$}$)$  \\
\textit{Solution:} The first error is an error because the symbol $\exists$ is reserved for the existential quantifier, and it never stands for a variable, which is what must always follow any $\forall$. The second error is because it appears as if the predicate $G$ is acting on the ``variable" $\exists$ -- this is an error similar to the first. The third error is similar: $\forall$ is being used as if it was a variable, while it is never one.
\end{enumerate}
2. Write a formal deduction for the argument:
\begin{center}
``All norms yield a metric. All things that yield a metric also yield a topology. Therefore all norms yield a topology."
\end{center}
\textit{Solution:} We read this semi-formally as
\begin{center}``For all $x$, if $x$ is a norm, then $x$ yields a metric. For all $x$, if $x$ yields a metric, then $x$ yields a topology. Therefore for all $x$, if $x$ is a norm, then $x$ yields a topology." \end{center}
We will let $N$ be the predicate ``is a norm", $M$ be the predicate ``yields a metric", and $T$ be the predicate ``yields a topology". First note our premises: \\
\begin{tabular}{|lll|}
\hline
$\{1\}$ & (1) $(\forall x)(Nx \rightarrow Mx)$ & Premise \\
$\{2\}$ & (2) $(\forall x)(Mx \rightarrow Tx)$ & Premise \\
\hline
\end{tabular}\\
We would like to conclude $(\forall x)(Mx \rightarrow Tx)$: \\
\begin{tabular}{|lll|}
\hline
$\{1\}$ & (1) $(\forall x)(Nx \rightarrow Mx)$ & Premise \\
$\{2\}$ & (2) $(\forall x)(Mx \rightarrow Tx)$ & Premise \\
$\{1\}$ & (3) $Nx \rightarrow Mx$ & 1 US \\
$\{2\}$ & (4) $Mx \rightarrow Tx$ & 2 US \\
$\{1,2\}$ & (5) $Nx \rightarrow Tx$ & 1 2 T Law of Hypothetical Syllogism \\
$\{1,2\}$ & (6) $(\forall x)(Nx \rightarrow Tx)$ & 5 UG \\
\hline
\end{tabular}\\
\vfill
3. Write a formal deduction for the argument:
\begin{center}
``All vector spaces are a group under addition. The set of positive integers do not form a group under addition. Therefore the set of positive integers is not a vector space."
\end{center} 
\textit{Solution:} We read this semi-formally, letting $z$ stand in for the ``set of positive integers" as
\begin{center}
``For all $x$, if $x$ is a vector space, then $x$ is a group under addition. $z$ is not a group under addition. Therefore, $z$ is not a vector space."
\end{center}
We let $V$ be the predicate ``is a vector space" and $G$ be the predicate ``is a group under addition". Our premises are
\begin{tabular}{|lll|}
\hline
$\{1\}$ & (1) $(\forall x)(Vx \rightarrow Gx)$ & Premise \\
$\{2\}$ & (2) $\neg Gz$ & Premise \\
\hline
\end{tabular} \\
We would like to conclude $\neg Vz$: \\
\begin{tabular}{|lll|}
\hline
$\{1\}$ & (1) $(\forall x)(Vx \rightarrow Gx)$ & Premise \\
$\{2\}$ & (2) $\neg Gz$ & Premise \\
$\{1\}$ & (3) $Vz \rightarrow Gz$ & 1 US \\
$\{1\}$ & (4) $\neg Gz \rightarrow \neg Vz$ & 3 T Law of Contraposition \\
$\{1,2\}$ & (5) $\neg Vz$ & 2 3 T Law of Detachment \\
\hline
\end{tabular}
\vfill 
\end{document}