Article
Kyungpook Mathematical Journal 2020; 60(3): 423-443
Published online September 30, 2020
Copyright © Kyungpook Mathematical Journal.
Variants of Essential Arity for Partial Functions
Erkko Lehtonen*, Nareupanat Lekkoksung
Institut für Algebra, Technische Universität Dresden, 01062 Dresden, Germany
e-mail : erkko.lehtonen@tu-dresden.de
Department of Mathematics, Faculty of Science, Khon Kaen University, 40002 Khon Kaen, Thailand
e-mail : n.lekkoksung@kkumail.com
Received: November 7, 2018; Revised: April 4, 2019; Accepted: August 22, 2019
Abstract
Generalizations of essential arity of partial functions, based on essential sets of arguments, are introduced, and their interplay with the minor relation of functions is investigated.
Keywords: partial function, essential argument, essential set of arguments
1. Introduction
In many-valued logic, the theory of essential arguments of functions is a topic that has been widely studied by many authors [2, 3, 5, 6, 7, 8, 9, 10, 14, 16]. In 1963, Salomaa [14] considered how the number of essential arguments of a Boolean function is affected by identification of arguments. It turned out that the so-called arity gap (i.e., the minimum decrease in the number of essential arguments when a pair of essential arguments is identified) of any Boolean function is at most 2. Willard [17] generalized this result in 1996. He considered the same problem for a function
A function
The number of essential arguments (essential arity) can be seen as a kind of measure of the structural complexity of a function. It is compatible with the minor quasiorder; the number of essential arguments of a total function does not increase upon formation of minors. Moreover, the essentially at most unary functions are minimal members of the minor quasiorder, and a total function is constant if and only if it has no essential arguments. This is no longer true for partial functions. As we will see in Section 2, in contrast to total functions, the number of essential arguments of a partial function may increase upon formation of minors, and it is possible that a nonconstant partial function has no essential argument. From this standpoint, essential arity seems slightly unsatisfactory as a measure of structural complexity for partial functions. We would like to modify this notion to be better suitable for partial functions.
In this paper, we introduce five notions that attempt to generalize essential arguments and essential arity to partial functions: essential argument, essential set of arguments, minimal essential set, width of the poset of essential sets, exact essential set. Each one of these notions gives rise to a quantity analogous to essential arity, and we will assess each with regard to the following properties, which are useful and desirable for a “successful” substitute of essential arity for partial functions:
-
(1) isotonicity with respect to the minor order,
-
(2) equality to 0 precisely for constant functions,
-
(3) coincidence with essential arity for total functions.
Introduced in Section 3, the first generalization of the notion of essential argument is that of essential set of arguments. The set of all essential sets of arguments of a function, ordered by inclusion, forms a poset, and we take the minimal essential sets as the second generalization of essential arguments. The next generalization is the width of the poset of essential sets, which is considered in Section 4. We will see that the associated quantities (essential arity, the number of essential sets, the number of minimal essential sets, the width of the poset of essential sets) may increase upon formation of minors, and hence do not have the desired property (1).
As a last variant of essential argument, we define the notion of exact essential set in Section 5. The logarithm of the number of exact essential sets of a partial function is called exact essential hyperarity. We will see that the exact essential hyperarity of a partial function does not increase when we form minors, and it equals 0 precisely for constant functions. Although this notion does not coincide with essential arity for total functions, it seems a suitable measure of the structural complexity for partial functions. We continue in Section 6 with a modification of the arity gap in which we consider the minimum decrease in the exact essential hyperarity of a partial function upon formation of minors. We will see that an analogue of Willard’s theorem does not hold for the exact hyperarity gap of partial functions. We summarize our findings in the final Section 7.
2. Minors and Essential Arguments of Partial Functions
We denote the set of natural numbers by ℕ := {0, 1, 2, …} and the set of positive integers by ℕ+ := {1, 2, …}. For . We denote constant tuples (0, … , 0) and (1, … , 1) in
by
For arbitrary sets
We can view any tuple
Let
It is not difficult to see that the minor relation ≤ is a quasiorder (a reflexive and transitive relation) on ℘
Let
The number of essential arguments in
The above definition of essential arguments is a natural and straightforward generalization of the usual definition of essential arguments of a total function (see [17]). For total functions, the essential arity behaves nicely with respect to minors, as described in the following lemma.
Lemma 2.1.([12, Lemma 2.2.4])
-
(i) Ess
f ⊆ Imσ. -
(ii)
For every i ∈ Essf, we have that σ −1(i ) ∩ Essg ≠ ∅︀. -
(iii) ess
f ≤ essg.
As shown by the following example, conditions (ii) and (iii) do not hold in general for partial functions. Nevertheless, implication (ii) ⇒ (iii) holds also for partial functions.
Example 2.2
Let
Define and
by
We see that
Lemma 2.3.([12, Lemma 2.2.4(vi)])
Fact 2.4
-
(i) ess
f = 0if and only if f is constant. -
(ii)
f <g implies essf < essg.
We note that Fact 2.4(ii) follows from Lemma 2.1(iii) and Lemma 2.3. These facts do not hold for partial functions. Before giving a counterexample below, in Example 2.5, we introduce some notation.
Let
for every
Example 2.5
Let of arity
by
for all of arity 2
by
for all
Let
is called an
for all
The identification minors
Lemma 2.6
Let
and
Since
Proposition 2.7
By Lemma 2.6, we have
Note that Example 2.2 shows that the inequality in Proposition 2.7 can hold as an equality.
Let
-
(i)
c 0 :=a σ , -
(ii) for each
j = 1, … ,r , letc j be the tuple obtained fromc j −1 by changing thel j -th entry froma i tob i .
Lemma 2.8
Let
That is, there exists
The following example shows that the converse of Lemma 2.8 does not hold.
Example 2.9
Let
and
Define and
by
Then
Corollary 2.10
Apply Lemma 2.1 and Lemma 2.8.
3. Essential Sets of Arguments
Essential arguments do not seem to adequately describe the behaviour of partial functions. A partial function might be very complex yet it depends on very few arguments. In particular, in stark contrast to total functions, the essential arity of partial functions can increase when minors are formed and a non-constant function might be essentially nullary (see Fact 2.4 and Examples 2.2 and 2.5).
In this section, we define an alternative notion of “essentiality” that would better express the idea of dependence of a (partial) function on several arguments collectively, not just on a single argument.
Definition 3.1
Let
The pair (
A set
These notions seem reasonable because for total functions they coincide with the classical notion of essential arguments. More generally, for a partial function
-
(1) argument
i is essential inf . -
(2) {
i } is an essential set inf . -
(3) {
i } is a minimal essential set inf .
Example 3.2
Let by
Then {3}, {1, 2}, {1, 3}, {2, 3} and {1, 2, 3} are essential sets in
Recall from Lemma 2.1 that for total functions
Example 3.3
Let
and
Define and
by
Then
Now, we see that MES(
Lemma 3.4
Let
Since
We conclude that the pair (
We observe that the converse of Lemma 3.4 does not hold as shown by Example 3.3. In fact, if we let
Example 3.5
Let
and
Define and
by
Then
The above examples show that the number of minimal essential sets may increase or decrease upon formation of minors. It is not clear to us under which conditions this quantity is nonincreasing.
Provide necessary and sufficient conditions for functions
As a partial answer to the above problem, the following theorem provides a sufficient condition.
Theorem 3.6
The map
Next, we introduce a particular kind of minor that forces the hypothesis of Theorem 3.6. Let
Example 3.7
Let
Define and
by
Then
Example 3.8
Let
and
Define and
by
Then
Lemma 3.9
Since
Since
Therefore, (
Proposition 3.10
Let
Proposition 3.11
Since
Thus, the hypothesis of Theorem 3.6 holds whenever
Theorem 3.12
It suffices to show that the map
The map
4. The Width of the Poset of Essential Sets
In this section, we will consider our next variant of essential arity: the width of the poset of essential sets. Recall that a poset (
Let
Example 4.1
Let
and
Define and
by
Then
We will still provide a sufficient condition for functions
-
(1)
f is a minor ofg via surjectiveσ , -
(2)
f is a surjective minor ofg viaσ .
(All combinations are possible: surjective minor via surjective
Lemma 4.2
.
First, we observe that by Lemma 3.4. Let
. Then
. Suppose that
is an antichain in (ES(
is an antichain in (ES(
by
. Thus,
.
Corollary 4.3
Let be a largest antichain in (ES(
is an antichain in (ES(
.
Theorem 4.4
Let be the largest antichain in (ES(
in ES(
where ℒ is a largest antichain in (ES(
where
is the largest antichain in (ES(
5. Exact Essential Sets
We have seen in Sections 2, 3 and 4 that the number of essential arguments, the number of essential sets, the number of minimal essential sets, and the width of the poset of essential sets are perhaps not the most suitable notions for describing the structural complexity of partial functions, because they are neither monotone increasing nor decreasing with respect to the minor order. In this section we will introduce a variant of essential arity which is somewhat better in that it does not increase upon formation of minors.
Definition 5.1
Let
Example 5.2
Consider the following partial function
We see that ES(
The following proposition provides a possibly clearer, equivalent condition describing exact witnesses of essentiality.
Proposition 5.3
-
(i) (
a ,b )is not a witness of essentiality of S \ {k }in f for any k ∈S , -
(ii)
for all i ∈ [n ],a i =b i if and only if i ∉S.
(i) ⇒ (ii): Let
(ii) ⇒ (i): Suppose, to the contrary, that there exists
Let
by
Let
-
(i)
a (i ←b ) ∉X for allb ∈A , -
(ii)
a (i ←b ) ∈X for allb ∈A andf (a (i ←b )) =f (a (i ←c )) for allb ,c ∈A .
Denote the set of all fictitious arguments of
Remark 5.4
In a total function, an argument is fictitious if and only if it is not essential. For partial functions this equivalence does not hold in general; an argument may be essential, fictitious, or neither of the two, but not both essential and fictitious.
Let
Example 5.5
Consider the following partial function
We see that the 3rd argument is fictitious in
Definition 5.6
Let
Remark 5.7
We observe that XES(
We note that if
Since the number of essential sets of an
Definition 5.8
The
Example 5.9
Consider the partial function
In general, if
Example 5.10
Consider the following partial functions.
Then
Theorem 5.11
Assume that
It remains to show that (
Corollary 5.12
Remark 5.13
Let
-
(i)
i ∈ Essf if and only if {i } ∈ XES(f ). -
(ii) ess
f ≤ xesf . -
(iii)
f is constant if and only if xesf = 1, or, equivalently, ßf = 0.
-
(iv) xes
f ≤ |ES(f )|. -
(v) mes(
f ) ≤ xesf .
We observe that if
Lemma 5.14
By Theorem 5.11, it is clear that
As a consequence, an analogue of Lemma 2.3 is true for the exact essential hyperarity of total functions.
Proposition 5.15
By Corollary 5.12,
which yields the desired contradiction, and we conclude that
The following example shows that Proposition 5.15 does not hold for partial functions in general.
Example 5.16
Consider the following partial functions.
Then
6. Exact Hyperarity Gap
As pointed out in Fact 2.4(ii), the essential arity of a total function decreases upon formation of minors. One may ask how large this decrease of essential arity must be for a given function. In this way one arrives at the notion of the arity gap of a function. This question was first considered by Salomaa [14].
Let
The arity gap of a total function is clearly at least 1. Salomaa showed that the arity gap can be as large as |
Later, Willard [17] extended this result to functions on arbitrary finite domains. He showed that the arity gap of any function
Partial functions may have a negative arity gap. By Proposition 2.7,
See Example 2.2 for an example of a function
The notion of exact essential hyperarity suggests an analogue of arity gap. Let
Obviously, for any partial function
By Example 5.16, we see that the exact hyperarity gap of a partial function can be as small as 0. The following example shows that the exact hyperarity gap can be as large as the arity
Example 6.1
Let
and
Define a partial function where
Example 6.2
Let by
Then xes
Definition 6.3. ([1])
Let oddsupp: ∪
A function
Example 6.4
Suppose that {0, 1, 2} ⊆ . Define a function
Let
-
If |
S | is odd, then the pair (0 ,a ) is an exact witness of essentiality ofS inf , where0 = (0, … , 0) ∈A n anda ∈A n is defined by -
If |
S | is even, thenS is a disjoint union of odd subsetsS 1 andS 2 ofS , and the pair (0 ,b ) is an exact witness of essentiality ofS inf , where0 = (0, … , 0) ∈A n andb ∈A n is defined by
We conclude that every subset of [
Willard’s upper bound for the arity gap can be stated as follows.
Theorem 6.5.([17, Lemma 1.2, Corollary 2.3])
The analogue of the above for the exact hyperarity gap of partial functions does not hold. The condition ess
Example 6.6
Let . Let
Let
Then
Provide a (sharp and nontrivial) upper bound for the exact hyperarity gap of
7. Concluding Remarks
We have defined some variants of essential arity for partial functions: the number of essential sets, the number of minimal essential sets, the width of the poset of essential sets, and the exact essential hyperarity. For these measures of structural complexity of a function, the following attributes are desirable:
-
(1) isotonicity with respect to the minor order,
-
(2) equality to 0 precisely for constant functions,
-
(3) coincidence with essential arity for total functions.
Our investigations show that only the exact essential hyperarity is isotone with respect to the minor order and that all measures but the essential arity are equal to 0 precisely for constant functions. The number of minimal essential sets coincides with essential arity for total functions; the other measures do not. This is summarized in Table 1.
Footnote
The second author was supported by the Development and Promotion of Science and Technology Talents Project (DPST), Thailand.
References
- J. Berman, and A. Kisielewicz.
On the number of operations in a clone . Proc Amer Math Soc.,122 (1994), 359-369. - Y. Breitbart.
Essential variables of functions of the algebra of logic . Russian, Dokl Akad Nauk USSR.,172 (1967), 9-10. - KN. Čimev.
Separable sets of arguments of functions . Studies 180/1986,, Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, 1986. - M. Couceiro, and S. Foldes.
On closed sets of relational constraints and classes of functions closed under variable substitutions . Algebra Universalis.,54 (2005), 149-165. - M. Couceiro, and E. Lehtonen.
On the effect of variable identification on the essential arity of functions on finite sets . Internat J Found Comput Sci.,18 (2007), 975-986. - M. Couceiro, and E. Lehtonen.
Generalizations of Świerczkowski’s lemma and the arity gap of finite functions . Discrete Math.,309 (2009), 5905-5912. - M. Couceiro, and E. Lehtonen.
On the arity gap of finite functions: results and applications . J Mult-Valued Logic Soft Comput.,27 (2016), 193-207. - RO. Davies.
Two theorems on essential variables . J London Math Soc.,41 (1966), 333-335. - K. Denecke, and J. Koppitz.
Essential variables in hypersubstitutions . Algebra Universalis.,46 (2001), 443-454. - A. Ehrenfeucht, J. Kahn, R. Maddux, and J. Mycielski.
On the dependence of functions on their variables . J Combin Theory Ser A.,33 (1982), 106-108. - O. Ekin, S. Foldes, PL. Hammer, and L. Hellerstein.
Equational characterizations of Boolean function classes . Discrete Math.,211 (2000), 27-51. - E. Lehtonen, . Reconstruction of functions from minors. Habilitation thesis 2018 Technische Universität Dresden. Dresden http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-237864.
- N. Pippenger.
Galois theory for minors of finite functions . DiscreteMath.,254 (2002), 405-419. - A. Salomaa.
On essential variables of functions, especially in the algebra of logic . Ann Acad Sci Fenn Ser A I Math.,339 (1963), 11 pp. - BSW. Schröder. Ordered sets: An introduction,
, Birkhäuser, Basel, 2003. - S. Shtrakov.
Essential arity gap of Boolean functions . Serdica J Comput.,2 (2008), 249-266. - R. Willard.
Essential arities of term operations in finite algebras . Discrete Math.,149 (1996), 239-259. - RO. Winder.
Fundamentals of threshold logic . Applied Automata Theory,, Academic Press, New York, 1968:235-318.