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 f : Aⁿ → B defined on arbitrary finite sets A and B. He found that if n > |A|, then the arity gap of f is at most 2.

A function f is a minor of a function g if f can be obtained from g by the operations of identification of arguments, permutation of arguments, introduction of inessential arguments, and deletion of inessential arguments. Minors of functions have been extensively investigated in the past decades [4, 5, 6, 7, 11, 12, 13]. This concept has also been used as a tool to study threshold functions [18]. It appears in many papers under different names, for example, “identification minor” in [11], “ℐ-minor”, where ℐ is the set containing just the identity function, in [13], “function obtained by simple variable substitution” in [4] and “simple minor” in [6].

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.

We denote the set of natural numbers by ℕ := {0, 1, 2, …} and the set of positive integers by ℕ₊ := {1, 2, …}. For n ∈ ℕ, the set {1, … , n} is denoted by [n] (note that [0] = ∅︀). Let A be a nonempty set and n a positive integer. The usual notation for a tuple in Aⁿ is (a₁, … , a_n) where a_i ∈ A for all 1 ≤ i ≤ n. We will use bold letters to denote tuples and corresponding italic letters with subscript to denote their components, that is, a = (a₁, … , a_n). We denote the set {0, 1} by . We denote constant tuples (0, … , 0) and (1, … , 1) in by 0 and 1, respectively.

For arbitrary sets A and B, a partial function (of several arguments) from A to B is a function f : X → B where X ⊆ Aⁿ, n ∈ ℕ₊. The number n is called the arity of f. The set X is called the domain of f. If A = B, then f is called a partial operation on A. Furthermore, if X = Aⁿ, then f is said to be an n-ary (total ) function from A to B. We denote the set of all partial functions from A to B by ℘_AB and the set of all total functions from A to B by ℱ_AB.

We can view any tuple a ∈ A^m as a mapping a: [m] → A; hence, a(i) = a_i for all i ∈ [m]. Then we can compose tuples with other maps. If σ: [n] → [m] is a map, then the composite a ◦ σ: [n] → A is a tuple in Aⁿ. For simplicity, we write aσ instead of a ◦ σ. Any map σ: [n] → [m] gives rise to a map σ : A^m → Aⁿ defined by σ(a) = aσ for all a ∈ A^m.

Let X ⊆ A^m and Y ⊆ Aⁿ for some natural numbers m and n. A partial function f : X → B is said to be a minor of a partial function g : Y → B if there exists a map σ: [n] → [m] such that X = σ⁻¹(Y) = {a ∈ A^m : aσ ∈ Y } and f = g ◦ σ|_X. The notation f ≤ g is used to designate the fact that f is a minor of g. For notational simplicity, we omit the “domain restriction” and write simply f = g ◦ σ for f = g ◦ σ|_X. If we want to emphasise the map σ that makes the above condition hold, we say that f is a minor of g (arising) via σ, briefly f ≤ g via σ.

It is not difficult to see that the minor relation ≤ is a quasiorder (a reflexive and transitive relation) on ℘_AB. The quasiorder ≤ on ℘_AB induces an equivalence relation ≡ on this set by the following: f ≡ g if and only if f ≤ g and g ≤ f. We say that f and g are equivalent if f ≡ g. Furthermore, the quasiorder ≤ on ℘_AB induces a partial order ≤ on the quotient ℘_AB/≡ by the following rule: f/≡ ≤ g/≡ if and only if f ≤ g.

Let f : X → B be a partial function, where X ⊆ Aⁿ. We say that the argument i ∈ [n] is essential in f, or f depends on argument i, if there exist tuples a = (a₁, … , a_n) and b = (b₁, … , b_n) in the domain of f such that a_j = b_j for all j ∈ [n] \ {i} and f(a) ≠ f(b). We call such a pair (a, b) a witness (of essentiality) of argument i in f. We denote by Essf the set of essential arguments of f, that is,

The number of essential arguments in f is called the essential arity of f and denoted by ess f, that is, ess f = |Ess f|.

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])

Let f : A^m → B and g : Aⁿ → B be total functions such that f ≤ g via σ. Then the following statements hold.

• (i) Ess f ⊆ Im σ.

• (ii) For every i ∈ Ess f, we have that σ⁻¹(i) ∩ Ess g ≠ ∅︀.

