PS1, Part 3: Universally and Existentially Quantified Statements

👈 Back to problem set index.

Problem Seven: Proving Existentially-Quantified Statements

This problem is all about proving existentially-quantified statements, statements that claim that certain objects with certain properties exist. As a reminder, one of the most straightforward ways to prove an existential statement is simply to find an example of an object meeting the appropriate properties, then prove it indeed has those properties. Note that these proofs are often easy to write once you know what the requisite objects are, but often require some time and effort because you have to find those objects in the first place.

  1. Fill in the blanks to complete this direct proof about floors and ceilings.

    Theorem: There are real numbers $a$ and $b$ where $\floor{a} \cdot \ceil{b} \ne \floor{ab}$.

    Proof: Pick $a = \blank$ and $b = \blank$. Then we see that

    \[\floor{a} \cdot \ceil{b} = \floor{\blank} \cdot \ceil{\blank} = \blank \cdot \blank = \blank,\]

    but

    \[\floor{ab} = \floor{\blank \cdot \blank} = \floor{\blank} = \blank.\]

    Thus $\blank \ne \blank$, as required. ■

    This proof simply asks you to prove that real numbers $a$ and $b$ exist that meet certain requirements. You do not need to (and, in fact, we recommend against) trying to find a general broad pattern of real numbers that work. Just give two concrete values and prove they work. That's fine in this case because you are proving an existential statement, where a single example is sufficient.

  1. Fill in the blanks to complete this direct proof about sums of squares.

    Theorem: There exist natural numbers $a$, $b$, $c$, and $d$ such that $a > b > c > d > 0$ and $a^2 + b^2 + c^2 + d^2 = 137$.

    Proof: Pick $a = \blank$, $b = \blank$, $c = \blank$, and $d = \blank$. Then we see that

    \[\blank > \blank > \blank > \blank > \blank\]

    and

    \[\begin{aligned} a^2 + b^2 + c^2 + d^2 &= \blank^2 + \blank^2 + \blank^2 + \blank^2 \\ &= \blank + \blank + \blank + \blank \\ &= 137, \end{aligned}\]

    as required. ■

    Trial and error is a great strategy here. So is writing a quick Python script or C++ program. 😃

Fun fact: every natural number can be written as the sum of four perfect squares of natural numbers. This is called the four square theorem. However, not all natural numbers can be written such that all those natural numbers are nonzero and different from one another.

Problem Eight: Proving Mixed Universal and Existential Statements

This problem explores a style of proof in which we mix together universally-quantified and existentially-quantified statements. To do so, we’ll explore a concept called modular congruence.

Different numbers can yield the same remainder when divided by some number. For example, the numbers $1$, $12$, $23$, and $34$ all leave a remainder of one when divided by eleven. To formalize this relationship between numbers, we'll introduce a relation $\equiv_k$ that, intuitively, indicates that two numbers leave the same remainder when divided by k. For example, we'd say that $1 \equiv_{11} 12$, since both $1$ and $12$ leave a remainder of $1$ when divided by $11$, and that $8 \equiv_3 14$, since both $8$ and $14$ leave a remainder of $2$ when divided by $3$.

To be more rigorous, we'll formally define $\equiv_k$. If $k$ is an integer, we define $a \equiv_k b$ as follows:

We say that $a \equiv_k b$ when there exists an integer $q$ such that $a = b + kq$.

We’d read the statement “$x \equiv_k y$” aloud as “$x$ is congruent to $y$ modulo $k$.” For example, $7 \equiv_3 4$, because $7 = 4 + 3 \cdot 1$, and $5 \equiv_4 13$ because $5 = 13 + 4 \cdot (-2)$.

  1. Fill in the blanks to complete this direct proof about modular congruence.

    Theorem: For all integers $x$ and $y$ and any integer $k$, if $x \equiv_k y$, then $y \equiv_k x$.

    Proof: Let $x$, $y$, and $k$ be arbitrary integers where $x \equiv_k y$. We need to show that $y \equiv_k x$. To do so, we will show that there is an integer $q$ where $\blank$. (Notice that after stating our want-to-show as usual for a direct proof, we expanded the want-to-show to be more specific about what it means to show that. Now our want-to-show has the form of an existential (“… there exists an integer $q$ …”). This is an important structural trait to focus in on. It means that in the body of the proof, we are going to have to demonstrate that such a $q$ exists very concretely by proposing a specific value for $q$.)

    Because $x \equiv_k y$, we know there is an integer $r$ such that $\blank$. Now, pick $q = \blank$. (Here it is, our announcement of the value we are proposing for $q$. Next, we need to justify to the reader that our choice works. What follows is that justification. Always do it in this order: first announce the value, then justify.) Then we see that

    \[\begin{aligned} y & = \blank && \color{blue}{\textit{(Do not write } x + qk \textit { here; see below)}} \\ & = \blank \\ & = x + kq, \end{aligned}\]

    which is what we needed to show. ■

    As the note in the proof suggests, you must not start with the equation $y = x + qk$, and do algebra from there. The reason is that you do not know yet if that is true, and proofs must be a sequence of statements that are certain to be true. So you want to write something there that we already know is true, and use algebra to reach the last line as written.

  1. Prove for all integers $x$, $y$, $z$, and $k$ that if $x \equiv_k y$ and $y \equiv_k z$, we have $x \equiv_k z$.

  1. Prove for all integers $x$ and $k$ that $x \equiv_k x$.

    This proof will feel different from the previous problems because you aren’t assuming anything about $x$ or $k$ other than the fact that they’re integers. But the basic setup will feel the same: you’re searching for some choice of $q$ that makes some equality hold. Follow the general idea from earlier when structuring your proof: state, explicitly, what choice of $q$ you’re going to make, then prove that it has the right properties.