Problem 1: The Cyclotron

A cycle in a relation \(R\) is a sequence of \(k\) distinct elements \(x_1, \ldots, x_k\) that are related in sequence and the sequence ends with \(x_k\) and \(x_1\) being related, i.e.,

\[ (x_1, x_2), (x_2, x_3), \ldots, (x_{k-1}, x_k), (x_k, x_1) \in R. \]

A cycle is considered non-trivial if \(k \geq 2\).

1. Give an artificial example equivalence relation and a non-trivial cycle in that equivalence relation.

2. Give a real-world example of an equivalence relation and an example of a non-trivial cycle in that relation.

3. An anti-symmetric relation is one where no pair of relations are related in both directions. More formally:

   Definition (Anti-symmetric): a relation \(R\) is anti-symmetric if the relation does not go “in both directions:”

   \[ \forall x, y \ldotp (x, y) \in R \rightarrow (y, x) \in R \rightarrow x = y. \]

   In other words, if a pair of elements are related in both directions, then they must be equal. A relation that is reflexive, anti-symmetric, and transitive is called a partial order.

   Definition (Reflexivity): a relation \(R\) is reflexive if it relates every element in the universe to itself.

   \[ \forall x \ldotp (x, x) \in R \]

   Definition (Transitivity): a relation \(R\) is transitive if whenever any pair of elements are related with a common element in the middle, the first and last elements are also related.

   \[ \forall x, y, z \ldotp (x, y) \in R \rightarrow (y, z) \in R \rightarrow (x, z) \in R \]

   For example, the \((\leq)\) relation between the integers (\(\mathbb{Z}\)) forms a partial ordering.

   Prove the following property regarding cycles and partial orderings.

   Claim (Cycles and Partial Orders): let \(R\) be a partial order. Then \(R\) possess no non-trivial cycles.

   (Hint 1: we are proving the absence of a thing. What is a good proof strategy for proving such “non”-properties?)

   (Hint 2: once you have established your proof strategy, try to show there are no non-trivial cycles for abstract cycles of varying lengths. Note the pattern in reasoning in each case and then generalize that pattern in your eventual proof.)

Problem 2: Structural Equivalence

When defining equality operations over custom datatypes, it is useful to default to a notion of structural equivalence. At a high-level, structural equivalence declares that two objects are equal if their components are equal, recursively. For example, we might define equality over lists as follows:

(define list-eq
  (lambda (l1 l2)
    (match (cons l1 l2)
      [(cons '() '()) #t]             ; + Two empty lists are equal
      [(cons (cons _ _) '()) #f]      ; + An empty and non-empty list
      [(cons '() (cons _ _)) #f]      ;   are not equal
      [(cons (cons x xs) (cons y ys)) ; + Two non-empty lists are equal
       (and (= x y)                   ;   whenever their heads and tails
            (list-eq xs ys))])))      ;   are equal

Show that for any pair of lists, if = is an equivalence relation over the values of the lists, then list-eq also forms an equivalence relationship.

(Hint 1: remember, to show that an equivalence, you must show that each of the properties of an equivalence holds.)

(Hint 2: lists are structurally recursive! Therefore, you will likely need to employ structural induction to reason about list-eq.)

Problem 2: Ugh, Functions

In this problem, we’ll examine the equality of mathematical functions and some of the trickiness involved as we try to apply similar reasoning to programming functions.

1. Consider a domain \(S\) and range \(T\) and two relations \(f_1, f_2 \subseteq S \times T\) that each fulfill the properties of a function. Give a formal definition of equality (\(=\)) between two functions \(f_1\) and \(f_2\) in terms of their interpretation as relations.

2. Show that your definition of function equality forms an equivalence over the elements of \(S\) and \(T\).

3. Your previous definition is an extensional definition of equality for functions. By extensional, we mean that we judge the objects equal if they have the same observable behavior, also called observable equivalence.

   In a few sentences, describe how your answer to part (a) fulfills this notion of observable equivalence. Specifically, what are you observing in terms of the behavior of the two functions?

4. In contrast to extensional definitions, we might instead employ an intensional definition of equality where we judge two objects equal if their definitions are the same. Note that while it seems like the relational definition of equality you defined earlier is intensional, it is actually extensional because relations capture the external behavior of a function as your described in the previous part.

   Let’s suppose that we define equality between functions in an intensional style rather than intensional style.

   Two functions \(f_1\) and \(f_2\) are equivalent if they share identical definitions.

   For example \(f_1(x) = x + 1\) and \(f_2(x) = x + 1\) are equivalent functions under this definition because they have identical definitions.

   Prove that this intensional definition of equality indeed forms an equivalence. (Hint: don’t overthink this! The strictness of intensionality makes the proof very straightforward.)

   Also, in a few sentences, describe why this intensional definition of function equivalence is undesirable, especially as we think about functions in the context of programming.

5. From the previous part, it is clear that an intensional definition of function equality is not what we want as programmers. However, even extensional equality/observational equivalence is problematic, especially as we think about programming functions!

   Think about the properties that a programming function fulfills and brainstorm one situation in which an observational definition of function equality runs into problems. Keep in mind that as programmers, we would like to be able to use our definition of equality to compute whether two functions are equal. So by “problems”, we really mean problematic functions that might make our observational definition of equality difficult, impossible, or ambiguous to use in practice.