• (iii) ess f ≤ ess g.

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 X and Y be sets given by

Define and by

We see that $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 1& 2\end{array}\right)$, Ess f = {1, 2} and Ess g = {3}. Now, 1 ∈ Ess f but σ⁻¹(1) ∩ Ess g = {1, 2} ∩ {3} = ∅︀, and ess f > ess g.

Lemma 2.3.([12, Lemma 2.2.4(vi)])

Let f : A^m → B, g : Aⁿ → B be total functions, and assume that f ≤ g via σ. Then f ≡ g if and only if ess f = ess g.

Fact 2.4

Let f and g be total functions. Then the following statements hold.

• (i) ess f = 0 if and only if f is constant.

• (ii) f < g implies essf < ess g.

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 n ∈ ℕ₊. For S ⊆ [n], the characteristic tuple of S is e_S := (a₁, … , a_n) where

for every i ∈ [n].

Example 2.5

Let n ∈ ℕ₊. We define a partial function of arity n, where

by

for all x ∈ X. We define a partial function of arity 2n, where

by

for all y ∈ Y. Then f ≤ g via the map σ: [2n] → [n] given by σ(i) = ⌈ i/2⌉ for all i ∈ [2n], where ⌈·⌉ is the ceiling function. We can further see that ess f = n and ess g = 0.

Let f : X → B, where X ⊆ Aⁿ, be a partial function and $I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$, where $\left(\begin{array}{c}[n]\\ 2\end{array}\right)$ designates the set of all two-element subsets on [n]. A partial function $f_I:{\underset{\_}{\delta }}_I^{-1}(X)\to B$ defined by the rule f_I (a) = f(aδ_I ) for all ${\underset{\_}{\delta }}_I^{-1}(X)$, where δ_I : [n] → [n − 1] is defined as

is called an identification minor of f. In explicit terms, if I = {i, j} with i < j, then

for all $(a_1,\dots ,a_{n-1})\in {\underset{\_}{\delta }}_I^{-1}(X)$.

The identification minors f_I are perhaps the most relevant among all minors of f, because every minor of f is equivalent to one that is obtained by successively identifying just a single pair of arguments at a time (see [12, Lemma 2.2.11, Fact 2.2.12]). As illustrated by Example 2.5, the essential arity of a minor of a partial function can be much larger than the essential arity of the given function itself. On the other hand, Proposition 2.7 below shows that the essential arity can only increase by at most 1 when a single pair of arguments is identified. The large increase in the essential arity seen in Example 2.5 is possible because many arguments are identified.

Lemma 2.6

Let f be a partial function of arity n and$I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$. If k ∈ Ess f_I\δ_I (I), then${\delta }_I^{-1}(k)\in \text{Ess\hspace{0.17em}}f\backslash I$.

Proposition 2.7

Let f be a partial function of arity n and$I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$. Then ess f_I ≤ ess f + 1.

Lemma 2.8

Let X ⊆ A^m, Y ⊆ Aⁿ, f : X → B, g : Y → B and f ≤ g via σ. For each i ∈ Ess f, if there exists a witness (a, b) of essentiality of the i-th argument of f and for some linear order ≤ of σ⁻¹(i) it holds that$C_{\le }^{(\mathbf{a},\mathbf{b})}(i)\subseteq Y$, then σ⁻¹(i) ∩ Ess g ≠ ∅︀.

Example 2.9

Let X and Y be sets given by

and

Define and by

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 2& 2& 2& 3\end{array}\right)$. Now, σ⁻¹(2) ∩ Ess g = {2, 3, 4} ∩ {4, 5} ≠ ∅︀ and σ⁻¹(3) ∩ Ess g = {5} ∩ {4, 5} ≠ ∅︀. But for 2 ∈ Ess f, $C_{\le }^{((0,0,0),(0,1,0))}(2)⊈Y$ for every linear order ≤ on σ⁻¹(2).

Corollary 2.10

Let X ⊆ A^m, Y ⊆ Aⁿ, f : X → B, g : Y → B and f ≤ g via σ. For each i ∈ Ess f, if there exists a witness (a, b) of essentiality of the i-th argument of f and for some linear order ≤ of σ⁻¹(i) it holds that$C_{\le }^{(\mathbf{a},\mathbf{b})}(i)\subseteq Y$, then ess f ≤ ess g.

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 f : X → B with X ⊆ Aⁿ be a partial function. A subset S ⊆ [n] is essential in f if there exist tuples a, b ∈ X such that a_i = b_i for all i ∈ [n] \ S and f(a) ≠ f(b).

