Lab: A Plethora of Definitions

In this lab, we’ll be exploring the variety of definitions found in today’s reading that span relations and functions. These definitions test our ability to (a) read definitions made from logical propositions and (b) explore definitions using artificial and real-world examples.

Problem 1: Relatable

Consider the following artificial set:

\[S = \{\, a, b, c, d, e, f \,\}\]

As well as the following relation $R$ over $S$:

\[R = \{\, (a, b), (a, c), (b, d), (c, c), (d, b), (e, b), (e, f) \,\}\]

1. Compute the following operations over $R$:

   • $\mathrm{dom}(R)$.
   • $\mathrm{range}(R)$.
   • $R^{-1}$.
   • $R(a)$.

2. Instantiation this artificial example to a real-life example. That is, give real-life meaning to the set $S$ and the relation captured by $R$. Describe this real-life example in a sentence or two.

3. For each of the operations from part (a), interpret what the operation is “computing” in terms of your real-life example.

Problem 2: Representatives

Uniqueness and totality are deceptively complex definitions. In this problem, we’ll explore them using artificial and real-world examples.

1. Give artificial examples of the following relations:

   • A partial function.
   • An injective function.
   • A surjective function.
   • A left-unique partial function.
   • A bijection.

   Your examples should possess exactly the properties implied by the definitions and no more. For example, your injective function should not also be a bijection. This way, you can use your artificial example to understand precisely what it means for a function be injective.

2. The notion of partial and (total) functions is an important concept in computer science! Note that the notion of output in a mathematical function corresponds to the function returning a value. Other kinds of ways that a function can produce some kind of observable behavior, e.g., mutating variables, throwing an exception, or printing to the console, do not count as output.

   Give an example of a function in a programming language of your choice (e.g., Racket) that is:

   • A partial function.
   • A surjective function.

Problem 3: Applications to Programming

Here is a common piece of advice about function design couched in terms of the language of relations:

We should heavily favor designing total rather than partial functions whenever possible.

Keep in mind that when we talk about programming language functions, we only count as output the values that a function returns.

• In a sentence or two, clarify what we mean by total versus partial programming language functions.
• In a few sentences, describe why we might favor total versus partial functions by appealing to the definitions of relations we’ve talked about today.

Problem 4: Compression

Imagine that you are writing a file-compressing program ala zip. We can think of this program as a pair of functions that (a) takes a file as input and produces a (presumably) compressed version of the file as output and (b) takes a compressed version of the file and produces the original file as output.

When viewed as functions, we clearly want these functions to be total, i.e., we want to be able to compress any file. However, what about the other properties of functions?

• First suppose that the functions in question were surjective but not injective. In a few sentences, describe whether such a compression program would be a good compression program.
• Now suppose that the functions are injective but not surjective. In a few sentences, describe whether the resulting compression program would be a good compression program.

Problem 5: Why We Don’t Talk About Floats

In CSC 161, learn that IEEE floating-point numbers (i.e., the float and double types) are approximations of real numbers in a computer system. Because they are approximations, computations over floats are prone to imprecision. To account for this, we typically say two floats $x$ and $y$ are equal whenever the difference between the two is no larger than some threshold value, call it $\epsilon$ (LaTeX: \epsilon). To model floats, we will use numbers drawn from the reals, and so we can define equality between floats, written $\doteq$, as:

\[(\doteq) = \text{\{}(x, y) \mid x, y \in \mathbb{R}, \vert y - x\vert < \epsilon\text{\}}.\]

In this definition, we can think of $\epsilon$ as a pre-defined global constant.

1. Is $(\doteq)$ reflexive? If so, prove this fact formally. If not, give a counterexample demonstrating that the claim does not hold.
2. Is $(\doteq)$ symmetric? If so, prove this fact formally. If not, give a counterexample demonstrating that the claim does not hold.
3. Is $(\doteq)$ transitive? If so, prove this fact formally. If not, give a counterexample demonstrating that the claim does not hold.
4. Is $(\doteq)$ an equivalence relation? Briefly explain your answer using your results from the previous parts.
5. In a few sentences, describe the implications of your answer to part (d) to computer programming. In particular, in what situations do your results from (d) arise and potentially introduce hard-to-find bugs in a program?

Problem 6: Closure

Recall that the closure of a set under a property $P$ of a relation $R$ is the largest relation that satisfies $P$ and contains $R$. We can compute the closure of any relation under a property by repeatedly applying the property to generate new pairs to add to the relation until we can no longer add new pairs.

1. Consider the following universe $\mathcal{U}$ and relation $R : \mathcal{U} \times \mathcal{U}$:

   \[\begin{align*} \mathcal{U} =&\; \text{\{}a, b, c, d, e\text{\}} \\ R =&\; \text{\{}(a, b), (b, d), (c, e), (e, d)\text{\}} \end{align*}\]

   Compute the:

   • The reflexive closure of $R$.
   • The transitive closure of $R$.
   • The equivalence closure of $R$.

2. Now consider $\mathcal{U}$ to be the set of all Racket programs and $R$ to be the relation:

   \[\text{\{}(e_1, e_2) \mid e_1 \longrightarrow e_2\text{\}}.\]

   In other words, $R$ is the single-step relation, $e_1 \longrightarrow e_2$, of our Racket model of computation where $e_1$ takes a single step of evaluation to $e_2$. For example (* 3 (+ 4 5)) $\longrightarrow$ (* 3 9). Answer the following questions regarding $R$ in a sentence or two each:

   • Is $R$ reflexive? Why?
   • Is $R$ symmetric? Why?
   • What does the transitive closure of $R$ represent? (Hint: if you iterate the single-step relation on an expression repeatedly, what do you obtain?)