Recursive Types in IΞ

In the last IΞ post, I introduced the calculus and sketched the construction of some standard mathematical objects. In this post, I will dive a little deeper and construct of all the positive recursive types. The proof will be in an informal style (in particular, omitting the H constraints), but I have little doubt that the proof will go through.

Only a superficial familiarity with IΞ is needed to understand this proof; I adopt a set-theoretic style notation, so the proof should be approachable. Here’s a quick refresher of the primitives of IΞ.

  • Membership is application, so when I write x \in A, this is translated into IΞ as A x. Thus sets, unary predicates, and types are all the same thing.
  • Because membership and application are identified, universal quantification and the subset relation are also. \Xi A B means “A is a subset of B”, or “x in A implies x in B”. In particular, the pattern \Xi A (\lambda a. P a) can be interpreted as “for every a in A, P a”.
  • L is the set of all sets (whose existence does not lead to a contradiction in this system!). I will give its definition at the end of the article.
  • Other symbols have their usual interpretation, and I’ll include an appendix which gives them all precise definitions at the end.

Definition: A function F : L \mapsto L is called monotone if A \subseteq B \Rightarrow F A \subseteq F B.

Intuitively, the monotone functions correspond roughly to the functors in Haskell; they use their parameter in a positive way (appear to the left of an even number of arrows).

Definition: The type recursion combinator μ is defined as: x \in \mu F = \forall P\!\in\!L.\, F P \subseteq P \Rightarrow x \in P.

We are allowed to define things simply by giving a condition for membership like this. Formally, this definition starts out: \mu = \lambda F. \lambda x. \Xi L (\lambda P. \dots)

This definition intuitively says, x is in μ F if x is in every type closed under F. We will see that this definition corresponds to a type recursion combinator.

Lemma 1: If F is monotone, then F (\mu F) \subseteq \mu F.

Proof. Given x \in F (\mu F); show x \in \mu F. Expanding the definition of μ above:

Given P \in L, F P \subseteq P; show x \in P.

Observe \mu F \subseteq P: Suppose y \in \mu F, show y \in P. Since y \in \mu F, we have \forall P'\!\in\!L.\, F P' \subseteq P' \Rightarrow y \in P' by definition of μ. Letting P' = P, we have F P \subseteq P from above, so y \in P.

Therefore, x \in F (\mu F) \subseteq F P \subseteq P (by the monotonicity of F and \mu F \subseteq P). QED.

Now for the easy direction:

Lemma 2: If F is monotone, then \mu F \subseteq F (\mu F).

Proof. Given x \in \mu F; show x \in F (\mu F).

By the definition of μ, we have \forall P\!\in\!L.\, F P \subseteq P \Rightarrow x \in P. Let P = F (\mu F). We have F P = F (F (\mu F)) \subseteq F (\mu F) =  P by monotonicity of F and Lemma 1, therefore x \in P = F (\mu F). QED.

Which leads us to the recursion equation.

Theorem: If F is monotone, \mu F = F (\mu F). (Proof trivial by the two lemmas)

I’m using set equality here, i.e. mutual containment, which is probably a bit weaker than Leibniz equality. It is obvious from the definition that this fixed point is minimal.

Monotonicity is easy to prove for any of the standard positive types (products, coproducts, functions). So we can model a good variety of Haskell data types already; however these are standard inductive (least fixed point) types, no infinite structures allowed. I’m still working on the encoding and analogous proofs for ν (greatest fixed point), which is closer to Haskell.

Hopefully I’ll be able to port many libraries (maybe after a few totality annotations) without having to worry about partiality. But there are more pressing matters, such as finishing my interactive proof assistant for IΞ.

Definitions


  • \text{True} = \Xi H H, the True proposition.
  • K x y = x, the constant function.
  • U = K \text{True}, the set of all objects.
  • (f \circ g) x = f (g x), function composition.
  • (a \mapsto b) f = \Xi a (b \circ f), the set of functions from a to b.
  • L = U \mapsto H, the set of all sets.
  • a \Rightarrow b = \Xi (Ka) (Kb), implication.
  • \Lambda f x = \Xi L (\lambda t. f t x), universal quantification of types (like forall in Haskell)
  • a \times b = \Lambda (\lambda r. (a \mapsto b \mapsto r) \mapsto r), product type.
  • a \oplus b = \Lambda (\lambda r. (a \mapsto r) \mapsto (b \mapsto r) \mapsto r), coproduct type.
About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s