chapter b

Responding to an email question from a listener, I explain how to derive a form of inconsistency from the assumption that True is related to False at type Bool.

I muse about the hopeless prospect of a single intrinsic conceptual decomposition of a problem domain in software engineering, and relate this to the idea of intrinsic identity we discussed recently for Relational Type Theory.

Where relational semantics for parametric polymorphism often includes a lemma called Identity Extension (discussed in Episode 10, on the paper "Types, Abstraction, and Parametric Polymorphism"), RelTT instead has a refinement of this called Identity Inclusion.  Instead of saying that the interpretation of every closed type is the identity relation (Identity Extension), the Identity Inclusion lemma identifies certain types whose relational meaning is included in the identity relation, and certain types which include the identity relation.  So there are two subset relations, going in opposite directions.  The two classes of types are first, the ones where all quantifiers occur only positively, and second, where they occur only negatively.  Using Identity Inclusion, we can derive transitivity for forall-positive types, which is needed to derive induction following the natural generalization of the scheme in Wadler's paper (last episode).

I give a brief glimpse at Phil Wadler's important paper "The Girard-Reynolds Isomorphism", which is quite relevant for Relational Type Theory as it shows that relational semantics for the usual type for Church-encoded natural numbers implies induction.  RelTT uses a generalization of these ideas to derive induction for any positive type family.

I talk through a proof I just completed that the type of relationally inductive naturals and the type of parametric naturals are equivalent.  This is similar to proofs one can find in a paper of Philip Wadler's titled "The Girard-Reynolds Isomorphism", which I plan to discuss in the next episode.

I discuss how to define internalized relational typings, implicit products, and two forms of natural number types, in RelTT.

In this episode, I discuss the semantics of the proposed six type constructors of RelTT.

This episode continues the introduction of RelTT by presenting the types of the language.  Because the system is based on binary relational semantics, we can include binary relational operators like composition and converse as type constructs!  Strange.  The language also promotes terms to relations, by viewing them as functions and then taking their graphs as the relational meaning.

This episode begins Chapter 11 of the podcast, on Relational Type Theory.  This is a new approach to type theory that I am developing.  The idea is to design a type system based on the binary relational semantics for types, which we considered in Chapter 10.  This episode recalls some of that semantics.