PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 67(81) (2000), 76–84

A GENERALIZATION OF THE NOTION OF REPRODUCTIVITY

Slaviša B. Prešić

Communicated by Žarko Mijajlović

Abstract. In Section 1 we state the known theory of reproductive equations in general. The key result is that every equation, having at least one solution, is equivalent to some reproductive equation. In Section 2 we extend the notion of reproductive equations to the class of equations Eq(x) which are solved by means of some given equation, denoted by Eq_{1}(ϱ). In that case we also prove that such an Eq(x), having at least one solution, is equivalent to some reproductive equation.

1. Reproductivity of an equation x = f(x)

Let A be a set (or a class) and Eq(x) an equation in x ∈ A. Eq can be understood as a unary relation over A. Let S be the set (class) of all solutions of Eq(x). Then we have:

(1)  (∀x ∈ A)(Eq(x) ⇔ x ∈ S)

Let us assume that P is another set (class) and ϕ : P → S a surjection. Using such P and a function ϕ formula (1) can be reformulated thus

(2)  (∀x ∈ A)(Eq(x) ⇔ (∃p ∈ P) x = ϕ(p))

In this case the formula x = ϕ(p), where p is any element of P, gives all the solutions of Eq(x), and accordingly we have the following definition:

Definition 1. If (2) holds, then the formula

x = ϕ(p), p is any element of P

is called a formula of the general solution of the equation Eq(x).

1991 Mathematics Subject Classification. 39B52.

Let us concentrate on the ⇒-part of the formula (2), i.e., (∀x ∈ A)(Eq(x) ⇒ (∃p ∈ P)x = ϕ(p)) which is equivalent to (∀x ∈ A)(∃p ∈ P)(Eq(x) ⇒ x = ϕ(p)), since p does not appear in the first part of the implication, i.e., in Eq(x). Using the axiom of choice, we can introduce a new function ψ : A → P such that:

(3)  (∀x ∈ A)(Eq(x) ⇒ x = ϕ(ψ(x)))

Let f : A → A be defined by f(x) = ϕ(ψ(x)). Then (3) transforms into:

(4)  (∀x ∈ A)(Eq(x) ⇒ x = f(x))

It is easy to see that (∀x ∈ A)(Eq(x) ⇔ (∃p ∈ P) x = f(p)) is also true. So, the formula:

(5)  x = f(p), p ∈ A

is the formula of the general solution of Eq(x). But, since (4) is true, we say that (5) is a formula of the general reproductive solution. The notion of a reproductive solution appeared in 1919 in Löwenheim paper on Boolean equations [1]. In Prešić [1] we gave the following definition of a reproductive equation.

Definition 2. Equation x = f(x) in x ∈ A is reproductive iff the equality (∀x ∈ A) f(f(x)) = f(x) holds.

It is easy to see that:

Lemma 1. If x = f(x) is a reproductive equation, then all of its solutions are given by the formula (5).

Example 1. Consider the system of equations

(∗1)  x = x ∪ y, y = x ∩ y

in x, y ∈ B, where B is a Boolean algebra. Let f : B^{2} → B^{2} be defined by:

If X = (x, y), then f(X) = (x ∪ y, x ∩ y)

Then (∗1) transforms into X = f(X), (X ∈ B^{2}), which is easily seen to be reproductive.

Example 2. Consider the functional equation

(∗2)  ϕ(x, y) = ϕ(y, x)

in ϕ : R^{2} → R. Let Func be the set of all functions ϕ : R^{2} → R and f : Func → Func be defined by:

If X is ϕ then f(X) is the function \binom{(x, y)}{\frac{ϕ(x,y)+ϕ(y,x)}{2}}

Equation (∗2) becomes X = f(X), which is easily seen to be reproductive. Indeed, let X = ϕ; then f(X) = ψ, where ψ(x, y) = (ϕ(x, y) + ϕ(y, x))/2. Moreover,

f(f(X)) = f(ψ) = \binom{(x, y)}{\frac{ψ(x,y)+ψ(y,x)}{2}} = \binom{(x, y)}{\frac{ϕ(x,y)+ϕ(y,x)+ϕ(x,y)+ϕ(y,x)}{4}}

= \binom{(x, y)}{\frac{ϕ(x,y)+ϕ(y,x)}{2}} = \binom{(x, y)}{ψ(x, y)} = ψ,

so f^{2} = f.

The next important fact (see Prešić [1]) is the following theorem:

Theorem 1. If Eq(x) has at least one solution in x ∈ A, then it has an equivalent reproductive equation.

