\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