This paper is an extended version of our proceedings paper announced at LICS'16; in order to complement it, this version is written from a different viewpoint including topos-theoretic aspect on our work. Technically, this paper introduces and studies the class of semi-galois categories, which extend galois categories and are dual to profinite monoids in the same way as galois categories are dual to profinite groups; the study on this class of categories is aimed at providing an axiomatic reformulation of Eilenberg's theory of varieties of regular languages--- a branch in formal language theory that has been developed since the mid 1960's and particularly concerns systematic classification of regular languages, finite monoids, and deterministic finite automata. In this paper, detailed proofs of our central results announced at LICS'16 are presented, together with topos-theoretic considerations. The main results include (I) a proof of the duality theorem between profinite monoids and semi-galois categories, extending the duality theorem between profinite groups and galois categories; based on this results on semi-galois categories, we then discuss (II) a reinterpretation of Eilenberg's theory from a viewpoint of duality theorem; in relation with this reinterpretation of the theory, (III) we also give a purely topos-theoretic characterization of classifying topoi BM of profinite monoids M among general coherent topoi, which is a topos-theoretic application of (I). This characterization states that a topos E is equivalent to the classifying topos BM of some profinite monoid M if and only if E is (i) coherent, (ii) noetherian, and (iii) has a surjective coherent point. This topos-theoretic consideration is related to the logical and geometric problems concerning Eilenberg's theory that we addressed at LICS'16, which remain open in this paper.
Provided here is a proof of the duality theorem between profinite monoids and semi-galois categories in the full form of a contravariant equivalence between suitable categories. Our proof is given intentionally as a natural extension of an elementary proof of the duality between profinite groups and galois categories. This elementary proof will be valuable in its own right mostly for those who are particularly concerned with profinite monoids and with comparison with the case of profinite groups: The structure of profinite monoids is still mysterious in general, while their analysis plays a fundamental role in Eilenberg's theory @cite_17 . We shall not proceed to generalize this duality theorem itself in this paper, since we instead proceed to another direction in : We consider another dual (coherent topoi) of semi-galois categories and see that they are axiomatized exactly as coherent noetherian topoi with coherent surjective points. This consideration serves yet another (topos-theoretic) viewpoint on the classical Eilenberg variety theory.
@cite_17
2000856728
Let J be the pseudovariety of all finite J-trivial semigroups and let ΩnJ denote the topological semigroup of all n-ary implicit operations on J. The semigroup ΩnJ is generated by the n component projections together with the 2n−1 idempotents. Furthermore, ΩnJ is described as a free algebra of type (1,2) in a certain variety and the word problem is solved in this algebra. As a consequence, ΩnJ is countable, which settles a conjecture proposed by I. Simon.