The pair (a, b) is called a witness of essentiality of S in f. We denote the collection of essential sets in f by ES(f) and esf := |ES(f)|.

A set M ∈ ES(f) is called a minimal element of ES(f) if N ⊆ M implies M = N for all N ∈ ES(f). We denote the set of all minimal elements of ES(f) by MES(f) and we set mes(f) := |MES(f)|. We can see that for every partial function f, ES(f) is an upper set of (℘([n]); ⊆).

These notions seem reasonable because for total functions they coincide with the classical notion of essential arguments. More generally, for a partial function f : X → B with X ⊆ Aⁿ and i ∈ [n] the following are equivalent:

• (1) argument i is essential in f.

• (2) {i} is an essential set in f.

• (3) {i} is a minimal essential set in f.

Example 3.2

Let X = {(0, 0, 0), (0, 0, 1), (1, 1, 0)}. Define by

Then {3}, {1, 2}, {1, 3}, {2, 3} and {1, 2, 3} are essential sets in f. Hence, MES(f) = {{3}, {1, 2}} and mes(f) = 2.

Recall from Lemma 2.1 that for total functions f and g, ess f ≤ ess g whenever f ≤ g; moreover, ess f = mes(f) and ess g = mes(g), that is, mes(f) ≤ mes(g) whenever f ≤ g. In contrast, for partial functions if f is a minor of g, then it does not necessarily hold that mes(f) ≤ mes(g), as shown by the following example.

Example 3.3

Let X and Y be sets given by

and

Define and by

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 2& 2& 3& 4\end{array}\right)$.

Now, we see that MES(f) = {{1, 2, 3}, {2, 3, 4}} and MES(g) = {{2}}, that is, mes(f) = 2 > 1 = mes(g).

Lemma 3.4

Let X ⊆ A^m, Y ⊆ Aⁿ, f : X → B, g : Y → B and f ≤ g via σ. We have that for all S ⊆ [m], if S ∈ ES(f), then σ⁻¹(S) ∈ ES(g).

Example 3.5

Let X and Y be sets given by

and

Define and by

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 1& 2& 3\end{array}\right)$. Now, we can see that MES(f) = {{1, 2}, {2, 3}} and MES(g) = {{1}, {3, 4}}. It is clear that {1, 2} ∈ MES(f) but σ⁻¹({1, 2}) = {1, 2, 3} ∉ MES(g).

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.

Theorem 3.6

Let f and g be partial functions such that f ≤ g via σ. Assume that σ⁻¹(S) ∈ MES(g) for all S ∈ MES(f). Then mes(f) ≤ mes(g).

Example 3.7

Let X and Y be sets given by

Define and by

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 1& 2\end{array}\right)$. We consider (0, 0, 0) = (0, 0)σ, (0, 0, 1) = (0, 1)σ and (1, 1, 0) = (1, 0)σ. Thus, f ≤_s g via σ.

Example 3.8

Let X and Y be sets given by

and

Define and by

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 2& 2& 3\end{array}\right)$. Non-surjectivity is obvious for cardinality reasons. This shows that f is not a surjective minor of g.

Lemma 3.9

Let f and g be partial functions such that f ≤ _sg via σ. If S ∈ ES(g), then σ(S) ∈ ES(f).

Proposition 3.10

Let f and g be partial functions such that f ≤ _s g via σ. If S ∈ MES(g), then σ(S) ∈ MES(f).

Proposition 3.11

Let f and g be partial functions such that f ≤ _s g via σ. If S ∈ MES(f), then σ⁻¹(S) ∈ MES(g).

Theorem 3.12

Let f and g be partial functions. If f ≤ _s g via σ, then mes(f) = mes(g).

In this section, we will consider our next variant of essential arity: the width of the poset of essential sets. Recall that a poset (P;≤) is called an antichain if for each distinct x, y ∈ P, we have x ≰ y and y ≰ x. We call an antichain Q a largest antichain in P if Q is a partially ordered subset of P and |R| ≤ |Q| for every antichain R in P. Let P be a poset. The width of P, denoted by w(P), is the cardinality of the largest antichain in P (see [15]).

