PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 63 (77), 1998 26–30

ON GENERAL AND REPRODUCTIVE SOLUTIONS OF FINITE EQUATIONS

Sergiu Rudeanu

Communicated by Žarko Mijajlović

Abstract. Prešić and his followers have studied the general and reproductive solutions of a certain equation over a finite set. In this paper we provide simple characterizations of these solutions.

The concept of general or parametric solution of an equation is well known in various contexts. Schröder [21, vol. 1], introduced reproductive general solutions of Boolean equations, which were extensively studied by Löwenheim [13], [14] and his followers (the term “reproductive” was introduced by Löwenheim [14]; cf. Rudeanu [19]). Prešić [15] initiated the axiomatic study of general solutions and reproductive general solutions, i.e., for the most general concept of equation. This line of research was followed by Prešić [17], Božić [9], Banković [1], [2], [3], Rudeanu [20] and Chvalina [10]. In their monograph [12], unfortunately unpublished, Kečkić and Prešić showed that the concept of reproductive solution is very important in various fields of mathematics.

A further step was taken by Prešić [16], who considered the case of equations over a finite set, on which he introduced a certain algebraic structure yielding a reproductive solution in compact form; see also Ghilezan [11]. Then Prešić [18] introduced within this framework an equation which generalizes Boolean and Post equations in one unknown and for which he obtained all reproductive solutions. Other descriptions of all general solutions and all reproductive solutions were then obtained by Banković [4]–[8].

In this paper we provide simpler characterizations of the general and reproductive solutions of that equation.

We first recall all necessary prerequisites.

AMS Subject Classification (1991): 04A05; 06E30, 08A99

Let T = {t_{0}, t_{1},…, t_{m}} be a finite set and 0, 1 two elements which may be either outside T or two distinguished elements of T. Define two binary partial operations + and · on T ∪ {0, 1} by the following conditions:

(1)  \begin{aligned}x + 0 & = 0 + x = x, \\ x · 0 & = 0 · x = 0, \\ x · 1 & = 1 · x = x, \end{aligned}

for every x ∈ T ∪{0, 1}; the operation · is usually denoted by concatenation. Define also