Proof. Let S ⊆ A be the set (class) of all the solutions for Eq(x). It is sufficient to define f : A → A thus:

If X ∈ S, then f(X) = X; if X ∈ A ∖ S, then f(X) is any element in S

It is easy to see that the equality X = f(X) is reproductive and equivalent to Eq(x).

We would like to point out that Theorem 1 was often a leading idea used in solving many classes of equations (functional, Boolean, on finite sets, etc.). We mention one such result concerning the so called linear homogeneous functional equations on groups (see Prešić [2], [3]):

a_{1}(x)ϕ(θ_{1}(x)) + ⋯ + a_{n}(x)ϕ(θ_{n}(x)) = 0

where x ∈ S (S given set); θ_{i} : S → S forms a group of order n, and a_{i} are given mappings from S into a given field F. The function ϕ : S → F is unknown.

For this equation, an equivalent reproductive equation is effectively described (see also Kuczma [1, p. 268]).

2. Reproductivity of an equation Eq(x) given by a formula of the form (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ))

In mathematics there are many cases when a given equation Eq(x) is solved up to some other equation, say Eq_{1}(ϱ). In other words, Eq(x) is solved by means of the equation Eq_{1}(ϱ).

Example 3. Equation (x − 1)^{2} = 7 in x real can be solved by means of the following equation Eq_{1}(ϱ) : ϱ^{2} = 7. Namely, we have the equivalence

(x − 1)^{2} = 7 ⇔ (∃ϱ ∈ R)(Eq_{1}(ϱ), x = 1 + ϱ)

Similarly, equation (x − y)^{2} = 7 in x, y ∈ R can be solved using the same equation Eq_{1}(ϱ). We have:

(x − y)^{2} = 7 ⇔ (∃p ∈ R)(∃ϱ ∈ R)(Eq_{1}(ϱ), y = p, x = p + ϱ)

There is a ‘parameter’ p in the previous formula and a quantifier (∃p ∈ R), since equation x − y = ϱ does not have a unique solution in x, y.

Bearing in mind this simple example we shall in general define the meaning of these sentences:

x is an Eq_{1}(ϱ)-solution of the equation Eq(x). Equation Eq(x) is solved by means of the equation Eq_{1}(ϱ).

Assume that B is some other set (class) with a unary relation Eq_{1}. Further, let P be another set (class).

Definition 3. (i) Let x ∈ A be determined by an equality of the form x = μ(ϱ), where μ : B ⟶ A is a certain function. We say that x is an Eq_{1}(ϱ)-solution of the equation Eq(x) iff the following implication is true

(x = μ(ϱ), Eq_{1}(ϱ)) ⇒ Eq(x)

(ii) Equation Eq(x) in x ∈ A is solved by means of the equation Eq_{1}(ϱ) iff the following equivalence is true^{1}

(6)  Eq(x) ⇔ (∃p ∈ P)(∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(p, ϱ))

where ϕ : P × B → A is a given function.

We can see how natural is the previous definition if we consider the following fact:

If (6) is true, then all the Eq_{1}(ϱ)-solutions of Eq(x) are determined by x = ϕ(p, ϱ), where p ∈ P is an arbitrary element and ϱ ∈ B is any solution of Eq_{1}(ϱ). According to this we introduce the following definition.

Definition 4. If the equivalence (6) holds, then the formula x = ϕ(p, ϱ), where p ∈ P is an arbitrary element and ϱ ∈ B is any solution of the equation Eq_{1}(ϱ), is called a formula of the general solution of the equation Eq(x) by means of the equation Eq_{1}(ϱ).

Notice that if Eq(x) has a unique solution, then P is superfluous and (6) becomes

Eq(x) ⇔ (∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(ϱ))

where ϕ : B → A is some function.

Concerning Definition 3 more examples follow. First, we notice that Example 3 can be extended to the case in Galois theory when one considers the question whether a given algebraic equation is solvable by radicals.

1We can put (∀x ∈ A) before the formula (6)

Example 4. In the class of all groupoids take equation gr(X) with the meaning: X is a group. We do not know a general solution to gr(X). But various representation theorems solve this equation up to some simpler equation. One such theorem, the so called Cayley representation theorem, can be stated thus:

gr(X) ⇔ (∃G)(G is a permutation group, X ≅ G)

assuming that in some sense ≅ (isomorphism) is an equality of algebras.

Similarly, the same is true for various representation theorems in many fields of mathematics.

Example 5. Consider the Pexider functional equation (for more on Pexider equation see Krapež and Taylor [1])