Let f : X → B, where X ⊆ Aⁿ, be a partial function. Then we can see that the poset (ES(f); ⊆) is a partially ordered subset of (℘([n]); ⊆). We are interested in w(ES(f)), the width of the poset of essential sets of f. Unfortunately, as shown by the following example, also this quantity may increase upon formation of minors.

Example 4.1

Let X and Y be sets given by

and

Define and by

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 1& 2\end{array}\right)$. We see that ES(f) = {{1}, {1, 2}, {1, 3}, {1, 2, 3}} and ES(g) = {{1, 2}, {1, 2, 3}}. Then the largest antichain in (ES(f); ⊆) is {{1, 2}, {1, 3}} and {{1, 2, 3}} is a largest antichain in (ES(g); ⊆), that is, w(ES(f)) = 2 > 1 = w(ES(g)). We observe that ℱ = {{1, 2}, {1, 3}} is an antichain in (ES(f); ⊆), but σ⁻¹(ℱ) = {{1, 2}, {1, 2, 3}} is not an antichain in (ES(g); ⊆).

We will still provide a sufficient condition for functions f and g with f ≤ g to satisfy w(ES(f)) ≤ w(ES(g)). For this, we are going to make a few observations about minors arising via nonsurjective maps σ. Note that the following two statements do not mean the same thing:

• (1) f is a minor of g via surjective σ,

• (2) f is a surjective minor of g via σ.

(All combinations are possible: surjective minor via surjective σ (Example 2.2), nonsurjective minor via surjective σ (Example 3.8), surjective minor via nonsurjective σ (Example 4.1), nonsurjective minor via nonsurjective σ (modify Example 4.1 by adding (0, 1, 1) ↦ 1 to the definition of g).)

Lemma 4.2

Let f ≤ g via σ, where σ is surjective, and letbe an antichain in (ES(f); ⊆). Thenis an antichain in (ES(g); ⊆). Moreover, .

Corollary 4.3

Let f ≤ g via σ, where σ is surjective. Then (ES(g); ⊆) has an antichain of cardinality equal to the cardinality of the largest antichain in (ES(f); ⊆).

Theorem 4.4

If f ≤ g via σ, where σ is surjective, then w(ES(f)) ≤ w(ES(g)).

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 f : X → B, where X ⊆ Aⁿ, be a partial function, and let S be a nonempty subset of [n]. A witness (a, b) of essentiality of S in f is called an exact witness (of essentiality) of S in f if (a, b) is not a witness of essentiality of S \ {k} in f for any k ∈ S.

Example 5.2

Consider the following partial function f.

We see that ES(f) = {{1, 2}, {1, 2, 3}}, and the pair ((0, 0, 0), (1, 1, 0)) is a witness of essentiality of {1, 2} and {1, 2, 3} in f. It is easy to see that ((0, 0, 0), (1, 1, 0)) is not a witness of essentiality of {1, 2} \ {1} = {2} and {1, 2} \ {2} = {1} in f. Thus, ((0, 0, 0), (1, 1, 0)) is an exact witness of essentiality of {1, 2} in f. But, ((0, 0, 0), (1, 1, 0)) is not an exact witness of essentiality of {1, 2, 3} in f since ((0, 0, 0), (1, 1, 0)) is a witness of essentiality of {1, 2, 3} \ {3} = {1, 2} in f.

The following proposition provides a possibly clearer, equivalent condition describing exact witnesses of essentiality.

Proposition 5.3

Let f : X → B, where X ⊆ Aⁿ, be a partial function. Assume that the pair (a, b) is a witness of essentiality of a nonempty set S ⊆ [n] in f. Then the following statements are equivalent:

