\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{mathtools}
\usepackage{enumerate}
\begin{document}
\noindent\underline{Homework 6} - MATH 2200 Spring 2017 \\
1. Write the sentence using quantifiers and predicates. You are welcome to specify a universe in each part to simplify your formulas. Clearly specify the predicates you use.
\begin{enumerate}[(a)]
\item  ``All real numbers are complex numbers." \\
\textit{Solution:} We read the sentence semi-formally as
\begin{center}``for all real numbers $x$, $x$ is a complex number"
\end{center} 
Let $\mathbb{R}$ be the predicate ``is a real number" and let $\mathbb{C}$ be the predicate ``is a complex number". We write
$$(\forall x)(\mathbb{R}x \rightarrow \mathbb{C}x).$$
\item ``The sum of the angles in any triangle is $180^{\circ}$." \\
\textit{Solution:} We read this sentence semi-formally as
\begin{center}``For all triangles with and for all angles $a$, $b$, and $c$ of the triangle, where $a, b,$ and $c$ are all different, the sum of the angles $a, b,$ and $c$ is $180^{\circ}$."\end{center} 
Let $T$ be the predicate ``is a triangle", let $Etabc$ be the predicate ``$a,b,$ and $c$ are the three different angles of the triangle $t$", and let $Sabc$ be the predicate ``the sum of the angles $a,b,$ and $c$ is $180^{\circ}$". Then we may write
$$(\forall t)(\forall a)(\forall b)(\forall c)((Tt \wedge Etabc) \rightarrow Sabc).$$
\item ``All Lipschitz functions with compact support are absolutely continuous and of bounded variation." \\
\textit{Solution:} We read the sentence semi-formally as
\begin{center}
``For all $f$, if $f$ is a Lipschitz function with compact support, then $f$ is absolutely continuous and $f$ is of bounded variation." 
\end{center}
Let $L$ be the predicate ``is a Lipschitz function with compact support", let $A$ be the predicate ``is absolutely continuous", and let $B$ be the predicate ``is of bounded support". We write
$$(\forall f)(Lf \rightarrow (Af \wedge Bf)).$$
\item ``There is a continuous function that is uniformly-continuous but is not H\"{o}lder-continuous." \\
\textit{Solution:} We read this semi-formally as
\begin{center}
``There exists an $f$ such that $f$ is continuous, and $f$ is both uniformly-continuous and not H\"{o}lder-continuous."
\end{center}
Let $C$ be the predicate ``is a continuous function", let $U$ be the predicate ``is uniformly-continuous" and, let $H$ be the predicate ``is H\"{o}lder continuous". We write
\begin{center}
$$(\exists f)(Cf \wedge (Uf \wedge \neg Hf)).$$
\end{center}
%\item ``For every vector space norm, there is both a metric induced by the vector space norm and for every metric, there is a topology induced by that metric."
\item ``Every even integer greater than $2$ can be expressed as the sum of two prime numbers." (this is the famous ``Goldbach's conjecture"...unknown if it is true or not!)\\
\textit{Solution:} We read this semi-formally as
\begin{center}
``For all $n$, if $n$ is both an integer and greater than $2$, then $n$ can be expressed as the sum of two prime numbers."
\end{center}
Let $I$ be the predicate ``is an integer", $G$ be the predicate ``greater than $2$", and $S$ be the predicate ``can be expressed as the sum of two prime numbers". We write
$$(\forall n)((In \wedge Gn) \rightarrow Sn).$$
\end{enumerate}
\vfill 
2. Let $R$ be the predicate ``is a real number" and let $I$ be the predicate ``is an integer". 
Is the sentence true or false? If false, explain why.
\begin{enumerate}[(a)]
\item $(\forall x)(Rx \rightarrow x^2 \geq 0)$ \\
\textit{Solution:} \textbf{It is true.} If $x$ is a real number, then $x^2 > 0$ because one of three cases are true: (i) $x$ is positive (hence $x^2 \geq 0$ because the product of two positive numbers is positive), (ii) $x$ is negative (hence $x^2 > 0$ because the product of two negative numbers is positive), or (iii) $x=0$ (hence $x^2=0$ because $0 \cdot 0 = 0$).
\item $(\exists x)(Ix \wedge x=\sqrt{2} )$ \\
\textit{Solution:} \textbf{This is false.} The number $\sqrt{2}$ is not an integer.
\item $(\forall x)(x^2+y^2=1 \rightarrow x^2=1-y^2)$ \\
\textit{Solution:} \textbf{This is true.} If $x^2+y^2=1$, the ``laws of algebra" tell us that we may subtract $y^2$ from both sides and simplify to achieve the formula $x^2=1-y^2$.
\item $(\forall x)((x>3) \rightarrow (\exists y)(Iy \wedge x+y=\frac{1}{2}))$ \\
\textit{Solution:} \textbf{This is false.} Consider a counterexample by letting $x=3+\dfrac{1}{3}$. This $x$ obeys the predicate $x>3$. For the sentence to be true, we must argue that there is an \textit{integer} $y$ that solves the equation $3+\dfrac{1}{3}+y=\dfrac{1}{2}$. But the laws of algebra allow us to subtract $3+\dfrac{1}{3}$ from both sides and simplify to arrive at the equation $y=\dfrac{1}{2}-3-\dfrac{1}{3}=\dfrac{1}{6}$. We observe that $\dfrac{1}{6}$ is not an integer. Moreover, we accept (via the theory of algebra) that this value for $y$ is the ``only possible value $y$ may take" and so we are certain that an integer found by some other method also will not work. \\
(note: More specifically, first we acknowledge that the integers ``are" or at least ``are encoded as" complex numbers -- this is similar to recognizing that in a programming language, a variable defined by the formula ``\texttt{int x = 0}" is ``the same, yet different" than ``\texttt{float x = 0}". We ``naturally" frame the equation $3+\dfrac{1}{3}+y=\dfrac{1}{2}$ as an equation where $y$ is a variable that ranges over the complex numbers and we have the {\color{blue}\href{https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra}{fundamental theorem of algebra}} to guarantee ``uniqueness" of the solution in the sense that this is a 1st degree equation and so the FTA tells us that there is exactly one solution (in the complex numbers, which ``includes" the integers). The FTA does not exist in number universes ``weaker" than the complex numbers! )
\end{enumerate}
\vfill
3. Consider the possible universes of quantification: the natural numbers $\mathbb{N}$ (i.e. the numbers $0,1,2,\ldots$), the integers $\mathbb{Z}$ (i.e. the numbers $\ldots -1,0,1,2,\ldots$), the real numbers $\mathbb{R}$ (i.e. everything on the number line), and complex numbers $\mathbb{C}$ (i.e. the numbers $a+bi$ where $i=\sqrt{-1}$ and $a$ and $b$ are real numbers). \\
List all universes (if any) in which the given formula is true. \\
\begin{enumerate}[(a)]
\item Let $Pxy$ denote ``is a solution of $x+2=y$": $(\forall x)(\exists y)(Pxy)$ \\
\textit{Solution:} This is true in all of the universes $\mathbb{N}, \mathbb{Z}, \mathbb{R},$ and $\mathbb{C}$. 
\item Let $Qxy$ denote ``is a solution of $2x+3y=1$": $(\forall y)(\exists x)(Qxy)$ \\
\textit{Solution:} This is true in only the universes $\mathbb{R}$ and $\mathbb{C}$. To see why it is not true in both $\mathbb{N}$ and $\mathbb{Z}$, consider when the quantifier $(\forall x)$ chooses the value $x=0$ ($0$ is in both $\mathbb{N}$ and $\mathbb{Z}$). Then the sentence is claiming $(\exists y)(2(0)+3y=1)$. But the only possible $y$ that could satisfy the equation is ``$y=\dfrac{1}{3}$" which is not in $\mathbb{N}$ and not in $\mathbb{Z}$. 
\item Let $Rx$ denote ``is a solution of $x^2+2=0$": $(\exists x)(Rx)$ \\
\textit{Solution:} The only universe this holds in is $\mathbb{C}$. Basic algebra tells us that the solution ``should be" given by subtracting $2$ to get $x^2=-2$ and taking square roots giving two solutions of the form $x = \pm \sqrt{-2}=\pm \sqrt{2}i,$ where $i=\sqrt{-1}$ is the ``imaginary number". Since these are the only ``possible" values for $x$ to be and these values are not in $\mathbb{N}, \mathbb{Z},$ or $\mathbb{R}$, we must exclude them from the list.
\item Let $Exy$ denote ``$x$ is equal to $y$" and $Bzxy$ denote ``$z$ is a number between $x$ and $y$": \\
$(\forall x)(\forall y)(\neg Exy \rightarrow (\exists z)(Bzxy))$ \\
\textit{Solution:} This holds for $\mathbb{R}$ and $\mathbb{C}$. It does not hold for either $\mathbb{N}$ or $\mathbb{Z}$ because, for instance, if the quantifier $(\forall x)$ chooses $x=0$ and the quantifier $(\forall y)$ chooses $y=1$, then these choices satisfy the predicate $\neg Exy$. However there does not exist a member of $\mathbb{N}$ or a member of $\mathbb{Z}$ between $0$ and $1$.
\end{enumerate}
\vfill
4. Diagram the scope of every quantifier that appears in the symbolized form of the sentence. Explain whether each instance of a variable is bound or unbound (i.e. free).
\begin{enumerate}[(a)]
\item ``for all $x$, there exists a $y$ such that $y<z$ and $x<y$" can be symbolized (with appropriate predicate symbols) as:
$$(\forall x)(\exists y)(Lyz \wedge Lxy)$$
\textit{Solution:}
$$\underbracket{(\forall x)\underbracket{(\exists y)(Lyz \wedge Lxy)}}$$
All variables except for the $z$ appearing in the predicate $Lyz$ are bound. The $z$ is free.
\item The definition of compactness in topology states \\
``For every open cover $u$ there is a finite subcover $f$ of $u$,"\\
and can be symbolized (with appropriate predicate symbols) as: 
$$(\forall u)(Ou \rightarrow (\exists f)(Sfu))$$
\textit{Solution:}
$$\underbracket{(\forall u)(Ou \rightarrow \underbracket{(\exists f)(Sfu))}}$$
All variables are bound.
\item H\"{o}lder's inequality in $L^p$ spaces states \\ ``For all measurable functions $f$ and $g$, for all $p\geq 1$ and for all $q \geq 1$, if $\dfrac{1}{p}+\dfrac{1}{q}=1$, then $\lVert fg\rVert_1 \leq \lVert f \rVert_p \lVert g \rVert_q$," \\
and can be symbolized (with appropriate predicate symbols) as:
$$(\forall f)(\forall g)\left[ (Mf \wedge Mg) \rightarrow [ (\forall p) (\forall q)[(Gp \wedge Gq) \rightarrow (Spq \rightarrow Lfg)] \right] ]$$
\textit{Solution:}
$$\underbracket{(\forall f)\underbracket{(\forall g)\left[ (Mf \wedge Mg) \rightarrow [ \underbracket{(\forall p) \underbracket{(\forall q)[(Gp \wedge Gq) \rightarrow (Spq \rightarrow Lfg)]]}} \right] }}$$
All variables are bound.
\end{enumerate}
\end{document}