We show that every finite Abelian algebra A from congruence-permutable varieties admits a full duality. In the process, we prove that A also allows a strong duality, and that the duality may be induced by a dualizing structure of finite type. We give
an explicit bound on the arities of the partial and total operations appearing in the dualizing structure. In addition, we show that the enriched partial hom-clone of A is finitely generated as a clone.
A finite algebra $bA=alg{A;cF}$ is emph{dualizable} if there exists a discrete topological relational structure $BA=alg{A;cG;cT}$, compatible with $cF$, such that the canonical evaluation map $e_{bB}colon bBto Hom( Hom(bB,bA),BA)$ is an isomorphism f
or every $bB$ in the quasivariety generated by $bA$. Here, $e_{bB}$ is defined by $e_{bB}(x)(f)=f(x)$ for all $xin B$ and all $fin Hom(bB,bA)$. We prove that, given a finite congruence-modular Abelian algebra $bA$, the set of all relations compatible with $bA$, up to a certain arity, emph{entails} the whole set of all relations compatible with $bA$. By using a classical compactness result, we infer that $bA$ is dualizable. Moreover we can choose a dualizing alter-ego with only relations of arity $le 1+alpha^3$, where $alpha$ is the largest exponent of a prime in the prime decomposition of $card{A}$. This improves Kearnes and Szendrei result that modules are dualizable, and Bentz and Mayrs result that finite modules with constants are dualizable. This also solves a problem stated by Bentz and Mayr in 2013.
We study the class of finite lattices that are isomorphic to the congruence lattices of algebras from a given finitely generated congruence-distributive variety. If this class is as large as allowed by an obvious necessary condition, the variety is c
alled congruence FD-maximal. The main results of this paper characterize some special congruence FD-maximal varieties.
The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Gi
ven a NW-deterministic Wang tile set, we construct an Mealy automaton, such that the plane admit a valid Wang tiling if and only if the Mealy automaton generates a finite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroup is undecidable.
We denote by Conc(A) the semilattice of all finitely generated congruences of an (universal) algebra A, and we define Conc(V) as the class of all isomorphic copies of all Conc(A), for A in V, for any variety V of algebras. Let V and W be locally fini
te varieties of algebras such that for each finite algebra A in V there are, up to isomorphism, only finitely many B in W such that A and B have isomorphic congruence lattices, and every such B is finite. If Conc(V) is not contained in Conc(W), then there exists a semilattice of cardinality aleph 2 in Conc(V)-Conc(W). Our result extends to quasivarieties of first-order structures, with finitely many relation symbols, and relative congruence lattices. In particular, if W is a finitely generated variety of algebras, then this occurs in case W omits the tame congruence theory types 1 and 5; which, in turn, occurs in case W satisfies a nontrivial congruence identity. The bound aleph 2 is sharp.
We denote by Conc(A) the semilattice of compact congruences of an algebra A. Given a variety V of algebras, we denote by Conc(V) the class of all semilattices isomorphic to Conc(A) for some A in V. Given varieties V1 and V2 varieties of algebras, the
critical point of V1 under V2, denote by crit(V1;V2) is the smalest cardinality of a semilattice in Conc(V1) but not in Conc(V2). Given a finitely generated variety V of modular lattices, we obtain an integer l, depending of V, such that crit(V;Var(Sub F^n)) is at least aleph_2 for any n > 1 and any field F. In a second part, we prove that crit(Var(Mn);Var(Sub F^3))=aleph_2, for any finite field F and any integer n such that 1+card F< n. Similarly crit(Var(Sub F^3);Var(Sub K^3))=aleph_2, for all finite fields F and K such that card F>card K.
We denote by Conc(L) the semilattice of all finitely generated congruences of a lattice L. For varieties (i.e., equational classes) V and W of lattices such that V is contained neither in W nor its dual, and such that every simple member of W contain
s a prime interval, we prove that there exists a bounded lattice A in V with at most aleph 2 elements such that Conc(A) is not isomorphic to Conc(B) for any B in W. The bound aleph 2 is optimal. As a corollary of our results, there are continuum many congruence classes of locally finite varieties of (bounded) modular lattices.
We introduce an extension, indexed by a partially ordered set P and cardinal numbers k,l, denoted by (k,l)-->P, of the classical relation (k,n,l)--> r in infinite combinatorics. By definition, (k,n,l)--> r holds, if every map from the n-element subse
ts of k to the subsets of k with less than l elements has a r-element free set. For example, Kuratowskis Free Set Theorem states that (k,n,l)-->n+1 holds iff k is larger than or equal to the n-th cardinal successor l^{+n} of the infinite cardinal k. By using the (k,l)-->P framework, we present a self-contained proof of the first authors result that (l^{+n},n,l)-->n+2, for each infinite cardinal l and each positive integer n, which solves a problem stated in the 1985 monograph of Erdos, Hajnal, Mate, and Rado. Furthermore, by using an order-dimension estimate established in 1971 by Hajnal and Spencer, we prove the relation (l^{+(n-1)},r,l)-->2^m, where m is the largest integer below (1/2)(1-2^{-r})^{-n/r}, for every infinite cardinal l and all positive integers n and r with r larger than 1 but smaller than n. For example, (aleph_{210},4,aleph_0)-->32,768. Other order-dimension estimates yield relations such as (aleph_{109},4,aleph_0)--> 257 (using an estimate by Furedi and Kahn) and (aleph_7,4,aleph_0)-->10 (using an exact estimate by Dushnik).
For a class V of algebras, denote by Conc(V) the class of all semilattices isomorphic to the semilattice Conc(A) of all compact congruences of A, for some A in V. For classes V1 and V2 of algebras, we denote by crit(V1,V2) the smallest cardinality of
a semilattice in Conc(V1) which is not in Conc(V2) if it exists, infinity otherwise. We prove a general theorem, with categorical flavor, that implies that for all finitely generated congruence-distributive varieties V1 and V2, crit(V1,V2) is either finite, or aleph_n for some natural number n, or infinity. We also find two finitely generated modular lattice varieties V1 and V2 such that crit(V1,V2)=aleph_1, thus answering a question by J. Tuma and F. Wehrung.
