Axioms and Decidability for Type Isomorphism in the Presence of Sums

ABSTRACT. We consider the problem of characterizing isomorphisms of types, or equivalently constructive cardinality of sets, in simultaneous presence of disjoint unions, Cartesian products, and exponentials. Mostly relying on classic results concerning polynomials with exponentiation that have not been used in our context, we derive: that the usual finite axiomatization known as High School Identities (HSI) is complete for a significant subclass of types; that it is decidable for that subclass when two types are isomorphic; that, for the whole of the set of types, a recursive extension of the axioms of HSI exists that is complete; and that, for the whole of the set of types, the question whether two types are isomorphic is decidable, that is, at least when base types are to be interpreted by finite sets. We also point out certain related open problems.