Normal forms for characteristic functions on n-ary relations

Functions of type (n) are characteristic functions on n-ary relations. Keenan established their importance for natural language semantics, by showing that natural language has many examples of irreducible type (n) functions, i.e., functions of type (n) that cannot be represented as compositions of unary functions. Keenan (1987,1992) proposed some tests for reducibility, and Dekker (2003) improved on these by proposing an invariance condition that characterizes the functions with a reducible counterpart with the same behaviour on product relations. The present paper generalizes the notion of reducibility (a quantifier is reducible if it can be represented as a composition of quantifiers of lesser, but not necessarily unary, types), proposes a direct criterion for reducibility, and establishes a diamond theorem and a normal form theorem for reduction. These results are then used to show that every positive (n) function has a unique representation as a composition of positive irreducible functions, and to give an algorithm for finding this representation. With these formal tools it can be established that natural language has examples of n-ary quantificational expressions that cannot be reduced to any composition of quantifiers of lesser degree.