• (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_iif and only if i ∉ S.

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 f : X → B and g : Y → B, where X ⊆ A^m and Y ⊆ Aⁿ, be partial functions. We observe that if f ≤ g via σ, then [m] \ Im σ ⊆ Ficf.

Example 5.5

Consider the following partial function f.

We see that the 3rd argument is fictitious in f since (0, 1, 0), (0, 1, 1), (1, 0, 0) and (1, 0, 1) are not in the domain, and moreover f(0, 0, 0) = f(0, 0, 1) and f(1, 1, 0) = f(1, 1, 1).

Definition 5.6

Let f : X → B, where X ⊆ Aⁿ, be a partial function. A subset S ⊆ [n] is called an exact essential set in f if S is the empty set, or S does not contain any fictitious argument of f and there exists a pair (a, b), where a, b ∈ Aⁿ, such that (a, b) is an exact witness of essentiality of S in f. We denote the set of all exact essential sets in f by XES(f) and we set xes f := |XES(f)|.

Remark 5.7

We observe that XES(f) ≠ ∅︀ since ∅︀ ∈ XES(f), every minimal essential set in f is an exact essential set in f, and every exact essential set in f is an essential set in f, but the converse is not true by Example 5.2.

We note that if S is an exact essential set in a total function f, then every element of S is an essential argument by Definition 5.6 and Remark 5.4.

Since the number of essential sets of an n-ary function can be as large as 2ⁿ, a number exponential to the arity, we find it convenient to rescale this quantity logarithmically so as to stay in the same order of magnitude as the arity.

Definition 5.8

The exact essential hyperarity of a partial function f is defined as ß f := log₂ xes f.

Example 5.9

Consider the partial function f of Example 5.5. We see that {1, 2} is an exact essential set in f since {1, 2} does not contain any fictitious argument of f, and the pair ((0, 0, 0), (1, 1, 0)) is an exact witness of essentiality of {1, 2} in f. However, {1, 2, 3} is not an exact essential set in f since it contains a fictitious argument of f.

In general, if f ≤ g via σ and S is a nonempty exact essential set in f, then σ⁻¹(S) is not necessarily an exact essential set in g.

Example 5.10

Consider the following partial functions.

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 2\end{array}\right)$. We see that S = {1, 2} ∈ XES(f) but σ⁻¹(S) = {1, 2, 3} ∉ XES(g). Observe that the 3rd argument is fictitious in g and σ⁻¹(S) \ {3} ∈ XES(g).

Theorem 5.11

Let f ≤ g via σ. If S is a nonempty exact essential set in f, then σ⁻¹(S) \ Ficg is an exact essential set in g.

Corollary 5.12

Let f ≤ g via σ. Then xes f ≤ xes g. Equivalently, ß f ≤ ß g.

Remark 5.13

Let f : X → B be a partial function, where X ⊆ Aⁿ. We can conclude immediately from definitions the following:

• (i) i ∈ Ess f if and only if {i} ∈ XES(f).

• (ii) ess f ≤ xes f.

• (iii) f is constant if and only if xes f = 1, or, equivalently, ß f = 0.

Lemma 5.14

Let f : A^m → B, g : Aⁿ → B be total functions, and assume that f ≤ g via σ. Then the mapping ϕ : XES(f) \ {∅︀} → XES(g) \ {∅︀} defined by ϕ(S) = σ⁻¹(S) ∩ Ess g is injective.

Proposition 5.15

Let f : A^m → B, g : Aⁿ → B be total functions, and assume that f ≤ g via σ. Then we have that f ≡ g if and only if xes f = xesg (equivalently, ß f = ßg).

Example 5.16

Consider the following partial functions.

Then $f\le g\hspace{0.17em}\text{via\hspace{0.17em}}\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 1& 2\end{array}\right)$. We see that xes f = 2 = xesg but g is not a minor of f. Hence f ≢ g.

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 f : Aⁿ → B be a function that depends on all of its variables, n ≥ 2. The arity gap of f is defined by the following

The arity gap of a total function is clearly at least 1. Salomaa showed that the arity gap can be as large as |A| = k, where k ≥ 2, by providing an example of a function f : A^k → A such that ess f = k and ess f_I = 0 for every $I\in \left(\begin{array}{c}[k]\\ 2\end{array}\right)$. He also showed that the arity gap of any Boolean function is at most 2 (see [14]).

Later, Willard [17] extended this result to functions on arbitrary finite domains. He showed that the arity gap of any function f : Aⁿ → B, where k = |A| and n > k, is at most 2.

Partial functions may have a negative arity gap. By Proposition 2.7,

See Example 2.2 for an example of a function f with gap f = −1.

The notion of exact essential hyperarity suggests an analogue of arity gap. Let f : X → B be a partial function, where X ⊆ Aⁿ. Define the exact hyperarity gap of f by

