Languages for defining sets in arbitrary algebras

This paper presents a self-contained and more elementary treatment of our mathematical theory of the syntax and semantics of language developed in [W-1] and [ W-2]. It applies this theory to the definition of subsets, and operators on subsets of the carrier of algebras. We show how regular and context-free sets of strings, recognizable sets of trees, and recursively enumerable (r.e.) sets of natural numbers or strings can be defined in a "natural" algebraic manner which defines "similar" types of sets for arbitrary algebras. We employ our mathematical framework to develop semantic and syntactic normal form theorems which explicate the relationship between different languages which define the same classes of sets and operators. We also investigate the relationship between our languages and the earlier work of Mezei, Eilenberg and Wright [M-W], [E-W] and the work of Eilenberg and Elgot [E-E].