검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

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

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

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 : AnB 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 An is (a1, … , an) where aiA for all 1 ≤ in. We will use bold letters to denote tuples and corresponding italic letters with subscript to denote their components, that is, a = (a1, … , an). 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 : XB where XAn, 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 = An, 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 aAm as a mapping a: [m] → A; hence, a(i) = ai 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 An. For simplicity, we write aσ instead of aσ. Any map σ: [n] → [m] gives rise to a map σ : AmAn defined by σ(a) = aσ for all aAm.

Let XAm and YAn for some natural numbers m and n. A partial function f : XB is said to be a minor of a partial function g : YB if there exists a map σ: [n] → [m] such that X = σ−1(Y) = {aAm : aσY } and f = gσ|X. The notation fg 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 fg 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: fg if and only if fg and gf. We say that f and g are equivalent if fg. Furthermore, the quasiorder ≤ on ℘AB induces a partial order ≤ on the quotient ℘AB/≡ by the following rule: f/≡ ≤ g/≡ if and only if fg.

Let f : XB be a partial function, where XAn. We say that the argument i ∈ [n] is essential in f, or f depends on argument i, if there exist tuples a = (a1, … , an) and b = (b1, … , bn) in the domain of f such that aj = bj 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,

Ess f:={i[n]:argument iis essential in f}.

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 : AmB and g : AnB be total functions such that fg via σ. Then the following statements hold.

  • (i) Ess f ⊆ Im σ.

  • (ii) For every i ∈ Ess f, we have that σ−1(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

X={(0,0),(0,1),(1,0)}         and         Y={(0,0,0),(0,0,1),(1,1,0)}.

Define and by

fg(0,0)0(0,0,0)0(0,1)1(0,0,1)1(1,0)1(1,1,0)1.

We see that fgvia σ=(123112), Ess f = {1, 2} and Ess g = {3}. Now, 1 ∈ Ess f but σ−1(1) ∩ Ess g = {1, 2} ∩ {3} = ∅︀, and ess f > ess g.

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

Let f : AmB, g : AnB be total functions, and assume that fg via σ. Then fg 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 eS := (a1, … , an) where

ai={1if iS,0if iS,

for every i ∈ [n].

Example 2.5

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

X:={e{i}:i[n]}{0},

by

f(x)={0if x=0,1if xX\{0},

for all xX. We define a partial function of arity 2n, where

Y:={e{2i-1,2i}:i[n]}{0},

by

g(y)={0if y=0,1if yY\{0},

for all yY. Then fg 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 : XB, where XAn, be a partial function and I([n]2), where ([n]2) designates the set of all two-element subsets on [n]. A partial function fI:δ_I-1(X)B defined by the rule fI (a) = f(aδI ) for all δ_I-1(X), where δI : [n] → [n − 1] is defined as

δI(i)={iif i<max I,min Iif i=max Ii-1if i>max I,

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

fI(a1,,an-1)=f(a1,,aj-1,ai,aj,,an-1)

for all (a1,,an-1)δ_I-1(X).

The identification minors fI 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 andI([n]2). If k ∈ Ess fI\δI (I), thenδI-1(k)Ess f\I.

Proof

Let k ∈ Ess fI \ δI (I) and let (a, b) be a witness of essentiality of argument k in fI. Then aδI = c and bδI = d for some c, dX. That is,

(c1,,cn)=(aδI(1),,aδI(n))

and

(d1,,dn)=(bδI(1),,bδI(n)).

Since k ∈ Ess fI, we have that al = bl for all l ∈ [n − 1] \ {k}. Then aδI (p) = bδI (p) for all p[n]\{δI-1(k)}. Thus, cr = dr for all r[n]\{δI-1(k)}. Then f(c) = f(aδI) = fI (a) ≠ fI (b) = f(bδI) = f(d). This shows that (c, d) is a witness of essentiality of argument δI-1(k)in f. Since kδI (I), we have that δI-1(k)I. Thus, δI-1(k)Ess f\I.

Proposition 2.7

Let f be a partial function of arity n andI([n]2). Then ess fI ≤ ess f + 1.

Proof

By Lemma 2.6, we have

ess fIEss fI\δI(I)+1Ess f\I+1ess f+1.

Note that Example 2.2 shows that the inequality in Proposition 2.7 can hold as an equality.

Let XAm, YAn, f : XB, g : YB and fg via σ. Let i ∈ Ess f. Note that σ−1(i) is a nonempty set since Ess f ⊆ Im σ. Let ≤ be a linear order of the set σ−1(i), say σ−1(i) = {l1, … , lr} with l1 < l2 < · · · < lr. For each i ∈ Ess f and a witness of essentiality (a, b) of the i-th argument in f, we define C(a,b)(i):={c0,c1,,cr}, where

  • (i) c0 := aσ,

  • (ii) for each j = 1, … , r, let cj be the tuple obtained from cj−1 by changing the lj-th entry from ai to bi.

Lemma 2.8

Let XAm, YAn, f : XB, g : YB and fg 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 orderof σ−1(i) it holds thatC(a,b)(i)Y, then σ−1(i) ∩ Ess g ≠ ∅︀.

Proof

Let i ∈ Ess f. Then by Lemma 2.1(i), σ−1(i) ≠ ∅︀. Suppose that σ−1(i) = {l1, … , lr} with l1 < l2 < · · · < lr. Let a, bX be a witness of essentiality of the i-th argument in f. By our procedure, we have that c0, c1, … , crAn, c0 = aσ and cr = bσ. By our assumption, we now know that c0, c1, … , crY. Then

g(aσ)=f(a)f(b)=g(bσ).

That is, there exists k ∈ {0, … , r − 1} such that g(ck) ≠ g(ck+1). This means that ck and ck+1 witness the essentiality of the lk+1-th argument in g. Thus, lk+1 ∈ Ess g. That is, σ−1(i) ∩ Ess g ≠ ∅︀.

The following example shows that the converse of Lemma 2.8 does not hold.

Example 2.9

Let X and Y be sets given by

X={(0,0,0),(0,1,0),(0,0,1)}

and

Y={(0,0,0,0,0),(0,1,1,1,0),(0,0,0,0,1),(0,1,0,0,1),(0,1,0,1,1)}.

Define and by

fg(0,0,0)0(0,0,0,0,0)0(0,1,0)1(0,1,1,1,0)1(0,0,1)1(0,0,0,0,1)1(0,1,0,0,1)0(0,1,0,1,1)1.

Then fgvia σ=(1234512223). Now, σ−1(2) ∩ Ess g = {2, 3, 4} ∩ {4, 5} ≠ ∅︀ and σ−1(3) ∩ Ess g = {5} ∩ {4, 5} ≠ ∅︀. But for 2 ∈ Ess f, C((0,0,0),(0,1,0))(2)Y for every linear order ≤ on σ−1(2).

Corollary 2.10

Let XAm, YAn, f : XB, g : YB and fg 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 orderof σ−1(i) it holds thatC(a,b)(i)Y, then ess f ≤ ess g.

Proof

Apply Lemma 2.1 and Lemma 2.8.

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 : XB with XAn be a partial function. A subset S ⊆ [n] is essential in f if there exist tuples a, bX such that ai = bi 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 NM 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 : XB with XAn 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

f(0,0,0)0(0,0,1)1(1,1,0)1.

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 fg; moreover, ess f = mes(f) and ess g = mes(g), that is, mes(f) ≤ mes(g) whenever fg. 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

X={(0,0,0,0),(1,1,1,0),(0,1,1,1)}

and

Y={(0,0,0,0,0),(0,1,0,0,0),(1,1,1,1,0),(0,1,1,1,1)}.

Define and by

fg(0,0,0,0)0(0,0,0,0,0)0(1,1,1,0)1(0,1,0,0,0)1(0,1,1,1)1(1,1,1,1,0)1(0,1,1,1,1)1.

Then fgvia σ=(1234512234).

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 XAm, YAn, f : XB, g : YB and fg via σ. We have that for all S ⊆ [m], if S ∈ ES(f), then σ−1(S) ∈ ES(g).

Proof

Let S ⊆ [m] be such that S ∈ ES(f). Then there exist a, bX such that (a, b) is a witness of essentiality of S in f. Let c := aσ and d := bσ. Then

(aσ(1),,aσ(n))=(c1,,cn),(bσ(1),,bσ(n))=(d1,,dn).

Since ai = bi for all i ∈ [m] \ S, we have that aσ(i) = bσ(i) for all i ∈ [n] \ σ−1(S). Thus, ci = di for all i ∈ [n] \ σ−1(S); moreover,

g(c)=g(aσ)=f(a)f(b)=g(bσ)=g(d).

We conclude that the pair (c, d) is a witness of essentiality of σ−1(S) in g. That is, σ−1(S) ∈ ES(g).

We observe that the converse of Lemma 3.4 does not hold as shown by Example 3.3. In fact, if we let S = {2}, then σ−1(S) = {2, 3} ∈ ES(g) but S ∉ ES(f). On the other hand, if S ∈ ES(g), then it is not necessarily true that σ(S) ∈ ES(f) by Example 3.3. Moreover, if S is a minimal essential set in f, then σ−1(S) may not be a minimal essential set in g, as shown by the following example.

Example 3.5

Let X and Y be sets given by

X={(0,0,0),(1,1,0),(0,1,1)}

and

Y={(0,0,0,0),(1,1,1,0),(0,0,1,1),(1,0,0,0)}.

Define and by

fg(0,0,0)0(0,0,0,0)0(1,1,0)1(1,1,1,0)1(0,1,1)1(0,0,1,1)1(1,0,0,0)1.

Then fgvia σ=(12341123). 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({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.

Open problem 1

Provide necessary and sufficient conditions for functions f and g with fg to satisfy mes(f) ≤ mes(g).

As a partial answer to the above problem, the following theorem provides a sufficient condition.

Theorem 3.6

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

Proof

The map σ−1 : MES(f) → MES(g) is clearly injective, which implies mes(f) ≤ mes(g).

Next, we introduce a particular kind of minor that forces the hypothesis of Theorem 3.6. Let f : XB and g : YB, where XAm and YAn, be partial functions. A partial function f is said to be a surjective minor of a partial function g if fg via σ for some σ: [n] → [m], and for every aY , there exists bX such that bσ = a; in other words, the map σ|X : XY is surjective. We designate the fact that f is a surjective minor of g by fsg, or if we want to specify a map σ, we write fsg via σ.

Example 3.7

Let X and Y be sets given by

X={(0,0),(0,1),(1,0)}         and         Y={(0,0,0),(0,0,1),(1,1,0)}.

Define and by

fg(0,0)0(0,0,0)0(0,1)1(0,0,1)1(1,0)1(1,1,0)1.

Then fgvia σ=(123112). We consider (0, 0, 0) = (0, 0)σ, (0, 0, 1) = (0, 1)σ and (1, 1, 0) = (1, 0)σ. Thus, fs g via σ.

Example 3.8

Let X and Y be sets given by

X={(0,0,0),(0,1,0),(0,0,1)}

and

Y={(0,0,0,0),(0,1,1,0),(0,0,1,0),(0,0,0,1)}.

Define and by

fg(0,0,0)0(0,0,0,0)0(1,1,0)1(0,1,1,0,)1(0,0,1)1(0,0,1,0)1(0,0,0,1)1.

Then fgvia σ=(12341223). 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 fsg via σ. If S ∈ ES(g), then σ(S) ∈ ES(f).

Proof

Since S ∈ ES(g), there exist a, bY such that (a, b) is a witness of essentiality of S in g. By assumption there exist c, dX such that cσ = a and dσ = b, that is,

(cσ(1),,cσ(n))=(a1,,an),(dσ(1),,dσ(n))=(b1,,bn).

Since ai = bi for all i ∈ [n] \ S, we have that cσ(i) = dσ(i) for all i ∈ [n] \ S. This implies that ci = di for all i ∈ [m] \ σ(S); moreover,

f(c)=g(cσ)=g(a)g(b)=g(dσ)=f(d).

Therefore, (c, d) is a witness of essentiality of σ(S) in f, that is, σ(S) ∈ ES(f).

Proposition 3.10

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

Proof

Let S ∈ MES(g). Then by Lemma 3.9, σ(S) ∈ ES(f). Suppose that there exists K ∈ MES(f) such that Kσ(S). Then by Lemma 3.4, σ−1(K) ∈ ES(g) and σ−1(K) ⊆ S. By the minimality of S, we obtain that σ−1(K) = S. This implies that K = σ(S). Therefore, σ(S) ∈ MES(f).

Proposition 3.11

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

Proof

Since S ∈ MES(f), by Lemma 3.4 we have that σ−1(S) ∈ ES(g). Suppose that there exists K ∈ MES(g) such that Kσ−1(S). Then σ(K) ∈ MES(f) by Proposition 3.10 and σ(K) ⊆ S. By the minimality of S, we have that σ(K) = S. Thus, K = σ−1(S), that is, σ−1(S) ∈ MES(g).

Thus, the hypothesis of Theorem 3.6 holds whenever f is a surjective minor of g. In fact, in this case, an even stronger conclusion holds.

Theorem 3.12

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

Proof

It suffices to show that the map ψ : MES(f) → MES(g) given by ψ(A) = σ−1(A) for all A ∈ MES(f) is bijective.

The map ψ is well defined by Proposition 3.11, and it is clearly injective. The surjectivity of ψ follows from Proposition 3.10.

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, yP, we have xy and yx. 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 : XB, where XAn, 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

X={(0,0,0),(0,0,1),(1,0,0),(1,0,1)}

and

Y={(0,0,0),(1,1,0)}.

Define and by

fg(0,0,0)0(0,0,0)0(0,0,1)0(1,1,0)1.(1,0,0)1(1,0,1)1

Then fgvia σ=(123112). 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(ℱ) = {{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 fg 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 fg via σ, where σ is surjective, and letbe an antichain in (ES(f); ⊆). Thenis an antichain in (ES(g); ⊆). Moreover, .

Proof

First, we observe that by Lemma 3.4. Let K and L be distinct members of . Then K = σ−1(S) and L = σ−1(T) for some distinct . Suppose that KL. Then by the surjectivity of σ, S = σ(σ−1(S)) ⊆ σ(σ−1(T)) = T. This is a contradiction to the fact that is an antichain in (ES(f); ⊆). Similarly, if LK, then a contradiction arises for the same reason. Therefore, is an antichain in (ES(g); ⊆). By the surjectivity of σ, we can define a bijective map by ψ(S) = σ−1(S) for all . Thus, .

Corollary 4.3

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

Proof

Let be a largest antichain in (ES(f); ⊆). Then by Lemma 4.2, is an antichain in (ES(g); ⊆) and .

Theorem 4.4

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

Proof

Let be the largest antichain in (ES(f); ⊆). We observe that for each antichain in ES(g), where ℒ is a largest antichain in (ES(g); ⊆). Thus, by Corollary 4.3, where is the largest antichain in (ES(g); ⊆). Therefore, 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 : XB, where XAn, 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 kS.

Example 5.2

Consider the following partial function f.

f(0,0,0)0(1,1,0)1

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 : XB, where XAn, 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 kS,

  • (ii) for all i ∈ [n], ai = biif and only if iS.

Proof

(i) ⇒ (ii): Let i ∈ [n]. Suppose that ai = bi. If iS, then (a, b) is a witness of essentiality of S \ {i} in f. This contradicts our presumption; hence iS. On the other hand, if iS, then it is clear that ai = bi by the fact that (a, b) is a witness of essentiality of S in f.

(ii) ⇒ (i): Suppose, to the contrary, that there exists kS such that (a, b) is a witness of essentiality of S \ {k} in f. This implies that ak = bk. But this means that kS. This is a contradiction to our assumption. Therefore, we have that (a, b) is a witness of essentiality of S \ {k} in f.

Let a := (a1, … , an) ∈ An. Let i ∈ [n] and bA. We denote the tuple

(a1,,ai-1,b,ai+1,,an)An

by a(ib).

Let f : XB, where XAn, be a partial function. The i-th argument is fictitious in f if for all aAn, one of the following conditions holds:

  • (i) a(ib) ∉ X for all bA,

  • (ii) a(ib) ∈ X for all bA and f(a(ib)) = f(a(ic)) for all b, cA.

Denote the set of all fictitious arguments of f by Ficf.

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 : XB and g : YB, where XAm and YAn, be partial functions. We observe that if fg via σ, then [m] \ Im σFicf.

Example 5.5

Consider the following partial function f.

f(0,0,0)0(0,0,1)0(1,1,0)1(1,1,1)1

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 : XB, where XAn, 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, bAn, 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 2n, 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 := log2 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 fg via σ and S is a nonempty exact essential set in f, then σ−1(S) is not necessarily an exact essential set in g.

Example 5.10

Consider the following partial functions.

fg(0,0)0(0,0,0)0(1,1)1(0,0,1)0(1,1,0)1(1,1,1)1

Then fgvia σ=(123122). We see that S = {1, 2} ∈ XES(f) but σ−1(S) = {1, 2, 3} ∉ XES(g). Observe that the 3rd argument is fictitious in g and σ−1(S) \ {3} ∈ XES(g).

Theorem 5.11

Let fg via σ. If S is a nonempty exact essential set in f, then σ−1(S) \ Ficg is an exact essential set in g.

Proof

Assume that f is m-ary and g is n-ary. Denote by X and Y the domain of f and the domain of g, respectively. Since S is an exact essential set in f, there exist tuples a, bX such that the pair (a, b) is an exact witness of essentiality of S in f; this means, by Proposition 5.3, that f(a) ≠ f(b) and for all i ∈ [m], ai = bi if and only if iS. Without loss of generality, assume that Ficg = [] for some ∈ ℕ. Let u := (bσ(1), … , bσ(), aσ(+1), … , aσ(n)). By the definition of fictitious arguments, we have uY and f(aσ) = f(u); hence, the pair (u, bσ) is a witness of essentiality of σ−1(S) \ Ficg in g.

It remains to show that (u, bσ) is an exact witness. Let k ∈ [n]. Consider first the case where kσ−1(S) \ Ficg. Then σ(k) ∈ S, so aσ(k)bσ(k) because (a, b) is an exact witness of S in f; therefore (aσ)(k) = aσ(k)bσ(k) = (bσ)(k) = u(k). Consider then the case where kσ−1(S) \ Ficg. If kFicg, then u(k) = bσ(k) = (bσ)(k). Otherwise (kσ−1(S) and kFicg) we have σ(k) ∉ S, so u(k) = aσ(k) = bσ(k) = (bσ)(k). It now follows from Proposition 5.3 that the pair (u, bσ) is an exact witness of essentiality of σ−1(S) \ Ficg in g.

Corollary 5.12

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

Remark 5.13

Let f : XB be a partial function, where XAn. 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.

Proofxes f=1The empty set is the only exact essential set in f.For every nonempty subset S[n],there is noexact witness of essentiality of Sin f.f(a)=f(b)for any a,bX.fis constant.
  • (iv) xes f ≤ |ES(f)|.

  • (v) mes(f) ≤ xes f.

We observe that if f and g are total functions such that fg via σ, then for every i ∈ Ess f, σ−1({i}) \ Ficg = σ−1(i) ∩ Ess g ≠ ∅︀.

Lemma 5.14

Let f : AmB, g : AnB be total functions, and assume that fg via σ. Then the mapping ϕ : XES(f) \ {∅︀} → XES(g) \ {∅︀} defined by ϕ(S) = σ−1(S) ∩ Ess g is injective.

Proof

By Theorem 5.11, it is clear that ϕ is well defined. Let S, S′ ∈ XES(f) such that SS′. It is clear that S, S′ ⊆ Ess f. Without loss of generality, assume that iS and iS′. By Lemma 2.1(ii), σ−1(i) ∩ Ess g ≠ ∅︀. Then there exists i′ ∈ σ−1(i) ∩ Ess g. We have i′ ∈ σ−1(S) ∩ Ess g and i′ ∉ σ−1(S′) ∩ Ess g, which shows that ϕ is injective.

As a consequence, an analogue of Lemma 2.3 is true for the exact essential hyperarity of total functions.

Proposition 5.15

Let f : AmB, g : AnB be total functions, and assume that fg via σ. Then we have that fg if and only if xes f = xesg (equivalently, ß f = ßg).

Proof

By Corollary 5.12, fg implies xes f = xesg. For the converse implication, assume xes f = xesg. By Lemma 5.14, the map ϕ: XES(f) \ {∅︀} → XES(g) \ {∅︀}, ϕ(S) = σ−1(S) ∩ Ess g is injective, and it is, in fact, bijective because xes f = xesg. Suppose, to the contrary, that fg. Then f < g, so essf < ess g by Fact 2.4(ii). In view of Remark 5.13(i), there exists i ∈ Ess g (i.e., {i} ∈ XES(g)) such that S := ϕ−1({i}) has at least two elements, say {a, b} ⊆ S, ab. We have {a, b} ⊆ Ess f by Remark 5.7; hence σ−1(a) ∩ Ess g ≠ ∅︀ and σ−1(b) ∩ Ess g ≠ ∅︀ by Lemma 2.1(ii), so there exist a′ ∈ σ−1(a) ∩ Ess g and b′ ∈ σ−1(b) ∩ Ess g. Since σ−1(a) ∩ σ−1(b) = ∅︀, we have a′ ≠ b′. Consequently,

{a,b}σ-1({a,b})Ess gσ-1(S)Ess g=φ(S)={i},

which yields the desired contradiction, and we conclude that fg.

The following example shows that Proposition 5.15 does not hold for partial functions in general.

Example 5.16

Consider the following partial functions.

fg(0,0)0(0,0,0)0(0,1)1(0,0,1)1(1,1)1(1,1,1)1

Then fgvia σ=(123112). We see that xes f = 2 = xesg but g is not a minor of f. Hence fg.

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

gap f:=minI([n]2)ess f-ess fI.

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 : AkA such that ess f = k and ess fI = 0 for every I([k]2). 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 : AnB, where k = |A| and n > k, is at most 2.

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

gap f:=minI([n]2)ess f-ess fIess f-(ess f+1)=-1.

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 : XB be a partial function, where XAn. Define the exact hyperarity gap of f by

xgap f:=minI([n]2)βf-βfI.

Obviously, for any partial function f : XB, where XAn, we have that 0 ≤ xgap fn.

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 kn − 1. Define the sets

X0={(1,2,,n-1)δ{l,l+1}:1ln-1}

and

X1={aAn:a(l)a(l+1)for all 1ln-1}.

Define a partial function where f−1(0) = X0 and f−1(1) = X1. Then xes f = 2n and xes fI = 1 for all I([n]2). Thus,

xgap f:=minI([n]2)βf-βfI=n.

Example 6.2

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

f(x)={0if x=0,1otherwise.

Then xes f = 2n and xes fI = 2n−1 for all I([n]2). Thus,

xgap f:=minI([n]2)βf-βfI=1.

Definition 6.3. ([1])

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

oddsupp(a1,,an)={aA:{i[n]:aj=a}is odd}.

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

Example 6.4

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

f*(X)={0if X=or X={0},1otherwise.

Let f : AnB be a function defined by f := f* ◦oddsupp |An. 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) ∈ An and aAn is defined by

    a(i)={0if iS,1if iS.

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

    b(i)={0if iS,1if iS1,2if iS2

We conclude that every subset of [n] is an exact essential set in f, that is, xes f = 2n. For any I([n]2), the argument δI (I) is fictitious in fI and fI is equivalent to f* ◦ oddsupp |An−2. Thus, every subset of [n − 1] which does not contain δI (I) is an exact essential set in fI, that is, xesfI = 2n−2 for all I([n]2). Thus,

xgap f:=minI([n]2)βf-βfI=2.

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 : AnB, 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

u:=(1,,1k,2,,2k,,k,,kk)Ak2.

Let X0 := {u} and

X1:={(aσ1,aσ2,,aσk)Ak2σ1,σ2,,σkpermutations of [k]}.

Then X0 and X1 are disjoint subsets of Ak2, and we can define a partial function f : X0X1B by f−1(0) = X0 and f−1(1) = X1. It is easy to see that the nonempty (exact) essential sets of f are precisely the subsets S of [k2] satisfying |S ∩ {ik + 1, ik + 2, … , ik + k}| = k − 1 for all 0 ≤ ik − 1. It follows that sf = log2(kk + 1) and sfI = 0 for all I([k2]2); thus, xgap f = log2(kk + 1) > 2.

Open problem 2

Provide a (sharp and nontrivial) upper bound for the exact hyperarity gap of n-ary functions in ℘AB. (A trivial upper bound for an n-ary function is n, but is this sharp?)

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.

  1. J. Berman, and A. Kisielewicz. On the number of operations in a clone. Proc Amer Math Soc., 122(1994), 359-369.
    CrossRef
  2. Y. Breitbart. Essential variables of functions of the algebra of logic. Russian, Dokl Akad Nauk USSR., 172(1967), 9-10.
  3. KN. Čimev. Separable sets of arguments of functions. Studies 180/1986, , Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, 1986.
  4. 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.
    CrossRef
  5. 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.
    CrossRef
  6. M. Couceiro, and E. Lehtonen. Generalizations of Świerczkowski’s lemma and the arity gap of finite functions. Discrete Math., 309(2009), 5905-5912.
    CrossRef
  7. 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.
  8. RO. Davies. Two theorems on essential variables. J London Math Soc., 41(1966), 333-335.
    CrossRef
  9. K. Denecke, and J. Koppitz. Essential variables in hypersubstitutions. Algebra Universalis., 46(2001), 443-454.
    CrossRef
  10. 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.
    CrossRef
  11. O. Ekin, S. Foldes, PL. Hammer, and L. Hellerstein. Equational characterizations of Boolean function classes. Discrete Math., 211(2000), 27-51.
    CrossRef
  12. 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.
  13. N. Pippenger. Galois theory for minors of finite functions. DiscreteMath., 254(2002), 405-419.
  14. 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.
  15. BSW. Schröder. Ordered sets: An introduction, , Birkhäuser, Basel, 2003.
    CrossRef
  16. S. Shtrakov. Essential arity gap of Boolean functions. Serdica J Comput., 2(2008), 249-266.
  17. R. Willard. Essential arities of term operations in finite algebras. Discrete Math., 149(1996), 239-259.
    CrossRef
  18. RO. Winder. Fundamentals of threshold logic. Applied Automata Theory, , Academic Press, New York, 1968:235-318.
    CrossRef