(7)  f(x + y) = g(x) + h(y)

where f, g, h : R → R are unknown functions. As is well known this equation reduces to the Cauchy equation ϕ(x + y) = ϕ(x) + ϕ(y). Indeed, from (7) we get:

(∗1)  g(x) = f(x) − h(0), h(x) = f(x) − g(0)

Equation (7) then becomes f(x + y) = f(x) − h(0) + f(y) − g(0), i.e.

(∗2)  f(x + y) − g(0) − h(0) = (f(x) − g(0) − h(0)) + (f(y) − g(0) − h(0))

Defining function ϕ by ϕ(x) = f(x) − g(0) − h(0) equation (∗2) transforms into the Cauchy functional equation. If we introduce two constants by C_{1} = g(0), C_{2} = h(0) then we have the following assertion.

(∗3) Any solution (f, g, h) of (7) satisfies the condition:

f(x) = ϕ(x) + C_{1} + C_{2}, g(x) = ϕ(x) + C_{1}, h(x) = ϕ(x) + C_{2}

where C_{1}, C_{2} are some constants and ϕ is a solution to the Cauchy functional equation.

This can be written down as (∗4) (∀x, y ∈ R)f(x + y) = g(x) + h(y) ⇒

(∃C_{1}, C_{2})(∃ϕ)(∀x, y ∈ R)[ϕ(x + y) = ϕ(x) + ϕ(y), f(x) = ϕ(x) + C_{1} + C_{2},

g(x) = ϕ(x) + C_{1}, h(x) = ϕ(x) + C_{2}]

As is usual when we prove some implication like (∗4), then we check whether the functions in the consequence part of the formula do make a solution. In this example this means whether the following equivalence is true:

(8) f(x + y) = g(x) + h(y) ⇔

(∃C_{1}, C_{2})(∃ϕ)[ϕ(x + y) = ϕ(x) + ϕ(y), f(x) = ϕ(x) + C_{1} + C_{2},

g(x) = ϕ(x) + C_{1}, h(x) = ϕ(x) + C_{2}]

It can be easily checked that equivalence (8) is indeed true.

Next, we prove that this equivalence is of the form (6). First, equation f(x+y) = g(x) + h(y) is Eq(X) in X ∈ A where A is the set of all triples (f, g, h) of real functions R → R. Further, let B be a set of all real functions and Eq_{1}(ϱ) be the Cauchy equation^{2} (∀x, y ∈ R)ϕ(x + y) = ϕ(x) + ϕ(y). Let P be R^{2} and Φ : P × B → A be defined in the following way:

2ϕ stands instead of ϱ

If p, denoted by (C_{1}, C_{2}), is any element of P and ϕ ∈ B, then Φ(p, ϕ) is the triple (f, g, h) where f(x) = ϕ(x) + C_{1} + C_{2}, g(x) = ϕ(x) + C_{1}, h(x) = ϕ(x) + C_{2}

Using this notation (8) becomes

Eq(X) ⇔ (∃p)(∃ϕ)(Eq_{1}(ϕ), X = Φ(p, ϕ))

which is of the form (6). Therefore (f, g, h) as given above is a solution of the Pexider equation by means of the equation Eq_{1}(ϱ), i.e., the Cauchy equation.

Let us return to the general case i.e., to the equation Eq(x) for which is supposed that (6) is true, i.e.:

(9)  (∀x ∈ A)(Eq(x) ⇔ (∃p ∈ P)(∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(p, ϱ)))

The ⇒-part of (9) is equivalent to

(∀x ∈ A)(∃p ∈ P)(Eq(x) ⇒ (∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(p, ϱ)))

Using the axiom of choice we can define a mapping ψ : A → P such that

(∗5)  (∀x ∈ A)(Eq(x) ⇒ (∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(ψ(x), ϱ)))

A new function f : A × B → A is defined by: f(x, ϱ) = ϕ(ψ(x), ϱ). Then (∗5) transforms into:

(∗6)  (∀x ∈ A)(Eq(x) ⇒ (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ)))

On the other hand, concerning ⇐-part of (9) we have the following implication chain

(∀x ∈ A)((∃p ∈ P)(∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(p, ϱ)) ⇒ Eq(x))
⇒ (∀x ∈ A)(∀p ∈ P)((∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(p, ϱ)) ⇒ Eq(x))

The variable p is not free in Eq(x) (using a logical law for the quantifier (∃p ∈ P)).