Obviously, for any partial function f : X → B, where X ⊆ Aⁿ, we have that 0 ≤ xgap f ≤ n.

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 n.

Example 6.1

Let n ≥ 4 and A := [k] with k ≥ n − 1. Define the sets

and

Define a partial function where f⁻¹(0) = X₀ and f⁻¹(1) = X₁. Then xes f = 2ⁿ and xes f_I = 1 for all $I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$. Thus,

Example 6.2

Let n ≥ 2. Define a Boolean (total) function by

Then xes f = 2ⁿ and xes f_I = 2ⁿ⁻¹ for all $I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$. Thus,

Definition 6.3. ([1])

Let oddsupp: ∪ _n≥1Aⁿ →℘(A) be the mapping defined by

A function f : Aⁿ → B is determined by oddsupp if there exists a mapping f* : ℘ (A) → B such that f = f* ◦ oddsupp |_Aⁿ.

Example 6.4

Suppose that {0, 1, 2} ⊆ A and . Define a function f* : ℘(A) → B by

Let f : Aⁿ → B be a function defined by f := f* ◦oddsupp |_Aⁿ. Let S be a nonempty subset of [n]. We must consider two different cases according to the parity of |S|.

• If |S| is odd, then the pair (0, a) is an exact witness of essentiality of S in f, where 0 = (0, … , 0) ∈ Aⁿ and a ∈ Aⁿ is defined by

  $$\mathbf{a}(i)=\{\begin{array}{ll}\hfill 0\hfill & \text{if\hspace{0.17em}}i\notin S,\hfill \\ \hfill 1\hfill & \text{if\hspace{0.17em}}i\in S.\hfill \end{array}$$

• If |S| is even, then S is a disjoint union of odd subsets S₁ and S₂ of S, and the pair (0, b) is an exact witness of essentiality of S in f, where 0 = (0, … , 0) ∈ Aⁿ and b ∈ Aⁿ is defined by

  $$\mathbf{b}(i)=\{\begin{array}{ll}\hfill 0\hfill & \text{if\hspace{0.17em}}i\notin S,\hfill \\ \hfill 1\hfill & \text{if\hspace{0.17em}}i\in S_1,\hfill \\ 2\hfill & \text{if\hspace{0.17em}}i\in S_2\hfill \end{array}$$

We conclude that every subset of [n] is an exact essential set in f, that is, xes f = 2ⁿ. For any $I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$, the argument δ_I (I) is fictitious in f_I and f_I is equivalent to f* ◦ oddsupp |_Aⁿ⁻². Thus, every subset of [n − 1] which does not contain δ_I (I) is an exact essential set in f_I, that is, xesf_I = 2ⁿ⁻² for all $I\in \left(\begin{array}{c}[n]\\ 2\end{array}\right)$. Thus,

Willard’s upper bound for the arity gap can be stated as follows.

Theorem 6.5.([17, Lemma 1.2, Corollary 2.3])

Let A and B be arbitrary finite nonempty sets, and let k = |A|. Let f : Aⁿ → B, and assume that ess f = n. If n > k, then gap f ≤ 2. Moreover, if n > max(k, 3), then gap f = 2 if and only if f is determined by oddsupp.

The analogue of the above for the exact hyperarity gap of partial functions does not hold. The condition ess f = n means that f has no fictitious arguments. As shown by the following example, there exist partial functions f without fictitious arguments with xgapf > 2.

Example 6.6

Let k ∈ ℕ with k ≥ 2, let A := [k], and assume . Let a := (1, 2, … , k) and

Let X₀ := {u} and

Then X₀ and X₁ are disjoint subsets of A^k2, and we can define a partial function f : X₀ ∪ X₁ → B by f⁻¹(0) = X₀ and f⁻¹(1) = X¹. It is easy to see that the nonempty (exact) essential sets of f are precisely the subsets S of [k²] satisfying |S ∩ {ik + 1, ik + 2, … , ik + k}| = k − 1 for all 0 ≤ i ≤ k − 1. It follows that sf = log₂(k^k + 1) and sf_I = 0 for all $I\in \left(\begin{array}{c}[k^2]\\ 2\end{array}\right)$; thus, xgap f = log₂(k^k + 1) > 2.

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.

The second author was supported by the Development and Promotion of Science and Technology Talents Project (DPST), Thailand.