Affinely recursive sets and orderings of languages Original Research Article

An affinely recursive set S consists of integers defined by these rules: 1∈S, and if x∈S, then f(x)∈S for every f in a prescribed set F of affine functions with integer coefficients. If these functions are indexed by a set A, then each x in S except 1 corresponds to a word in the language L(A) of nonempty words over the alphabet A. Conditions are found for the correspondence to be bijective, so that the ordering of numbers in S induces an ordering of L(A). Moreover, since each x except 1 in S is of the form f(y) for some y in S and f in F, the set S is partitioned by F. The partition extends to L(A); viz., a component consists of words that end in the same letter. The distribution and limiting density within S of the numbers in each component is considered.