⇒ (∀x ∈ A)((∃ϱ ∈ B)(Eq_{1}(ϱ), x = ϕ(ψ(x), ϱ)) ⇒ Eq(x)).

“Replacing p by ψ(x)” (using a logical law for the quantifier (∀p ∈ P)). Thus we have the following implication

(∀x ∈ A)((∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ)) ⇒ Eq(x)).

Combining this implication and (∗6) we obtain the following equivalence

(∀x ∈ A)(Eq(x) ⇔ (∃p ∈ P)(∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(p, ϱ)))

which states that the formula:

x = f(p, ϱ), p ∈ A, ϱ ∈ B {while ϱ is a solution of Eq_{1}(ϱ)}

gives all the solutions of Eq(x) by means of the solutions of the equation Eq_{1}(ϱ). Furthermore, since (∗6) is true, we can say that this formula is reproductive.

Now we concentrate on the formula

(10)  (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ))

the right-hand part of the implication (∗6), which is understood as an equation in x ∈ A. In the sequel, whenever we give an x-solution, for instance x_{0}, we shall also specify a value ϱ_{0}, as a corresponding ‘witness’ for the quantifier (∃ϱ ∈ B). That means that the pair < x_{0}, ϱ_{0} > shall satisfy the conditions Eq_{1}(ϱ_{0}), x_{0} = f(x_{0}, ϱ_{0}). Now we define when formula (10) is reproductive:

Definition 5. The formula (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ)) is reproductive iff the following condition

(∀x ∈ A)(∀ϱ ∈ B)(Eq_{1}(ϱ) ⇒ f(x, ϱ) = f(f(x, ϱ), ϱ)))

holds.

The reason for this definition is that like Lemma 1 we have the following fact:

Lemma 2. If the formula (10) is reproductive, then all of its solutions by means of the equation Eq_{1}(ϱ) are given by the following formula

(11)  x = f(p, ϱ)

p ∈ A, ϱ ∈ B are any elements provided Eq_{1}(ϱ)

Indeed, if p_{0} ∈ A, and ϱ_{0} ∈ B with property Eq_{1}(ϱ_{0}) are any elements, then x defined by x = f(p_{0}, ϱ_{0}) satisfies the formula (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ)), since we can take ϱ_{0} as a witness for quantifier (∃ϱ ∈ B) and the equality x = f(x, ϱ) reduces to the true equality f(x_{0}, ϱ_{0}) = f(f(x_{0}, ϱ_{0}), ϱ_{0}). Conversely, if x_{1} is a solution of (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ)), then a certain ϱ_{1} is a witness for (∃ϱ ∈ B), consequently the equality x_{1} = f(x_{1}, ϱ_{1}) holds. This equality is an instance of (11) when p = x_{1}, ϱ = ϱ_{1}.

It is important that we have a theorem similar to Theorem 1:

Theorem 2. Let Eq(x) be an equation in x ∈ A whish is solvable by means of^{3} Eq_{1}(ϱ), and which has at least one Eq_{1}(ϱ)-solution. Then there is a formula

(∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ))) (f : A × B → A is some function)

3i.e., the equivalence of type (6) is valid

which is equivalent to Eq(x) and reproductive in the sense of Definition 5.

Proof. Denote by S the set of all the Eq_{1}(ϱ)-solutions of Eq(x). We define the function f as follows: If x ∈ S, then for all ϱ ∈ B such that Eq_{1}(ϱ), we define f(x, ϱ) = x; for other ϱ′s f(x, ϱ) is arbitrary. If x ∉ S, then for all ϱ ∈ B such that Eq_{1}(ϱ), we define f(x, ϱ) as some x′ ∈ S; for the remaining ϱ′s f(x, ϱ) is arbitrary.

First, we prove the equivalence:

Eq(x) ⇔ (∃ϱ ∈ B)(Eq_{1}(ϱ), x = f(x, ϱ))

The ⇒-part. Let Eq(x_{0}), i.e. x_{0} ∈ S and ϱ_{0} some element in B such that Eq_{1}(ϱ_{0}). Further, by the definition of f, the value of f(x_{0}, ϱ_{0}) is x_{0}. So: Eq_{1}(ϱ_{0}), x_{0} = f(x_{0}, ϱ_{0}), which yields (∃ϱ ∈ B)(Eq_{1}(ϱ), x_{0} = f(x_{0}, ϱ)).

The ⇐-part. Let for some ϱ_{0} and x_{0} be Eq_{1}(ϱ_{0}), x_{0} = f(x_{0}, ϱ_{0}). According to the definition of f we conclude that x_{0} ∈ S, i.e. Eq(x_{0}).

