(pset3) Part 1: Warmup Problems

👈 Back to problem set index.

Problem One: Properties of Functions

Below is a list of purported functions. For each of those purported functions, determine where in the following Venn diagram that object goes.

A Venn diagram. There is a bubble marked Functions separating the outside from the inside. Inside of Functions are two partially-overlapping circles. One is labeled Injections. One is labeled Surjections. The intersection is labeled Bijections. Inside the bubble labeled "functions" and outside the other bubbles is the number 1. Outside all of the bubbles is the number 2.

To get you started, we’ve shown you where functions 1 and 2 go.

To submit your answers, run the starter files for PS3 and choose the “Properties of Functions” option. This program will write your answers to res/PropertiesOfFunctions.answers. You can use the provided test cases to check your work, and when you’re ready you can submit this file to Gradescope. Do not manually edit this file; use the program instead.

As a reminder, in this class we consider $0$ to be a natural number.

  1. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = 137$.

  2. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = -137$.

    Make sure you can explain why these first two items go where they do in this diagram!

  3. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.

    The notation $\abs{n}$ means “the absolute value of n.” For example, $\abs{\pi} = \abs{-\pi} = \pi$.

  4. $f : \mathbb{Z} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
  5. $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
  6. $f : \mathbb{R} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
  7. $f : \mathbb{N} \to \mathbb{R}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.

  8. $f : \mathbb{R} \to \mathbb{R}$ defined as $f(n) = \sqrt{n}$.

    The notation $\sqrt{n}$ denotes the principal square root of $n$, the nonnegative one.

  9. $f : \mathbb{R} \to \Set{ x \in \mathbb{R}\ \vert\ x \ge 0 }$ defined as $f(n) = \sqrt{n}$.
  10. $f : \Set{ x \in \mathbb{R} \ \vert\ x \ge 0 } \to \Set{ x \in \mathbb{R}\ \vert\ x \ge 0 }$ defined as $f(n) = \sqrt{n}$.
  11. $f : \Set{ x \in \mathbb{R} \ \vert\ x \ge 0 } \to \mathbb{R}$ defined as $f(n) = \sqrt{n}$.

  12. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \left\lbrace \begin{aligned} &n^2 + 2 &\text{if } n \lt 137 \\ &n^2 - 2 &\text{if } n \gt 137 \end{aligned} \right.\]

  13. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \left\lbrace \begin{aligned} &2 - n &\text{if } n \le 2 \\ &n - 2 &\text{if } n \ge 2 \end{aligned} \right.\]

  14. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \begin{cases} n-1 & \text{if } n \text{ is even} \\ n+1 & \text{if } n \text{ is odd} \\ \end{cases}\]

  15. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \begin{cases} n+1 & \text{if } n \text{ is even} \\ n-1 & \text{if } n \text{ is odd} \\ \end{cases}\]

Problem Two: All You Need Is Love

Let $P$ be a set consisting of some number of entities (cats, robots, and people). Here are three possible properties the set $P$ might have:

\[\begin{aligned} \text{(I)} & \quad \forall x \in P. Loves(x, x). \\ \text{(II)} & \quad \forall x \in P. \forall y \in P. (Loves(x, y) \to Loves(y, x)). \\ \text{(III)} & \quad \forall x \in P. \forall y \in P. \forall z \in P. (Loves(x, y) \land Loves(y, z) \to Loves(x, z)). \end{aligned}\]

Below is an incorrect proof of an incorrect theorem.

(Incorrect!) Theorem: If $P$ has properties (II) and (III), then $P$ also has property (I):

(Incorrect!) Proof: Assume $P$ has properties (II) and (III). We need to show that $P$ has property (I).

Pick any $x, y \in P$ such that $x$ loves $y\text.$ Since $x$ loves $y\text,$ by property (II) we know that $y$ loves $x\text.$ Then, since $x$ loves $y$ and $y$ loves $x\text,$ by property (III) we see that $x$ loves $x\text.$ And since $x$ loves $x\text,$ we see that $P$ has property (I), as required. $\qed$

The error in this proof turns out to be one of the most common mistakes we see on this problem set, so before we jump into formal proofwriting, let's take a minute to figure out what's the error is.

  1. The proof (correctly) starts off by assuming property (II) is true. Based on the assume/prove table for first-order logic, what variables, if any, should the proof introduce as a result of this? If any variables are introduced, what assumptions, if any, should the proof make about them? If any variables are introduced, what should the proof aim to show about them?

  1. The proof (correctly) starts off by assuming property (III) is true. Based on the assume/prove table for first-order logic, what variables, if any, should the proof introduce as a result of this? If any variables are introduced, what assumptions, if any, should the proof make about them? If any variables are introduced, what should the proof aim to show about them?

  1. The proof (correctly) starts off by stating it will prove property (I) is true. Based on the assume/prove table for first-order logic, what variables, if any, should the proof introduce as a result of this? If any variables are introduced, what assumptions, if any, should the proof make about them? If any variables are introduced, what should the proof aim to show about them?

  1. Based on your answers to parts (i), (ii), and (iii) of this problem, what is the error in this proof? Be as specific as possible. (If the proof contains multiple logical errors, we just care about the first one. After all, once it's made a logical error, everything after that point is irrelevant.)

  1. The "theorem" in this problem is not true. Draw an example of a world in which properties (II) and (III) are true, but property (I) is not. No justification is required.