manysorted

Manysorted is a term used in universal algebra, model theory, and formal specification to denote structures or logics that distinguish multiple sorts (types) of objects rather than a single universe. It encompasses two related ideas: manysorted algebras and manysorted logic. In a manysorted framework, the domain of discourse is partitioned into several sorts, and operations and predicates have specified input and output sorts.

Formally, let S be a nonempty set of sorts. A manysorted signature consists of a collection of operation symbols, each with an arity described by a sequence s1, ..., sn and a result sort s, where each si and s belong to S; constant symbols are 0-ary operations. A manysorted algebra A assigns to each sort s ∈ S a nonempty carrier A_s, and to each operation symbol f a function f^A: A_{s1} × ... × A_{sn} → A_s. A homomorphism h from A to B is a family of maps h_s: A_s → B_s that preserves every operation symbol. Equations and identities are written with terms that have a well-defined sort, ensuring type-correctness.

Manysorted logic extends single-sorted first-order logic by introducing sorts, typed variables, and sort-specific quantification. Interpretations map each sort to a domain and assign meanings to symbols in a way that respects their input and output sorts. Satisfaction, consequence, and model theory are developed analogously, with attention to well-typed formulas.

Applications include modular algebraic specifications and formal methods. Manysorted frameworks underpin languages such as OBJ and CafeOBJ, supporting heterogeneous data modeling, subsorts, and clear separation of concerns in software specification and verification. A simple graph model, with sorts Node and Edge and operations like src: Edge → Node and dst: Edge → Node, illustrates how multi-sorted structures organize interacting domains.