Second, we prove that f satisfies

(∗7)  f(f(x, ϱ), ϱ) = f(x, ϱ) whenever Eq_{1}(ϱ)

for all x ∈ A, ϱ ∈ B. Indeed, let Eq_{1}(ϱ). Then: 1^{∘} If x ∈ S, then f(x, ϱ) = x and (∗7) follows. 2^{∘} If x ∉ S, then f(x, ϱ) = x′, where x′ ∈ S so:

(i) f(f(x, ϱ), ϱ) = f(x′, ϱ) = x′ (since x′ ∈ S); (ii) f(x, ϱ) = x′

From (i) and (ii) (∗7) follows.

Now, we can use Definition 5 and Theorem 2 to guide us in solving a given equation Eq(x) by means of another given equation Eq_{1}(ϱ). Briefly, we follow the following plan. We attempt to find a formula For with these properties:

For is a logical consequence of Eq(x)

For is equivalent to Eq(x)

For is reproductive in the sense of Definition 5. However, comparing this idea with the idea from Example 5 used in solving

Pexider equation, it might seem that it is rather artificial. Returning to Pexider equation we disprove this view.

The main step was the conclusion (∗3), stated as the implication (∗4). But was it necessary to introduce constants C_{1}, C_{2}, which are just denotations for g(0), h(0) respectively? We might say that this introduction was merely for psychological reasons—therefore unnecessary. Without C_{1}, C_{2} formula (∗4) would read:

(∀x, y ∈ R)f(x + y) = g(x) + h(y)

⇒ (∃ϕ)(∀x, y ∈ R)[ϕ(x + y) = ϕ(x) + ϕ(y), f(x) = ϕ(x) + g(0) + h(0)

g(x) = ϕ(x) + g(0), h(x) = ϕ(x) + h(0)]

Denote this implication by P ⇒ Q temporarily. The converse of this implication is also true and moreover the part Q is easily seen to be reproductive. Therefore, all the solutions (f, g, h) are given by:

f(x) = ϕ(x) + G(0) + H(0), g(x) = ϕ(x) + G(0), h(x) = ϕ(x) + H(0)

where ϕ is any solution of the Cauchy functional equation and G, H arbitrary functions. Therefore, whether we prefer C_{1}, C_{2} to G(0), H(0) is just a matter of taste.

I wish to express my thanks to S. Rudeanu who read this paper and made many helpful suggestions.

References

[1] L. Löwenheim, Über die Auflösungen von Gleichungen in logishen Gebietskalkul, Math. Ann. 68 (1919), 169–207.

[1] 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.

[2] S.B. Prešić, Méthode de résolution d’une classe d’équations fonctionnelles linéaires, Univ. Beograd, Publ. Elek. Fak. Ser. Mat. Fiz. 119 (1963).

[3] S.B. Prešić, Méthode de résolution d’une classe d’équations fonctionnelles linéaires, C.R. Acad. Sci. Paris 257 (1963), 2224–2226.

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

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

[2] D. Banković, The general reproductive solution of Boolean equation, Publ. Inst. Math. (Beograd) 34(48) (1983), 7–11.

[3] D. Banković, All general reproductive solutions of Boolean equations, Publ. Inst. Math. (Beograd) 46(60) (1989), 13–19.

[1] J. Kečkić, Reproductivity of some equations of analysis, Publ. Inst. Math. (Beograd) 31(45) (1982), 73–81.

[2] J. Kečkić, Reproductivity of some equations of analysis I, II, Publ. Inst. Math. (Beograd) 31(45) (1982), 73–81; 33(47) (1983), 109–118;

[3] J. Kečkić, On reproductive solutions of differential equations, Facta Univ. Ser. Math. Inform. 8 (1993), 45–53.

[1] A. Krapež, M.A. Taylor, On the Pexider equation, Aequationes Math. 28 (1985), 170–189 [1] M. Kuczma, Functional Equations in a Single Variable, Monografie Mat. 46, Polska akad.

nauk, Warszawa, 1968.

[1] F.M. Brown, S. Rudeanu, Triangular reproductive solutions of Boolean equations, An. Univ. Craiova. Mat. Fiz. Chim. 13 (1985), 18–23

[1] S. Rudeanu, On reproductive solutions of Boolean equations, Publ. Inst. Math. (Beograd) 10(24) (1970), 71–78

Matematički fakultet (Received 14 09 1998) Studentski trg 16 (Revised 10 01 1999) 11001 Beograd, p.p. 550 Yugoslavia