Types and Programming Languages Exercises

Preface

2 Mathematical Preliminaries

2.2 Ordered Sets

2.2.6

Exercise [★★ ↛]: Suppose we are given a relation R on a set S. Define the relation R′ as follows:

R′ = R ∪ {(s, s) | s ∈ S}.

That is, R′ contains all the pairs in R plus all pairs of the form (s, s). Show that R′ is the reflexive closure of R.

We need to show that:

• R′ is reflexive:
  • For every element s in S, we have (s, s) ∈ {(s, s) | s ∈ S} ⊆ (R ∪ {(s, s) | s ∈ S}) = R′, so R′ is reflexive.
• R ⊆ R′:
  • R ⊆ (R ∪ {(s, s) | s ∈ S}) = R′, so R ⊆ R′.
• R′ is smallest:
  • All elements in R′ is either an element in R or an element in {(s, s) | s ∈ S}, remove any element will cause R′ no longer containing either R or {(s, s) | s ∈ S}, which breaks the reflexive closure definition, so we can’t remove any element from R′, R′ must be smallest.

2.2.7

Exercise [★★, ↛]: Here is a more constructive definition of the transitive closure of a relation R. First, we define the following sequence of sets of pairs:

$$\begin{array}{ccc}{R}_0& =& R\\ R_{i+1}& =& R_i\cup \{(s,u)\mid \text{for some }t\text{, }(s,t)\in R_i\text{ and }(t,u)\in R_i\}\end{array}$$

That is, we construct each R_{i + 1} by adding to R_i all the pairs that can be obtained by “one step of transitivity” from pairs already in R_i. Finally, define the relation R⁺ as the union of all the R_i:

$$R^{+}=\bigcup _i{R}_i$$

Show that this R⁺ is really the transitive closure of $R$—i.e., that it satisfies the conditions given in Definition 2.2.5.

We need to show that:

• R⁺ is transitive:
  • If (s, t) ∈ R⁺ and (t, u) ∈ R⁺, then there must exist an i such that (s, t) ∈ R_i and (t, u) ∈ R_i. By definition, (s, u) will be added to R⁺ at some i + n step. So R⁺ is transitive.
• R ⊆ R⁺:
  • R = R₀ ⊆ $\bigcup _i{R}_i$ = R⁺, so R ⊆ R′.
• R⁺ is smallest:
  • All elements in R⁺ is either originally contained in R, or added to R⁺ at some later step. If we remove an element from R⁺ that is originally contained in R, R⁺ will no longer contain R, which breaks the transitive closure condition. Similarly, we also can’t remove an element that is added at some later step. If (s, u) is added at some later step, is must due to the set also containing some t, so that both (s, t) and (t, u) are in the set. If we remove (s, u), the condition that (s, t) ∈ R⁺ and (t, u) ∈ R⁺ implies (s, u) ∈ R⁺ will be broken. So we can’t remove any element from R⁺, R⁺ must be smallest.

2.2.8

Exercise [★★, ↛]: Suppose R is a binary relation on a set S and P is a predicate on S that is preserved by R. Show that P is also preserved by R^*.

We need to show that: For any s ∈ S and t ∈ S: (s, t) ∈ R^* and s ∈ P implies t ∈ P.

Since P is preserved by R, we have: For any s ∈ S and t ∈ S: (s, t) ∈ R and s ∈ P implies t ∈ P.

First, we prove that for all i, P is preserved by R_i that is defined in exercise 2.2.7. This can be done by induction:

• Base case: If i = 0, we have R_i = R₀ = R, which preserves P by definition.

• Inductive cases: Assume P is preserved by R_i, (s, t) ∈ R_i, (t, u) ∈ R_i, and the pair we add to R_i to get R_{i + 1} is (s, u):

  • If s ∈ P, since P is preserved by R_i, we have t ∈ P and u ∈ P. Since both s ∈ P and u ∈ P, adding (s, u) to R_i doesn’t break the preserving property.
  • If s ∉ P, trivially, adding (s, u) to R_i doesn’t break the preserving property.

  So we have P is also preserved by R_{i + 1}.

Since R^* is the union of all R_i, P is also preserved by R^*.

List of common unicode characters:

U+2032 PRIME : minutes, feet                       ′
U+219B RIGHTWARDS ARROW WITH STROKE:               ↛
U+2208 ELEMENT OF                                  ∈
U+2209 NOT AN ELEMENT OF                           ∉
U+2223 DIVIDES : such that, APL stile:             ∣
U+222A UNION : cup:                                ∪
U+2286 SUBSET OF OR EQUAL TO:                      ⊆
U+22C3 N-ARY UNION : z notation generalised union: ⋃
U+2605 BLACK STAR:                                 ★