|
Organizers |
On the scales of potentials of computability of universal algebras
by
Sergey Zhurkov
Novosibirsk State Technical University
Coauthors: Alexander Pinus
In [1] concepts of conditional term and conditional termal function on the universal algebra are defined. Conditional termal functions on an algebra are functions for which there exists some program of its calculations, which consists of the simplest subprograms (that calculate signature functions) with the help of superposition and conditional operator. So the set CT(A) of conditional termal functions of algebra A plays the role of computability potential for the algebra A. The work [2] defines the concept of conditional rational equivalence of two algebras A1 and A2 which is a formalization of equality of computability potentials of algebras A1 and A2, i.e. of equality of sets CT(A1) and CT(g(A2)) for some bijection g of the basic set of algebra A1 onto the basic set of algebra A2. It is proved in [2] that two finite algebras A1 and A2 are conditionally rationally equivalent iff there exists some bijection g such that g(Sub A2)=Sub A1 and g conjugate maps from Iso A2 with maps from Iso A1. Here Iso A is semigroup if innere isomorphisms of the algebra A.
Let CTn={CT(A)|A be an universal algebra with the basic set n={0, 1, ..., n-1}}. For F1, F2 from CTn let F1 ~ F2 iff there exists some permutation g on n such that F1=g(F2) and let CT(n)=CTn/ ~ . On CT(n) we define some order relation <= :F1/ ~ <= F2/ ~ iff there exists some permutation g on n such that g(F1) subset or equal F2. It is natural to think of the class CT(A)/ ~ as of the computability potential of n-element algebra A. So the order set < CT(n); <= > would be natural to call the scale of computability potentials of n-element algebras. The scale < CT(n); <= > has the largest and the smallest elements.
Theorem 1. a).For n >= 3 the scale < CT(n); <= > is not the up and down semilattice. b).The number of atoms of the scale < CT(n); <= > is [n/2]+1+R(n), the number of coatoms is (n-1)+K(n). Here K(n) is the number of different nonunit factors of the number n and R(n) is the number of pairwise nonconjugated maximal transitive subgroups of symmetric group on n.
Theorem 2. For any finite lattice L there exist F1/ ~ , F2/ ~ from CT(n) such that interval [F1/ ~ , F2/ ~ ] from the scale < CT(n); <= > is a lattice and the lattice L is embedded in the lattice [F1/ ~ , F2/ ~ ].
| References |
1. A.G.Pinus. On the conditional terms and identities of universal algebras. //Siberian Adv. Math., v.8, No.2, 1998, p.96-109.
2. A.G.Pinus. The calclulus of conditional identities and conditional rational equivalence. //Algebra and logic, v.37, No.4, 1998, p.432-459
Date received: January 17, 2001
Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cagi-03.