Blog

When does the universal quantifier commute with the existential quantifier? That is, when does $\forall x \in A. \exists y \in B. P(x, y)$ imply $\exists y \in B. \forall x \in A. P(x, y)$? Obviously, this is not always the case. There are many counter examples — every house in Aarhus has an owner but there is no person that owns all houses in Aarhus. Here, we will see two criteria where the universal quantifier commutes with the existential quantifier.

There is a problem with mixing impredicative polymorphism, i.e., polymorphism in System F, and side effects, e.g., references, continuations, etc. This problem arises when we allow arbitrary computations to considered polymorphic. The solution usually used is to restrict the programming language so that only values are allowed to be abstracted as polymorphic programs. Here we discuss this issue and its solution which is usually referred to as “Value Restriction”.