=Paper=
{{Paper
|id=Vol-2925/short5
|storemode=property
|title=Monotonic computation rules for nonassociative calculus
|pdfUrl=https://ceur-ws.org/Vol-2925/short5.pdf
|volume=Vol-2925
|authors=Miguel Couceiro,Michel Grabisch
|dblpUrl=https://dblp.org/rec/conf/algos/CouceiroG20
}}
==Monotonic computation rules for nonassociative calculus==
https://ceur-ws.org/Vol-2925/short5.pdf
M ONOTONIC COMPUTATION RULES FOR NONASSOCIATIVE
CALCULUS
Miguel Couceiro Michel Grabisch
Université de Lorraine, CNRS, Inria N.G.E., LORIA Paris School of Economics, University of Paris I
F-54000 Nancy, France 106-112, Bd de l’Hôpital, 75013 Paris, France
miguel.couceiro@loria.fr michel.grabisch@univ-paris1.fr
Dedicated to Maurice Pouzet on the occasion of his 75th birthday
A BSTRACT
In this paper we revisit the so-called computation rules for calculus using a single nonassociative
binary operation over possibly infinite sequences of integers. In this paper we focus on the symmetric
maximum 6 that is an extension of the usual maximum _ so that 0 is the neutral element, and x is
the symmetric (or inverse) of x, i.e., x 6( x) = 0. However, such an extension does not preserve
the associativity of _. This fact asks for systematic ways of bracketing terms of a sequence using 6,
and which we refer to as computation rules.
These computation rules essentially reduce to deleting terms of sequences based on the condition
x 6( x) = 0, and they can be quasi-ordered as follows: say that rule 1 is below rule 2 if for all
sequences of numbers, rule 1 deletes more terms in the sequence than rule 2. As it turns out, this
quasi-ordered set is extremely complex, e.g., it has infinitely many maximal elements and atoms, and
it embeds the powerset of natural numbers by inclusion.
Local properties of computation rules have also been presented by the authors, in particular, con-
cerning their canonical representations. In this paper we address the problem of determining those
computation rules that preserve the monotonicity of _, and present an explicit description of mono-
tonic computation rules in terms of their factorized irredundant form.
Keywords Nonassociative calculus · symmetric maximum · computation rules · monotonic rules
1 Motivation
This short contribution is the continuation of the work initiated in [1, 2], and we refer the reader to these references
for further motivation. Let L be a totally ordered set with bottom element 0, and let L := { a : a 2 L} be its
“symmetric” copy endowed with the reversed order. Consider the symmetric ordered structure L̃ := L [ ( L) \ { 0}, a
bipolar scale analogous to the real line where the zero acts as a neutral element and such that a + ( a) = 0 (symmetry).
In particular, ( a) = a.
The symmetric maximum 6 is intended to extend the maximum on L with 0 as neutral element, while fulfilling
symmetry. However, this symmetry requirement immediately entails that any extension 6 of the maximum operator
_ cannot be associative. To illustrate this point, let L = N and observe that (2 6 3) 6( 3) = 3 6( 3) = 0 whereas
2 6(3 6( 3)) = 2 6 0 = 2.
Nonetheless, Grabisch [3] showed that the “best” definition of 6 (see Theorem 1 below) is:
(
(|a| _ |b|) if b 6= a and |a| _ |b| = a or = b
a6b = 0 if b = a (1)
|a| _ |b| otherwise.
In other words, if b 6= a, then a 6 b returns the element that is the larger in absolute value among the two elements a
and b. Moreover, it is not difficult to see that 6 satisfies the following properties:
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
(C1) 6 coincides with the maximum on L2 ;
(C2) a 6( a) = 0 for every a 2 L̃;
(C3) (a 6 b) = ( a) 6( b) for every a, b 2 L̃.
Hence, 6 almost behaves like + on the real line, except for associativity a 6(b 6 c) = (a 6 b) 6 c, for every a, b, c 2 L̃.
For instance, we have:( 3 6 3) 6 1 = 0 6 1 = 1 but 3 6(3 6 1) = 3 6 3 = 0. However, it was shown in [3] that if
one requires that (C1), (C2) and (C3) hold, then (1) is the best possible definition for 6.
Theorem 1. [3, Prop. 5] No binary operation satisfying (C1), (C2), (C3) is associative on a larger domain than 6.
Further properties of 6 were presented in [3, 1, Prop. 5]. In particular, it was W shown that 6 V
is associative on an
n n
expression involving a1 , . . . , an 2 L̃, with |{i : ai 6= 0}| > 2, if and only if i=1 ai 6= i=1 ai . Sequences
fulfilling this condition were referred to as associative in [1].
To remove the ambiguity when evaluating 6 on nonassociative sequences, Grabisch [3] suggested ways of making 6
associative. The solution proposed was to define a rule of computation, that is, a systematic way of putting parentheses
so that the result is no longer ambiguous. Let us present here informally three of these rules1 that are rather natural:
(i) aggregate separately positive and negative terms, then compute their symmetric maximum. Taking the sequence
3, 2, 3, 1, 3, 2, 1, we obtain
6(3, 2, 3, 1, 3, 2, 1) = (3 6 2 6 1 6 1) 6(( 3) 6( 3) 6( 2))
= 3 6( 3) = 0.
(ii) aggregate first extremal opposite terms to cancel them, till there is no more extremal opposite terms. This
gives:
6(3, 2, 3, 1, 3, 2, 1) = (3 6( 3)) 6(2 6 1 6( 3) 6( 2) 6 1)
= 0 6( 3) = 3.
(iii) the same as above, but first aggregate these extremal opposite terms. This gives:
6(3, 2, 3, 1, 3, 2, 1) = (3 6(( 3) 6( 3))) 6(2 6( 2)) 6(1 6 1)
= (3 6( 3)) 6 0 6 1 = 0 6 1 = 1.
One sees that all results differ, and that many other rules can be created. In fact, it is more convenient to define a rule as
a systematic way of deleting terms in a sequence of numbers, so as to make it associative, provided the way of deleting
terms corresponds to some arrangement of parentheses. Indeed, the first rule consists in deleting all terms whenever
the sequence does not fulfill the condition of associativity. The second rule consists in deleting recursively all pairs
of extremal opposite elements, and the third rule deletes recursively all occurrences of extremal opposite elements.
However, one has to be careful that any systematic way of deleting elements making any sequence associative does not
necessarily correspond to an arrangement of parentheses. For example, deleting the maximal element 3 in the above
sequence makes it associative, however no arrangement of parentheses can produce this.
This framework based on rules of computation was formalized in [1], and we will recall it in the next section. We
will also recall equivalent, yet semantically rather different, quasi-orderings of rules, and briefly survey the main
characteristics of the resulting partially ordered set of (equivalent classes) of computation rules.
Denoting a computation rule by R, 6R is an unambiguously defined operator acting on any sequence of L̃, by first
making the sequence associative by means of R, and then computing the result by 6. Then, to any given computation
rule R corresponds an aggregation operator 6R , aggregating all ”numbers” of a sequence into a single number in L̃.
In the sequel, we only deal with countable sets L, so that L̃ can be thought to be Z. It follows that such a study is
related to the aggregation of integers, in particular to the so-called integer means or Z-means, see [4]. In the latter
work, it is shown that the decomposability property introduced by Kolmogoroff [5] imposes a very limitative form of
integer means, namely that the output depends only on the smallest and greatest entries. In [2], we have weakened the
decomposability property and shown that a whole family of operators 6R can serve as integer means.
The main objective of this paper is to study monotonic computation rules R, that is, leading to an aggregation operator
6R which is monotonically nondecreasing w.r.t. all terms of the sequence. This property is a basic requirement in
most fields of application, and this is why aggregation operators, defined on either real numbers or integers, are always
required to be nondecreasing (see, e.g., any kind of means, median, order statistics, etc.). As it will be shown, not all
computation rules are monotonic. The main result of this paper, shown in Section 3, is to give a characterization of the
set of monotonic computation rules.
1
These will be revisited in Section 2 and formally defined in the proposed language formalism of [1].
2 Rules of Computation
We now recall the formalism of [1]. As we will only consider countable sequences of elements of L̃, without loss
of generality, we may assume that L̃ = Z. In this way, elements of L̃⇤ are (finite) sequences of integers, denoted by
= ( i )i2I for some finite index set I, including the empty sequence ", i.e.,
⇣[ ⌘
L̃⇤ = (L̃)n [ {"}.
n2N
This convention will simplify our exposition and establish connections to the theory of integer means.
Also, as 6 is commutative, the order of symbols in the word does not matter, and we can consider the decreasing order
of the absolute values of the elements in the sequence (e.g., 5, 5, 5, 3, 2, 2, 1, 0). Since sequences are ordered, we
can consider the following convenient formalism for representing sequences. For an arbitrary sequence
= (n1 , . . . , n1 , n1 , . . . , n1 , . . . , nq , . . . , nq , nq , . . . , nq )
| {z } | {z } | {z } | {z }
p1 times m1 times pq times mq times
with n1 · · · nq , let ✓( ) = (n1 , . . . , nq ) be the sequence of absolute values (magnitudes) of integers in , and let
( ) = ((p1 , m1 ), . . . , (pq , mq )) be the sequence of pairs of numbers of occurrence of these integers. For instance, if
= (3, 3, 3, 2, 2, 2, 1, 1, 1, 1), then
✓( ) = (3, 2, 1); ( ) = ((2, 1), (1, 2)(4, 0)).
Let S denote the set of all integer sequences in this formalism, including the empty sequence, and let S0 be the subset
of all nonassociative sequences.
To facilitate the precise definition of rules of computation, we proposed [1] a language formalism over a 5-element
alphabet made of 5 elementary rules ⇢i : S ! S that act on in the following way:
(i) Elementary rule ⇢1 : if p1 > 1 and m1 > 0, then p1 is changed to p1 = 1;
(ii) Elementary rule ⇢2 : same as in (i) with p1 , m1 exchanged;
(iii) Elementary rule ⇢3 : if p1 > 0, m1 > 0, the pair (p1 , m1 ) is changed into (p1 c, m1 c), where c = p1 ^ m1 ;
(iv) Elementary rule ⇢4 : if p1 > 0, m1 > 0, and if p2 > 0, then p2 is changed into p2 = 0;
(v) Elementary rule ⇢5 : same as in (iv) with m2 replacing p2 .
Hence, elementary rules delete terms only in nonassociative sequences, and leave the associative ones invariant.
A (well-formed) computation rule R is a word built with the alphabet {⇢1 , . . . , ⇢5 }, i.e., R 2 L(⇢1 , . . . , ⇢5 ), such that
R( ) 2 S \ S0 for all 2 S. The set of (well-formed) computation rules is denoted by R. Examples of rules are
(words are read from left to right)
(i) h·i+ = (⇢4 ⇢5 )⇤ ⇢1 ⇢2 ⇢3 , that corresponds to first putting parentheses around all positive terms and all negative
terms, and then computing the symmetric maximum of the two results.
(ii) h·i0 = ⇢⇤3 , that corresponds to putting parentheses around each pair of maximal symmetric terms.
(iii) h·i= = (⇢1 ⇢2 ⇢3 )⇤ , that corresponds to putting parentheses around terms with the same absolute value and
sign, and then to putting parentheses around each each pair of maximal symmetric resulting terms.
It is shown in [1] that each computation rule R 2 R corresponds to an arrangement of parentheses together with a
permutation on the terms of sequences. Thus each R 2 R turns the symmetric maximum into an associative operation
6R : L̃⇤ ! L̃ defined by 6R = 6 R, since R( ) 2 S \ S0 for all 2 S 2 . Moreover, each computation rule has
the form R = T1 T2 · · · , where each Ti has the form !⇢↵
1 ⇢2 ⇢3 , with ! 2 L(⇢4 , ⇢5 ) and ↵, 2 {0, 1} (factorization
scheme)3
Now, to compute 6R ( ) one needs to delete symbols in the sequence ✓( ) exactly as they are deleted in ( ). This
entails an ordering of R that is discussed below.
Let R, R0 2 R and, for each sequence = (ai )i2I , let J ✓ I and J 0 ✓ I, be the sets of indices of the terms in
deleted by R and R0 , respectively. Then, we write R 6 R0 if for all sequences 2 S we have J ◆ J 0 . Clearly, it is
2
For convenience, we assume that 6R (") = 0 and 6R (a) = a, for every a 2 L̃
3
Here, ⇢0 = " and ⇢1 = ⇢.
reflexive and transitive, and thus it is a preorder. This induces an equivalence relation ⇠ defined as follows: R ⇠ R0 if
R 6 R0 and R0 6 R. The following proposition reassembles several results in [1], and provides equivalent definitions
of ⇠.
Proposition 1. Let R, R0 2 R. Then the following assertions are equivalent.
(i) R ⇠ R0 .
(ii) 6R = 6R0 .
(iii) Ker(6R ) = Ker(6R0 ), where Ker(6R ) denotes the kernel of 6R that is defined by
Ker(6R ) = { 2 S | 6R ( ) = 0}.
Furthermore, any two equivalent rules have exactly the same “ factorized irredundant form”. Recall that a rule R 2 R
is considered in factorized irredundant form (FIF) if the two following conditions are verified:
(i) Factorization: R can be factorized into a composition
R = T1 T2 · · · Ti · · · (2)
where each term has the form Ti = !i ⇢a1 i ⇢b2i ⇢3 , with !i 2 L({⇢4 , ⇢5 }) (possibly empty), and ai , bi 2 {0, 1}.
(ii) Simplification: Suppose that in (2) there exists j 2 N such that !j = !⇢⇤4 or !⇢⇤5 for some ! 2 L({⇢4 , ⇢5 }),
or that ⇢4 and ⇢5 alternate infinitely many times in !j . Let
k1 = min{j : !j = !⇢⇤4 or !⇢⇤5 }, and
k2 = min{j : ⇢4 and ⇢5 alternate infinitely many times in !j }.
• If k1 < k2 , then R ⇠ T1 · · · Tk1 .
a b
• Otherwise, k2 6 k1 , and R ⇠ T1 · · · Tk0 2 , where Tk0 2 = (⇢4 ⇢5 )⇤ ⇢1 k2 ⇢2k2 ⇢3 .
Observe that every non-terminal term Tj (i.e., of the form !⇢a1 ⇢b2 ⇢3 ) in a rule in FIF has a “certificate”.
Certificates can be defined recursively as follows. A certificate of non-terminal term T = !⇢a1 ⇢b2 ⇢3 is an element
of Ker(T ) such that no letter of T is left unused (unread or without deleting an element of ) when is deleted.
For instance, consider T = ⇢4 ⇢25 ⇢4 ⇢3 . Then = (1, 1)(2, 1)(0, 1) is a kernel element but not a certificate, while
= (1, 1)(2, 1)(1, 1) is a certificate.4 The definition is then recursively extended to rules in R/⇠ using factorization.
The structure of the poset R/⇠ of equivalence classes endowed with the partial order induced by 6 was investigated
in [1] and shown to be highly complex. To give an idea, the subposet R123 /⇠ of equivalence classes of rules
R 2 L(⇢1 , ⇢2 , ⇢3 ) has infinitely many maximal elements, and (R123 /⇠ , 6) (and thus (R/⇠ , 6)) embeds the powerset
(2N , ✓) of natural numbers, and hence it is of continuum cardinality. For further results on R/⇠ , see [1].
The complex structure of (R/⇠ , 6) gives little hope to obtain a complete description of this poset. In addition to
considering restrictions on the syntax of computation rules, another approach to provide local descriptions is to consider
computation rules with certain desirable properties. One of such properties is monotonicity which is particularly
relevant in applied mathematics, especially, in decision making and aggregation theory. In the next section we provide
the explicit description of monotonic computation rules in terms of their factorized irredundant form (FIF).
3 Monotonic computation rules
In this section we aim to describe those computation rules that are monotonic. Recall that a rule R 2 R is monotonic
if 6R (a1 , . . . , an ) 6 6R (a01 , . . . , a0n ), whenever ai 6 a0i for every n 2 N and i = 1, . . . , n. For instance, it is not
difficult to see that both h·i0 and h·i+ are monotonic, however, h·i= is not:
6h·i= (5, 5, 5, 4, 3) = 4 whereas 6h·i= (5, 5, 4, 4, 3) = 3.
In order to study monotonicity, first observe the following facts.
(i) 6R is monotonic for every rule R on S \ S0 . Hence, we can consider only sequences in S0 .
4
Note that a certificate exists if and only if ! neither contains ⇢⇤4 , ⇢⇤5 nor (⇢4 ⇢5 )⇤ .
(ii) It is sufficient to study the effect of increasing one element of the sequence . If we increase nk to n > n1 ,
then the sequence becomes associative, and the value of 6R is n. Hence, it is sufficient to consider an increase
to any value at most n1 .
Lemma 1. Let 2 S0 . Then 6R is monotonic w.r.t. any element n1 or n1 of the sequence, for any rule
R = T 1 T 2 · · · with T 1 = !⇢3 .
Proof. Suppose that an element n1 is changed to n01 > n1 . Then the new sequence 0 becomes associative and
6R ( 0 ) = n01 > 6R ( ). Suppose now that an element n1 is changed to n1 + ✏ n2 . Then (p1 , m1 ) is changed
to (p1 , m1 1), which can only increase the result of 6R , as ⇢1 , ⇢2 are not present in T 1 .
Let us start with computation rules with a single term.
Lemma 2. If R has the form (⇢4 ⇢5 )⇤ ⇢a1 ⇢b2 ⇢3 then 6R is monotonic.
Proof. Let 2 S0 . After the application of (⇢4 ⇢5 )⇤ only the first term (p1 , m1 ) remains, so that it is enough to study
the effect of increasing ±n1 . If n1 is increased to n01 , then 6R ( 0 ) = n01 , and if n1 is increased, this can only increase
the result of 6R .
Lemma 3. Let R 2 R be in FIF.
(i) Suppose that R has the form !⇢a1 ⇢b2 ⇢3 for ! = ! 0 ⇢⇤4 with ! 0 2 L(⇢4 , ⇢5 ). Then R is monotonic if and only if
(a, b) = (a, 0), for a 2 {0, 1}, and ! 0 = ".
(ii) Suppose that R has the form !⇢a1 ⇢b2 ⇢3 for ! = ! 0 ⇢⇤5 with ! 0 2 L(⇢4 , ⇢5 ) . Then R is monotonic if and only if
(a, b) = (0, b), for b 2 {0, 1}, and ! 0 = ".
Proof. We show that (i) holds; the proof of (ii) is analogous. To see that the condition is necessary, suppose that
(a, b) = (a, 1), where a 2 {0, 1}. Consider the sequence
0
1 = (1, 2) ! 0 ,
where !0 is a certificate of ! 0 and 0 a sequence such that the difference between the smallest absolute value of !0
and the greatest absolute value of 0 is at least 2. Then 6R ( 1 ) = n for some n in 0 if it exists, or 6R ( 1 ) = 0.
Consider now the sequence
0
2 = (1, 1) ! 0 (0, 1) ,
obtained from by increasing n1 to n greater than all n in !0 and smaller than all n in 0 . Clearly, 1 < 2
0
but 6R ( 2 ) = n0 < 6R ( 1 ).
To see that we must have ! 0 = ", suppose to the contrary that ! 0 6= ". Hence, ! 0 has the form ! 0 = ! 00 ⇢5 , otherwise we
would have ! 0 ⇢⇤4 = ⇢⇤4 . Consider the sequences
= (1, 1) !00 (0, 1)(1, 0) < (1, 1) !00 (1, 0)(0, 1) = 0
where 0 has been obtained from by increasing the last but one element n to n0 s.t. n0 < n00 , with n00 the last
element in . Then 6R ( ) = 0 > 6R ( 0 ) = n0 , which contradicts the fact that R is monotonic. Hence, ! 0 = ".
To prove sufficiency, consider the case (a, b) = (0, 0) (the case (a, b) = (1, 0) is similar). Any sequence has the
form = (p1 , m1 )(p2 , 0) · · · (pt , 0) 0 with t 0. Note that (a) if p1 > m1 , then 6R ( ) = n1 , (b) if p1 < m1 , then
6R ( ) = n1 (smallest value), and (c) if p1 = m1 , 6R ( ) = n if it exists in 0 , or 6R ( ) = 0. It is not difficult to
check that, in each case, any increase in can only result in an increase of 6R ( ).
We now extend our study to rules made of several terms, and we will make use of the two following auxiliary results to
simplify our search for nonmonotonic rules.
Lemma 4. Suppose that 6R is not monotonic, and let T 2 L(⇢1 , . . . , ⇢5 ) such that T R 2 R be in FIF. Then 6T R also
is not monotonic.
Proof. Since T R 2 R is in FIF, T = T1 T2 · · · Ti · · · is finite and each term Tj has a certificate j. Hence, the
composition = 1 2 · · · i · · · is a certificate of T .
Suppose that 6R is not monotonic, and let 0 and 00 be sequences such that 0 < 00 and 6R ( 0 ) > 6R ( 00 ). Consider
the two composite sequences 0 and 00 . Clearly, 0 < 00 but
6T R ( 0 ) = 6R ( 0 ) > 6R ( 00 ) = 6T R ( 00 ).
In other words, 6T R is not monotone.
Lemma 5. Let R 2 R be in FIF, and let T = ⇢k3 R with k 1. Then, 6R is monotonic if and only if 6T is monotonic.
Proof. From Lemma 4 it follows that the condition is sufficient. Conversely, suppose that 6R is monotonic. It suffices
to prove that 6⇢3 R is monotonic and apply k times the result. Consider any sequence = (p1 , m1 ) 1 2 S0 . By
Lemma 1, 6⇢3 R is monotonic w.r.t. ±n1 . Now, consider 0 obtained by increasing any element in 1 . Then
⇢
0 (p1 , m1 ) 10 with 10 > 1
= 0
(p1 + 1, m1 ) 1
In the first case, 6⇢3 R ( 0 ) = 6⇢3 R ( ) when p1 6= m1 , otherwise 6⇢3 R ( 0 ) = 6R ( 10 ) 6R ( 1 ) since R is
monotonic.
In the second case, we have 6⇢3 R ( 0 ) > 6⇢3 R ( ) if p1 = m1 or p1 = m1 1, otherwise 6⇢3 R ( 0 ) = 6⇢3 R ( ).
Lemma 6. Let R = T 1 T 2 · · · be in FIF where T i = !i ⇢a1 i ⇢b2i ⇢3 . If there exists k such that
• (ak , bk ) = (1, 0) and !k 6= ⇢⇤4 , (⇢4 ⇢5 )⇤ ,
• (ak , bk ) = (0, 1) and !k 6= ⇢⇤5 , (⇢4 ⇢5 )⇤ , or
• (ak , bk ) = (1, 1) and !k 6= ⇢⇤4 , ⇢⇤5 , (⇢4 ⇢5 )⇤ ,
then 6R is not monotonic.
Proof. Assuming that R is in FIF, by Lemma 4, we may assume that k = 1.
• Suppose that (a1 , b1 ) = (1, 0) and !1 6= ⇢⇤4 , (⇢4 ⇢5 )⇤ . Consider the sequences
|!1 |⇢4 |!1 |⇢4
1 = (1, 1)(1, 0)(1, 0) and 2 = (2, 1)(1, 0)
obtained from 1 by augmenting n|!1 |⇢4 +2 to n1 , where |!1 |⇢4 indicates the number of occurrences of ⇢4 in
!1 . Although 1 < 2 we have
6R ( 1 ) = n|!1 |⇢4 +2 > 0 = 6R ( 2 ),
and thus 6R is not monotonic.
• Suppose that (a1 , b1 ) = (0, 1) and !1 6= ⇢⇤5 , (⇢4 ⇢5 )⇤ . Consider the sequences
|!1 |⇢5 |!1 |⇢5
1 = (1, 2)(0, 1) and 2 = (1, 1)(0, 1) (0, 1),
obtained from 1 by increasing the value n1 to n|!1 |⇢5 +2 . Clearly, 1 < 2 but 6R ( 1 ) = 0 >
n|!1 |⇢5 +2 = 6R ( 2 ), and thus 6R is not monotonic.
• The remaining case (a1 , b1 ) = (1, 1) and !1 6= ⇢⇤4 , ⇢⇤5 , (⇢4 ⇢5 )⇤ is dealt with similarly.
We now consider the case where (ai , bi ) = (0, 0) in each term T i = !i ⇢a1 i ⇢b2i ⇢3 .
Lemma 7. Suppose R = T 1 T 2 · · · is in FIF, and that no term contains ⇢1 nor ⇢2 . If there is k 1 such that !k in T k
is of the AFT type or equal to ⇢↵
4 or ⇢5 , then 6R is not monotonic.
Proof. By Lemma 4, it suffices to consider the case k = 1. Suppose first that R = !⇢3 R0 with ! of the AFT type, say
! = ⇢↵ 1 1 ↵t
4 ⇢5 · · · ⇢4 ⇢5 . Consider the sequence
t
= (1, 1)(1, 0) 1 (0, 1)⇠1 · · · (1, 0) t (0, 1)⇠t (1, 0)(1, 0).5
Clearly, 6R ( ) = nt+2 . Now let us increase the term with value nt+2 to nj , where j is the first index such that j = 1,
so that we obtain the sequence 0 . Clearly, we have < 0 but 6R ( ) = nt+2 > nt+3 = 6R ( 0 ).
Now, w.l.o.g. suppose that ! = ⇢↵
4 with ! 6= ⇢4 ; the other case ! = ⇢5 with ! 6= ⇢5 is dealt with similarly. Consider
⇤ ⇤
= (1, 1)(1, 0) (1, 0)(1, 0) and obtained from by increasing the value of n↵+2 to n2 , i.e.,
↵ 0
= (1, 1)(2, 0)(1, 0)↵ 1 (1, 0).
In this case, we get 6R ( ) = n↵+2 > n↵+3 = 6R ( 0 ).
In both cases, we get that 6R is not monotonic.
5
Here i = 1 if ↵i > 0, otherwise i = 0. Similarly, ⇠i = 1 if i > 0, otherwise ⇠i = 0.
We can now provide a complete description of monotonic rules.
Theorem 2. Let R 2 R be in FIF. Then 6R is monotonic if and only if either
(i) R = ⇢⇤3 , or
(ii) R = ⇢k3 T , where T = !⇢a1 ⇢b2 ⇢3 satisfies the following conditions
• if (a, b) = (1, 0), then ! = ⇢⇤4 or (⇢4 ⇢5 )⇤ ,
• if (a, b) = (0, 1), then ! = ⇢⇤5 or (⇢4 ⇢5 )⇤ ,
• if (a, b) = (1, 1), then ! = (⇢4 ⇢5 )⇤ ,
• if (a, b) = (0, 0), then ! = ⇢⇤4 , ⇢⇤5 , (⇢4 , ⇢5 )⇤ .
Proof. Let us prove that all rules in (i) and (ii) are monotonic. It was already established that 6⇢⇤3 = h·i0 is monotonic.
As for (ii), by using Lemma 5, it suffices to prove monotonicity for R = T , which is obtained by Lemmas 2 and 3.
It remains to prove that no other rule is monotonic. As rules are in FIF, no term can exist after T . Moreover, by
0 0
Lemmas 6 and 7, no term of the form T 0 = ! 0 ⇢a1 ⇢b2 ⇢3 with ! 0 2 L(⇢4 , ⇢5 ) finite can occur before T or before ⇢k3 .
Furthermore, by Lemma 3, it is not possible to add a finite ! 0 2 L(⇢4 , ⇢5 ) before T . Thus, every monotonic rule must
be of one of the stated forms, and the proof of Theorem 2 is now complete.
References
[1] Miguel Couceiro and Michel Grabisch. On the poset of computation rules for nonassociative calculus. Order,
30(1):269–288, 2013.
[2] Miguel Couceiro and Michel Grabisch. On integer-valued means and the symmetric maximum. Aequationes
Mathematicae, 91(2):353–371, 2017.
[3] Michel Grabisch. The Möbius transform on symmetric ordered structures and its application to capacities on finite
sets. Discrete Mathematics, 287(1-3):17–34, 2004.
[4] C. D. Bennett, W. C. Holland, and G. J. Székely. Integer valued means. Aequationes Mathematicae, 88:137–149,
2014.
[5] A. Kolmogoroff. Sur la notion de moyenne. Atti delle Reale Accademia Nazionale dei Lincei Mem. Cl. Sci. Fis.
Mat. Natur. Sez., 12:323–343, 1930.