Skip to content
Identity Inclusion in Relational Type Theory episode artwork

Jan 18, 2021 13 min

Identity Inclusion in Relational Type Theory

from Iowa Type Theory Commute Hosted by Aaron Stump

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

Episode details come from the podcast's RSS feed.

Embed this episode

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

Ready to play

Identity Inclusion in Relational Type Theory

0:00 13:47

No transcript yet.

Requests help us decide what to transcribe next.

Frequently asked questions

How long is this episode of Iowa Type Theory Commute?

This episode is 13 minutes long.

When was this Iowa Type Theory Commute episode published?

This episode was published on January 18, 2021.

Can I download this Iowa Type Theory Commute episode?

Yes. Use the download control on the episode player to save the publisher-provided media file.