Problem 1: 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.

1. Prove that list-eq is reflexive.

   Claim 1: If = is an equivalence relation, then list-eq is reflexive.

2. Prove that list-eq is symmetric.

   Claim 2: If = is an equivalence relation, then list-eq is symmetric.

3. Prove that list-eq is transitive.

   Claim 3: If = is an equivalence relation, then list-eq is transitive.

4. Conclude your proof that list-eq forms an equivalence relationship.

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 extensional 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.

Problem 3: Counting Sets

1. Prove that the Cartesian Product of two countable sets is itself countable, i.e., prove that if \(A\) and \(B\) are countable sets, then the set \(A\times B\) is also countable.

2. In one or two sentences, use your result from the previous problem to prove that the set of all pairs of natural numbers is a countable set, i.e., prove that the set \(S = \{(a,b)\,|\,a,b\in\mathbb{N}\}\) is countable.

3. Prove that the set of all 3-tuples of natural numbers is countable, i.e., prove that the set \(S = \{(a,b,c)\,|\,a,b,c\in\mathbb{N}\}\) is countable.