An Analog of Slupecki’s Theorem for Polynomials

Abstract

Functional systems are among the main objects in discrete mathematics and mathematical cybernetics. The meaningful connection of functional systems with real cybernetic models of control systems, on the one hand, determines a series of essential requirements that are imposed on functional systems, and on the other hand, generates a class of important problems that have both theoretical and application significance. The theory of functional systems covers a wide range of problem areas, the main of them being the problems of completeness, relative completeness, expressibility, synthesis, analysis, and some others. The article considers the functional systems of polynomial functions falling in the following categories: (i) with natural coefficients in which the values of both the arguments and the functions themselves belong to the set of natural numbers; (ii) with integer coefficients in which the values of both the arguments and the functions themselves belong to the set of integer numbers; and (iii) with rational coefficients in which the values of both the arguments and the functions themselves belong to the set of rational numbers. The superposition operations (permutation of variables, renaming of variables without identifying them, identifying the variables, introducing a fictitious variable, removing a fictitious variable, and substituting one function into another) were taken as a set of operations in all these functional systems, and the problem of relative completeness is investigated for these systems. An algorithmic approach of this problem (an analog of Slupecki's theorem) is presented for the above-mentioned functional systems. In particular, it has been proven that the posed problem has a positive answer only for a functional system with natural coefficients, whereas the answer for the other two systems is negative.