On the scales of computability potentials of n-element unars
by
Sergey Zhurkov
Novosibirsk State Technical University

In [1] there was given the definition of the scale < CT_n; <= > of computability potentials of n-element algebras. It determines what computability potential has an arbitrary n-element universal algebra. In [2]-[3] we present some results concerning the structure of these scales - a number of its atoms, coatoms, the length of the scale < CT_n; <= > . Also we considered the problem of inserting the lattice into the scale and the problem of scale diagram planarity.

Let CT_n¹ be the set of computability potentials of n-element unar algebras. We call the partially ordered set < CT_n¹; <= > the scale of computability potentials of n-element unars.

We present the following results for the scale < CT_n¹; <= > :

Theorem 1: a). A number of coatoms of the scale < CT_n¹; <= > is equal to d(n)+n-1 where d(n) is a number of prime divisors of n except 1.

b). A number of atoms of the scale < CT_n¹; <= > is equal to D(1)+...+D(n)+T₁^n-1+T₂^n-2+...+T_n-1¹ where D(i) is a number of divisors of i except 1; T_i^j - a number of representations of i as sum of not more than j non-zero natural numbers.

Theorem 2: For n >= 3 the scale < CT_n¹; <= > is not up or down semilattice.

Theorem 3: For any m < n the scale < CT_m¹; <= > is a retract for the scale < CT_n¹; <= > .

Theorem 3': The scale < CT_n¹; <= > is a retract for the scale < CT_n; <= > .

Theorem 4: For n >= 3 the scale < CT_n¹; <= > can't be represented as a planar graph.

Also we have found the structure of the scales < CT₂¹; <= > and < CT₃¹; <= > . The following statement takes place:

Statement: Any 2-element unar is conditionally rationally equivalent to one algebra from 4 pairwise conditionally rationally non-equivalent algebras B₁, ..., B₄. Any 3-element unar is conditionally rationally equivalent to one algebra from 14 pairwise conditionally rationally non-equivalent algebras A₁, ..., A₁₄.

[1] A.G.Pinus, S.V.Zhurkov. On the scales of computability potentials of universal algebras. // Contributions to Galois Connections, Potsdam, 2001 (in print).

[2] A.G.Pinus, S.V.Zhurkov. Some remarks on the scales of computability potentials of n-element algebras. // Algebra and Model Theory-3, Novosibirsk State Technical University, 2001, p.107-113.

[3] A.G.Pinus, S.V.Zhurkov. On the length of the scale of computability potentials of n-element algebras. // Siberian Mathematical Journal, 2002, vol.43, No.4, p.858-863.

Date received: January 17, 2003