The research was performed within the state task of the RF Ministry of Education and Science, the project 1.1375.2014/K.

 A semiring is an algebraic structure áS, +, ×ñ with binary operations of addition + and multiplication × such that the following axioms are satisfied: addition is associative and commutative, multiplication is associative and distributive over addition from both sides.

If a semiring S has an additive identity 0, besides it is a multiplicative zero, then S is called a semiring with zero.

A set SS of all functions S®S is a semiring with respect to pointwise addition and multiplication of functions: (f+g)(a)=f(a)+g(a) and (fg)(a)=f(a)g(a) for all f, gÎSS, aÎS. We identify every element a ÎS with the corresponding constant function. We regard the variable x that takes values in S as the identity map y=x.

By S*[x] denote the subsemiring generated by all constants aÎS and the function x, i.e., by the set SÈ{x}. Note that for a ring S we have obtained the new ring S*[x].

A monomial in a semiring S*[x] is a product of an element from S and several copies of variable x with an arbitrary order of the multipliers. All these multipliers are considered as elements from the semiring SS. Every function fÎS*[x] is a sum of several monomials and may be a constant term a0ÎS. For a commutative semiring S every function f from the semiring S*[x] has the following representation:

f=f(x)=a0+a1x+n1x+a2x2+n2x2+…+amxm+nmxm,

where mÎN, aiÎSÈ{0} and niÎN0  for each i=0, 1, …, m. Note that if S does not have 0 then the coefficients can not equal 0 simultaneously. If S is a commutative semiring with 1, then f=a0+a1x+a2x2+…+amxm.

Similarly, by S*[x1,…, xn] denote the subsemiring in a ring  of all functions Sn®S that is generated by the set SÈ{x1, …, xn}. Here, each element aÎS is identified with the constant Sn®{a}; and independent variables x1,…, xn are considered as i-th projections. It means that xi(a1,…, an)=ai for every a1,…, anÎS, where i=1,…, n.

A function from a semiring S*[x1,…, xn] is called a polynomial function of n variables x1,…, xn.

A semiring S is called functionally complete if SS=S*[x].

We write a polynomial function fÎS*[x] as f(x)=a0+g(x), where a0ÎS and the polynomial function g(x)ÎS*[x] does not have a constant term. If f does not have a constant term, then f(x)=g(x).

Theorem 1. A functionally complete semiring is a finite ring.

Proof. Let S be an arbitrary functionally complete semiring. Let us split the proof into 3 steps and prove consistently the following:

(I) S is finite.

(II) S is a semiring with 0.

(III) S is a ring.

The statement (I) is obvious. Indeed, if a semiring S is infinite then ïSçïSç=2ïSç. But this power of the set is more than |Sç=÷S*[x]ê.

(II) We will prove existence of 0 in S in several stages.

1) Let J={aÎS: a+a=a} be the set of all additive idempotents in the finite semiring S. It is well-known that there exists at least one idempotent in a finite semigroup. Hence, J is not empty. It is clear that J is an ideal of the semiring S. It is not difficult to verify that on an additive idempotent semiring J there exists the order £ such that a£ b Û $cÎS a+c=b ("a, bÎJ). This order coincides with the natural order: a£ b Û a+b=b. Note that J is an upper lattice with respect to the order. It is easy to see that a polynomial function g(x)ÎS*[x] without a constant term takes additive idempotents to additive idempotents, i.e., g(J)ÍJ. Besides, the function g is isotonic on J, i.e., a£ b Þ g(a)£ g(b) for all a, bÎJ.

2) The ideal J consists of a single element q. Assume to the contrary that ïJ ç³ 2. Then in the finite upper lattice J there exist elements a< b. Now let us take a polynomial function fÎS*[x] satisfying f(a)=b and f(b)=a. We have

a0+g(a)=b, a0+g(b)=a, g(a)£ b, g(b)£ a, g(a)< g(b).

It follows that a1=g(a)< a< b in J. Note that if a summand a0 is absent, then we get the contradiction: b=g(a)< g(b)=a. Arguing in the same way for the pair a1< a, we get an element a2< a1 in J. As a result we build an infinite set in the finite set J. This is impossible. Therefore, J={q}, having

q+q=q, qs=q=sq for any sÎS.

3) For an arbitrary polynomial function gÎS*[x] without a constant term we have g(q+s)=q+g(s) for any sÎS. This follows from the properties of the element 0 which were indicated in the item 2), the property g(q)=q, and the identity (q+s)n=q+sn being true for all nÎN.

4) Finally, let us prove that the element q is an additive identity, i. e., q+s=s for every sÎS. Let us take s¹q and consider the element t=q+s.

At first, let t=q, i.e., q+s=q. Let us choose fÎS*[x] such that f(q)=s. We get s=a0+g(q)=a0+q. Hence q=q+s=a0+q+q=a0+q=s. Contradiction. If we write f without a0, then we have s=q too.

Now, let t¹q. In this case there exists a function fÎS*[x] satisfying f(q)=q and f(s)=f(t)=s. From 3) we get

s=f(t)=a0+g(q+s)=a0+q+g(s)=q+a0+g(s)=q+f(s)=q+s.

If a0 is absent, then we have s=q+g(s)=q+s too.

From 2) and 4) we can conclude that S is a semiring with zero 0=q.

(III) Let us show that S is a ring. If a is a nonzero element from S then we take a function fÎSS such that f(0)=a and f(a)=0. We have f(x)=a0+g(x), a0=f(0)=a, and a+g(a)=0. This means that the element a has the additive inverse.

Theorem 1 and a corresponding result from [1] imply the following:

Theorem 2. A semiring S is functionally complete if and only if S is either an one-element semiring or a two-element ring with zero multiplication, or isomorphic to the complete matrix ring Mn(Fq) over a finite field Fq.