Number of functions in classes given by central predicates (Q1088650)

The aim of this paper, considering metric problems in the k-valued logics, is to obtain asymptotics of the logarithm of the number of functions in n variables in every class of the family of precomplete classes given by central predicates. A function \(f(x_ 1,...,x_ n)\), such that both the arguments and the function assume values in \(E_ k=\{0,1,...,k-1\}\), is said to preserve a predicate \(R(y_ 1,...,y_ h)\) if for any h n-tuples \({\tilde \alpha}_ 1=(\alpha^ 1_ 1,...,\alpha^ 1_ n),...,{\tilde \alpha}_ h=(\alpha^ h_ 1,...,\alpha^ h_ n)\), where all \(\alpha^ j_ i\in E_ k\), the following implication holds: \[ (\forall i)\quad (R(\alpha^ 1_ i,...,\alpha^ h_ i)=1)\Rightarrow R(f({\tilde \alpha}_ 1),...,f({\tilde \alpha}_ h))=1. \] A predicate \(R(y_ 1,...,y_ h)\) on \(E_ k\) is said to be central if i) (\(\forall i,j)\) ((i\(\neq j)\&(\beta_ i=\beta_ j)\Rightarrow R(\beta_ 1,...,\beta_ i,...,\beta_ j,...,\beta_ h)=1)\); ii) \(R(\beta_ 1,...,\beta_ h)=1\Rightarrow R(\beta_{i_ 1},...,\beta_{i_ h})=1\) for each permutation \((i_ 1,...,i_ h)\) of the numbers 1,...,h; and iii) there exists an element c in \(E_ k\) such that (\(\forall i)\) \((\beta_ 1,...,\beta_{i-1},...,\beta_ h)\) \((R(\beta_ 1,...,\beta_{i-1},c,\beta_{i+1},...,\beta_ h)=1).\) C\({}_ R(n)\) denotes the number of functions depending on variables in the class of all functions preserving the arbitrary central predicate \(R(y_ 1,...,y_ n)\). \(C_ R(n)\) is found, for \(h=1\); and the author obtains asymptotics of ln \(C_ R(n)\), as n increases, for \(h\geq 2.\) A subset \(A\subseteq E_ k\) is said to be admissible for a predicate R if \(R(\beta_ 1,...,\beta_ h)=1\) for all \(\beta_ 1,...,\beta_ h\in A\). Let \(d(R)=\max | A|\), where the maximum is taken over all subsets A of \(E_ k\) admissible for R. The following results are obtained: \(C_ R(n)\geq d(R)^{k^ n}\); \(C_ R(n)\leq d(R)^{k^ n(1+\epsilon (n))}\), where \(\epsilon\) (n)\(\to 0\) as \(n\to \infty\) (more exactly, \(\epsilon (n)=O(n((k-1)/k)^{n/3}))\); and ln \(C_ R(n)n\sim k^ n \ln d(R)\) as \(n\to \infty\), with a suitable definition for \(\sim.\) This last result permits the proof of the hypothesis proposed by \textit{J. Demetrovics}, \textit{L. Hannák}, and \textit{L. Rónyai} [C. R. Math. Acad. Sci., Soc. R. Can. 4, 363-366 (1982; Zbl 0509.08009)].