\(\newcommand{\set}[1]{\{\, #1 \,\}}\)

In this lab, we’ll be exploring the variety of definitions found in today’s reading that span relations and their properties. 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: 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) = \set{(x, y) \mid x, y \in \mathbb{R}, |y - x| < \epsilon}. \]

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 that the claim does not hold.
2. Is \((\doteq)\) symmetric? If so, prove this fact formally. If not, give a counterexample demonstrating that that the claim does not hold.
3. Is \((\doteq)\) transitive? If so, prove this fact formally. If not, give a counterexample demonstrating that 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 does your results from (d) arise and potentially introduce hard-to-find bugs in a program?

Problem 2: 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} =&\; \set{a, b, c, d, e} \\ R =&\; \set{(a, b), (b, d), (c, e), (e, d)} \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:

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

   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?)