Define a relational structure (A,R) to consist of a set A and a n-ary relation on A for some ordinal n. A homomorphism f:(A,R)->(B,S) is a function f:A->B between the underlying sets of two relational structures of the same arity, such that f(R) c S. Write Str_n for the category of all n-ary relational structures and homomorphisms between them, and Str for the sum in CAT of Str_n over all ordinals n. 1. What is the term for the notion of full subcategory of either Str_n or Str? Failing that, what would be a suitable term? Relational categories? Categories of relational structures?
Familiar examples of such categories and an upper bound on their arities include those of groups (3), rings (4), fields (4), lattices (3), vector spaces over the field K (1+max(|K|,2)), directed graphs (2), posets (2), and categories (3).
I would expect complete lattices, complete Boolean algebras, topological spaces, and hypergraphs not to embed in Str_n for any n, because their structural elements (subsets, e.g. open sets) have no fixed cardinality bound, unlike n-tuples. A pointer to a proof of such nonembedding, or a demonstration of how to embed them, would be greatly appreciated. Since the concept is such a natural one, this question must surely have been looked at before.
2. What generalizations of Str or Str_n have been considered? One can make Str a bit more "communicative" by permitting homomorphisms between dissimilar structures (A,R), (B,S) of respective arities m<n. Do this by padding out (A,R) to arity n by defining R$(n) to be the set of n-tuples of A whose first m elements satisfy R. This probably looks about as useful today as the telephone did in 1879.
I can offer a few comments on arity concerning your category of "relational structures" Str. First, with regard to the list of examples where you mentioned an "an upper bound on their arities", I wondered if you meant (e.g. for groups) the *least* n such that groups embed into Str_n? That would be n=3 in the group case since each group's multiplication table can be regarded as a 3-ary relation R where (a,b,c) in R iff ab=c. For *any* n>3 one can define (for any group) an n-ary relation S where (a1,...,an) belongs to S iff a1 ... an = 1. The mult table for the group determines S and is recoverable from S. Thus a group embeds in Str_n for any n>3. However, n=3 is minimal for groups. Second, an n+1-ary relation R on S0 x ... x Sn spawns an infinite family of relations of all arities. These are generated by two operations: (1) Projection: the image of R in the composition R >---> (product all j) Sj ----> (product all j except i) Sj. (Simplicially speaking, this is the "i'th face" of R, i=0,...,n). (2) Repetition of coordinates: R x Si >---> S0 x ... x Si x Si x ... x Sn. (Simplicially speaking, this is the "i'th degenerate image" of R). There are equations, the "simplicial identities", which equate the various relations obtained this way. While none of these relations derived from R contain "new" information, they provide a useful alternative for defining homomorphisms between relations of different arities. Here's what I have in mind. Let R >--> A^m and S >--> B^n be relations , m and n arbitrary. Then define a homomorphism from (R,A) ---> (S,B) as the composite (R,A) --> (R',A) --> (S,B) where R' >---> A^n is a "simplicial image" of R >--> A^m obtained by some sequence of projection and repetition operations described above, and where (R',A) ---> (S,B) is a homomorphism in Str_n. This strikes me as being perhaps more "natural" (though more restrictive) than the "padding out" process you mentioned in your post. With this definition of homomorphism, an n-ary relation R >--> A^m corresponds to a functor (delta/[m])^op --> Sets. (Delta = cat of finite totally ordered sets and non-decreasing maps). The category Str can be viewed, equivalently, as: (1) fibred over delta (i.e. there's a discrete opfibration Str --> delta^op), or (2) a coalgebra for a certain cotriple on Cat, the (ordinary) category of small categories. (This must be qualified slightly since Str isn't small). The details of these assertions are in a paper I've written (I'd be glad to send a preprint). In that paper, I viewed monics R >--> A^(m+1), (more generally, A >--> A0 x ... x Am) as formulas in a first order theory. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++