About Us

Executive Editor:
Publishing house "Academy of Natural History"

Editorial Board:
Asgarov S. (Azerbaijan), Alakbarov M. (Azerbaijan), Aliev Z. (Azerbaijan), Babayev N. (Uzbekistan), Chiladze G. (Georgia), Datskovsky I. (Israel), Garbuz I. (Moldova), Gleizer S. (Germany), Ershina A. (Kazakhstan), Kobzev D. (Switzerland), Kohl O. (Germany), Ktshanyan M. (Armenia), Lande D. (Ukraine), Ledvanov M. (Russia), Makats V. (Ukraine), Miletic L. (Serbia), Moskovkin V. (Ukraine), Murzagaliyeva A. (Kazakhstan), Novikov A. (Ukraine), Rahimov R. (Uzbekistan), Romanchuk A. (Ukraine), Shamshiev B. (Kyrgyzstan), Usheva M. (Bulgaria), Vasileva M. (Bulgar).

Additional Information

Authors

Login to Personal account

Home / Issues / № 2, 2014

Phisics and Mathematics

FUNCTIONALLY COMPLETE SEMIRINGS
Varankina V. I., Vechtomov E.M.

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.



References:
1. Werner H. Einführung in die allegemeine Algebra. – Mannheim, Wien, Zürich: Bibliographisches Institut, 1978.


Bibliographic reference

Varankina V. I., Vechtomov E.M. FUNCTIONALLY COMPLETE SEMIRINGS. International Journal Of Applied And Fundamental Research. – 2014. – № 2 –
URL: www.science-sd.com/457-24643 (21.08.2019).