(2)  x^{y} = \{ \begin{matrix}1, & if x = y, \\ 0, & if x ≠ y, \end{matrix}

for every x, y ∈ T ∪ {0, 1}, as well as a family ∑_{i=0}^{n} of partial operations given by

(3)  ∑_{i=0}^{0} x_{i} = x_{0}, ∑_{i=0}^{n+1} x_{i} = (∑_{i=0}^{n} x_{i}) + x_{n+1}  (n ∈ ℕ).

Proposition 1. Every function f: T → T can be written in the form

(4)  f(x) = ∑_{i=0}^{m} f_{i}x^{t_{i}}  (∀x ∈ T),

where the coefficients are uniquely determined by

(5)  f_{k} = f(t_{k})  (k = 0, 1,…, m).

Proof. For each k = 0, 1,…, m, the equality

(6)  f(t_{k}) = ∑_{i=0}^{m} f(t_{i})t_{k}^{t_{i}}

holds because the right-hand side of (6) contains the term f(t_{k})t_{k}^{t_{k}} = f(t_{k}), while the other terms are 0. Conversely, (4) implies, for each k = 0, 1,…, m,

f(t_{k}) = ∑_{i=0}^{m} f_{i}t_{k}^{t_{i}} = f_{k}t_{k}^{t_{k}} = f_{k}.

The equation introduced by Prešić and studied by him and Banković is

(7)  a_{0}x^{t_{0}} + a_{1}x^{t_{1}} + … + a_{m}x^{t_{m}} = 0,

where a_{0}, a_{1},…, a_{m} ∈ {0, 1} and the unknown x ∈ T. Let us denote by S the (possibly empty!) set of solutions of equation (7).

Remark [18]. For x = t_{k} the left-hand side of equation (7) reduces to a_{k}, hence

(8)  t_{k} ∈ S ⇔ a_{k} = 0  (k = 0, 1,…, m),

therefore equation (7) is consistant if and only if a_{k} = 0 for some k. In other words, taking also into account the associativity of the operation · on {0, 1}, we see that the consistency condition for equation (7) is

(9)  a_{0}a_{1} … a_{m} = 0.

The next definition is borrowed from the axiomatic framework introduced by Prešić [15].

Definition. Suppose equation (7) is consistent. A function f: T → T is called a general solution of equation (7) if f(T) = S. By a reproductive general solution or simply a reproductive solution of equation (7) is meant a general solution f such that s = f(s) for all s ∈ S.

The next lemma is in fact valid for any equation over a finite set.

Lemma 1 [4]. A function f: T → T is a general solution of equation (7) if and only if it fulfils

(i) f(T) ⊆ S, and (ii) there is a permutation β of {0, 1,…, m} such that

(10)  t_{β(k)} ∈ S ⇒ f(t_{k}) = t_{β(k)}  (k = 0, 1,…, m).

Proof. Sufficiency is obvious. Conversely, suppose f is a general solution. Define a map φ_{0}: S → T by choosing, for each element t ∈ S, an element φ_{0}(t) such that t = f(φ_{0}(t)). Then φ_{0} is obviously injective and it follows immediately that φ_{0} can be extended to a bijection φ: T → T. The defining property of φ_{0} implies that t_{h} = f(φ(t_{h})) for all t_{h} ∈ S. The latter property can be written in the form (10) for the permutation β of {0, 1,…, m} defined by β(k) = h ⇔ φ(t_{h}) = t_{k}.

Lemma 2. The implication (10) in Lemma 1 can be written in the form

(11)  f(t_{k}) = t_{β(k)}a_{β(k)}^{0} + f(t_{k})a_{β(k)}^{1}  (k = 0, 1,…, m).

Proof. It follows from (11) that

(12)  a_{β(k)} = 0 ⇒ f(t_{k}) = t_{β(k)}  (k = 0, 1,…, m);

but (12) is equivalent to (10) by (8). Conversely, suppose (10) holds. Then (11) is checked immediately by considering the cases a_{β(k)} = 1 and a_{(k)} = 0 and by using again (8).

Theorem 1. A function f: T → T is a general solution of equation (7) if and only if it is of the form

(13)  f(x) = ∑_{k=0}^{m}(t_{β(k)}a_{β(k)}^{0} + c_{k}a_{β(k)}^{1})x^{t_{k}}  (∀x ∈ T)

where β is a permutation of {0, 1,…, m} and

(14)  c_{k} ∈ S  (k = 0, 1,…, m)

Proof. Suppose (13) and (14) hold. Consider an arbitrary but fixed k ∈ {0, 1,…, m}. Taking into account Proposition 1, it follows that if a_{β(k)} = 1; then f(t_{k}) = c_{k} ∈ S, while t_{β(k)} ∈ S ⇔ a_{β(k)} = 0 ⇒ f(t_{k}) = t_{β(k)}. Therefore f is a general solution by Lemma 1. Conversely, necessity follows from Proposition 1 and Lemmas 1 and 2.

Theorem 2. A function f: T → T is a reproductive solution of equation (7) if and only if it is of the form

(15)  f(x) = ∑_{k=0}^{m}(t_{k}a_{k}^{0} + c_{k}a_{k}^{1})x^{t_{k}}  (∀x ∈ T)

where

(14)  c_{k} ∈ S  (k = 0, 1,…, m).

Proof. It follows from Theorem 1 and Proposition 1 that any function satisfying (15) and (14) is a general solution and

(16)  f(t_{k}) = t_{k}a_{k}^{0} + c_{k}a_{k}^{1}  (k = 0, 1,…, m),

therefore if t_{k} ∈ S then f(t_{k}) = t_{k} because a_{k} = 0. Conversely, suppose f is a reproductive solution of equation (7). Then f satisfies conditions (i) and (ii) in Lemma 1 with the identity in the role of β. Taking also into account Lemma 2 we see that relations (14) and (16) hold for c_{k} = f(t_{k}). The proof is completed by Proposition 1.

Acknowledgement. I thank the referee for his/her useful remarks.

Bibliography

[1] D. Banković, On general and reproductive solution of arbitrary equations, Publ. Inst. Math. Beograd 26(40) (1979), 31–33.

[2] D. Banković, Solving systems of arbitrary equations, Discrete Math. 46 (1983), 305–309.

[3] D. Banković, Some remarks on reproductive solutions, Publ. Inst. Math. Beograd 38(52) (1985), 17–19.

[4] D. Banković, All general solutions of finite equations, Publ. Inst. Math. Beograd 47(61) (1990), 5–12.

[5] D. Banković, A new proof of Prešić’s theorem on finite equations, Publ. Inst. Math. Beograd 51(65) (1992), 22–24.

[6] D. Banković, A note on finite equations, Zb. Rad. Prir.-Mat. Fak. u Kragujevcu 14 (1993), 15–18.

[7] D. Banković, All solutions of finite equations, Discrete Math. 137 (1995), 1–6.

[8] D. Banković, Finite equations in n unknowns, Publ. Inst. Math. Beograd 61(75) (1997), 1–5.

[9] D. Božić, A note on reproductive solutions, Publ. Inst. Math. Beograd 19(33) (1975), 33–35.

[10] J. Chvalinna, Characterizations of certain general and reproductive solutions of arbitrary equations, Mat. Vesnik 39 (1987), 5–12.

[11] C. Ghilezan, Méthode à résoudre des relations dont les résolutions appartiennent à un ensemble fini, Publ. Inst. Math. Beograd 10(24) (1970), 21–23.

[12] J.D. Kečkić, S.B. Prešić, Reproductivity – a general aproach to equations (1984, unpublished).

[13] L. Löwenheim, Über das Auflösungsproblem im logischen Klassenkalkul, Sitzungsber. Berl. Math. Geselschaft 7 (1908), 89–94.

[14] L. Löwenheim, Über die Auflösung von Gleichungen im logischen Gebietenkalkul, Math. Ann. 68 (1910), 169–207.

[15] S.B. Prešić, Une classe d’équations matricielles et l’équation fonctionnelle f^{2} = f, Publ. Inst. Math. Beograd 8 (22) (1968), 143–148.

[16] S.B. Prešić, Une méthode de résolution des équations dont toutes les solutions appartiennent à un ensemble fini donné, C.R. Acad. Sci. Paris 272 (1971), 654–657.

[17] S.B. Prešić, Ein Satz Über reproduktive Lösungen, Publ. Inst. Math. Beograd 14(28) (1972), 133–136.

[18] S.B. Prešić, All reproductive solutions of finite equations, Publ. Inst. Math. Beograd 44(58) (1988), 3–7.

[19] S. Rudeanu, Boolean functions and equations, North-Holland Amsterdam 1974.

[20] S. Rudeanu, On reproductive solutions of arbitrary equations, Publ. Inst. Math. Beograd 24(38) (1978), 143–145.

[21] E. Schröder, Vorlesungen Über die Algebra der Logik, Leipzig; vol. 1, 1890; vol. 2, 1891, 1905; vol. 3, 1895. Reprint 1966 (Chelsea, Bronx NY).

Facultatea de matematică (Received 05 01 1998) Universitatea Bucureşti Str. Academiei 14 70109 Bucureşti Romania