PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 95 (109) (2014), 111–117 DOI: 10.2298/PIM1409111G

BINARY RELATIONS AND ALGEBRAS ON MULTISETS

Silvia Ghilezan, Jovanka Pantović, and Gradimir Vojvodić

Communicated by Žarko Mijajlović

Abstract. Contrary to the notion of a set or a tuple, a multiset is an unordered collection of elements which do not need to be different. As multisets are already widely used in combinatorics and computer science, the aim of this paper is to get on track to algebraic multiset theory. We consider generalizations of known results that hold for equivalence and order relations on sets and get several properties that are specific to multisets. Furthermore, we exemplify the novelty that brings this concept by showing that multisets are suitable to represent partial orders. Finally, after introducing the notion of an algebra on multisets, we prove that two algebras on multisets, whose root algebras are isomorphic, are in general not isomorphic.

1. Introduction

Besides having an object representing an unordered collection of distinct elements, which is a set, and an object representing an ordered collection of (not necessarily distinct) elements, which is a tuple, a fundamental object to complete this list would be the multiset, an unordered collection of elements. An element can belong to a multiset more than once, but its multiplicity has to be finite. Several names have been introduced for such an object: bag, heap, bunch, weighted set, etc.

The lack of the notion of a multiset in mathematics appears to be groundless since it is irreplaceable by known objects, e.g., the multiset of prime factors of a number.

While these objects are used frequently in many areas of computer science, engineering and philosophy, there is still no coherent fundamental theory that describes their appearance and behavior. The application goes back to the ancient

2010 Mathematics Subject Classification: Primary 08A99; Secondary 03C99. Key words and phrases: multiset, bag. Partly supported by the Serbian Ministry of Education and Science (projects ON174026 and

III44006).

times when numbers were represented as unordered collections of tally marks. However, the first time they were mentioned formally was by Dedekind [3] in his wellknown essay “The nature and meaning of numbers", noticing that “In this way we reach the notion, very useful in many cases, of systems in which every element is endowed with a certain frequency-number which indicates how often it is to be reckoned as an element of the system." Later on, mathematics has been developing on classical set theory and the necessity for the introduction of the notion of a multiset appeared in applications a few decades ago. Multisets were used for proving termination properties and in some search and sort algorithms [8], Petri nets [9], relational data bases [11], automata theory [4], software verification and interactive theorem proving [10], etc.

For example, in concurrency theory, the replication of a process !P is structurally equivalent with the paralell composition of the process and its replication P |!P. This means that !P is a parallel composition of infinite number of copies of P and one can represent it as the multiset containg infinite number of copies of P, as it was done in [5]. A deep survey and axiomatic introduction of multisets can be found in the work of Blizard [1, 2]. More on relations and functions can be found in [6].

The paper is organized as follows. In order to make the presentation selfcontained, we recall some basic notions in Section 2. For references, we refer the reader to [1] and [6]. In Section 3, we give a characterization of equivalence relations on multisets and give a property of equivalence relations on a set that does not hold for equivalence relations on a multiset. The main results are the content of Section 4, where we show that it is possible to represent algebraic properties by multisets. Section 5 introduces the notion of an operation and an algebra on a multiset, as well as subalgebras and homomorphisms of algebras on multisets. We prove a property specific to multisets, namely, that a necessary but not sufficient condition for two algebras on a multiset to be isomorphic is that their root algebras are isomorphic.

2. Preliminaries and basic definitions

A multiset is a collection of elements that may appear more than once and the number of occurrences of an element in a multiset is a unique positive integer. For a multiset M the root set of M, denoted by M^{∗}, is the set containing all distinct elements from M. A multiset is completely described by its root set and the number of occurrences in the multiset of each element of the root set.

For a positive integer n, if M contains n copies of x, we write x ∈^{n} M. The multiplicity of x in M will be denoted by |x|_{M}. For a multiset M with |x_{1}|_{M} = n_{1}, |x_{2}|_{M} = n_{2} and so on, we usually write M = [x_{1}, x_{2}, …]_{n_{1} ,n_{2} ,...} or repeat all the occurrences of elements in square brackets. The cardinality of the multiset [x_{1}, x_{2}, …, x_{m}]_{n_{1} ,n_{2} ,...,n_{m}} , having a finite root set, is equal to n_{1} + n_{2} + ⋯+ n_{m}.

Let M and N be non-void multisets and l, m, n non-negative integers. The intersection of M and N is the multiset denoted by M ∩ N such that x ∈^{l} M ∩ N iff x ∈^{m} M and x ∈^{n} N and l = min{m, n}. The union of M and N is the multiset denoted by M ∪N such that x ∈^{l} M ∪N iff x ∈^{m} M and x ∈^{n} N and l = max{m, n}. We say that M is a multisubset of N, written as M ⊆ N, iff x ∈^{m} M implies x ∈^{n} N and m ⩽ n. They are equal if x ∈^{m} M iff x ∈^{m} N. The n-th Cartesian power of M is defined by: M^{0} = {∅}, M^{1} = M and

M^{n} = ⋃_{x_{i} ∈^{m_{i}} M, 1⩽i⩽n} [(x_{1}, …, x_{n})]_{m_{1} ·m_{2} ·...·m_{n}} , for n ⩾ 2.

The n-ary relation α on M is an arbitrary subset of M^{n} satisfying:

(x_{1}, …, x_{n}) ∈^{l_{1} ·...·l_{n}} α ∧ x_{1} ∈^{m_{1}} M ∧ … ∧ x_{n} ∈^{m_{n}} M

for some 0 < l_{i} ⩽ m_{i}, i ∈ {1, …, n}, where we also take into account the multiplicity of each coordinate and write (x_{1}, …, x_{n}) ∈^{(l_{1} ,...,l_{n} )} α. For a relation α on a multiset M, we denote by α^{∗} the relation that contains all distinct elements from α. Since for an element of a relation we specify the multiplicity of each coordinate, operations on relations also depend on them.

Let α and β be n-ary relations on a multiset M.

(a) α ⊆ β iff (x_{1}, …, x_{n}) ∈^{(m_{1} ,...,m_{n} )} α implies (x_{1}, …, x_{n}) ∈^{(k_{1} ,...,k_{n} )} β and

m_{i} ⩽ k_{i} for each i ∈ {1, …, n}.

(b) (x_{1}, …, x_{n}) ∈^{(l_{1} ,...,l_{n} )} α ∩ β iff (x_{1}, …, x_{n}) ∈^{(m_{1} ,...,m_{n} )} α and (x_{1}, …,

x_{n}) ∈^{(k_{1} ,...,k_{n} )} β and l_{i} = min{m_{i}, k_{i}}, 1 ⩽ i ⩽ n.

We define the inverse relation α^{−1} of a binary relation α as follows:

(x, y) ∈^{(k,l)} α^{−1} iff (y, x) ∈^{(l,k)} α.

and we say that (R) α is reflexive on M iff (∀x ∈^{m} M) (x, x) ∈^{(m,m)} ∈ α, (S) α is symmetric on M iff (∀x, y ∈ M^{∗}) (x, y) ∈^{(k,l)} α ⇒ (y, x) ∈^{(l,k)} α, (A) α is antisymmetric on M iff

(∀x, y, z ∈ M^{∗})((x, y) ∈^{(k,l)} α ∧ (y, x) ∈^{(l,k)} α ⇒ x = y ∧ l = k),

(T) α is transitive on M iff

(∀x, y, z ∈ M^{∗})((x, y) ∈^{(k,l)} α ∧ (y, z) ∈^{(l,m)} α ⇒ (x, z) ∈^{(k,m)} α).

3. On equivalence and order relations

Concepts of equivalence and order relations are powerful descriptive tools widely applied both in mathematics and computer science. We will point out similarities and differences of these concepts for sets and multisets. Proofs that are straightforward are omitted. As usual, a binary relation α on a multiset M is said to be an equivalence relation on M iff α is a reflexive, symmetric and transitive relation on M. A binary relation α on a multiset M is said to be an order relation on M iff α is a reflexive, antisymmetric and transitive relation on M. The following theorem gives a characterization of equivalence relations on a multiset, providing necessary and sufficient conditions for a relation on a multiset, whose root relation is an equivalence, to be an equivalence relation too.

Theorem 3.1. Let M be a non-void multiset with the root set M^{∗}. α is an equivalence relation on M iff

(a) for all x, y ∈ M^{∗} it holds that (x, y) ∈^{(k,l)} α implies x ∈^{k} M and y ∈^{l} M.

(b) α^{∗} is an equivalence relation on M^{∗}.

Proof. Even-though the proof is straightforward, we do not omit it since we find this theorem to be of fundamental importance for the characterization of multiset partitioning.

(⇒) (a) From (x, y) ∈^{(k,l)} α, since α is symmetric, it follows that (y, x) ∈^{(l,k)} α. Hence, since α is transitive, we have that (x, x) ∈^{(k,k)} α and (y, y) ∈^{(l,l)} α. By reflexivity of α we conclude that x ∈^{k} M and y ∈^{l} M.

(b) (R) If α is reflexive, then (x, x) ∈^{(m,m)} α for any x ∈^{m} M. Therefore, (x, x) ∈ α^{∗} for each x ∈ M^{∗}.

(S) From (x, y) ∈ α^{∗} and x ∈^{k} M, y ∈^{l} M, by the definition of the root relation and (a), we have that (x, y) ∈^{(k,l)} α. Since α is symmetric, it follows that (y, x) ∈^{(l,k)} α, and so (y, x) ∈ α^{∗}.

(T) Let us assume that (x, y) ∈ α^{∗}, (y, z) ∈ α^{∗}, x ∈^{k} M, y ∈^{l} M and z ∈^{m} M. From the definition of the root relation and (a) we conclude that (x, y)^{(k,l)} ∈ α and (y, z) ∈^{(l,m)} α. By transitivity of α, it holds that (x, z) ∈^{(k,m)} α and therefore (x, z) ∈ α^{∗}.

(⇐) (R) If α^{∗} is reflexive then (x, x) ∈ α^{∗} for every x ∈ M^{∗}. Therefore, (x,

x) ∈^{(m′,m′′)} α for some positive integers m′, m′′. From (b) it holds that x ∈^{m} M for m = m′ = m′′. So, (x, x) ∈^{(m,m)} α for every x ∈^{m} M.

(S) If (x, y) ∈^{(k,l)} α, then (x, y) ∈ α^{∗} and from symmetry of α^{∗} also (y, x) ∈ α^{∗}. Then, (y, x) ∈^{(l′,k′)} α for some positive integers l′, k′ which by (a) gives l = l′ and k = k′.

(T) Let us suppose that (x, y) ∈^{(k,l)} α and (y, z) ∈^{(l,m)} α. It follows that (x, y) ∈ α^{∗}, (y, z) ∈ α^{∗}, x ∈^{k} M, y ∈^{l} M and z ∈^{m} M. By transitivity of α^{∗}, it holds that (x, z) ∈ α^{∗}. We can conclude, by applying (a), that (x, z) ∈^{(k,m)} α. □

We will show that for a reflexive and transitive relation α on a multiset, the relation α ∩ α^{−1} is in general not an equivalence relation, contrary to what holds for relations on sets.

Theorem 3.2. Let M be a non-void multiset and α a reflexive and transitive relation on M. Then, α ∩ α^{−1} is a reflexive and symmetric relation on M.

Proof. (R) Let x ∈^{m} M. Since α is reflexive, (x, x) ∈^{(m,m)} α and (x, x) ∈^{(m,m)} α^{−1} implies (x, x) ∈^{(m,m)} α ∩ α^{−1} .

(S) If (x, y) ∈^{(k,l)} α ∩ α^{−1} then (x, y) ∈^{(k′,l′)} α and (x, y) ∈^{(k′′,l′′)} α^{−1} , where k = min{k′, k′′} and l = min{l′, l′′}. Therefore, (y, x) ∈^{(l′,k′)} α^{−1} and (y, x) ∈^{(l′′,k′′)} α, and hence so (y, x) ∈^{(l,k)} α ∩ α^{−1} . □

In contrast to the well-known property that holds for sets, we show now that α ∩ α^{−1} is not necessarilly an equivalence relation, assuming that α is a reflexive and transitive relation.

Example 3.1. Let α = [(x, x), (y, y), (x, y), (y, x)]_{(5,5),(3,3),(2,3),(1,5)} be a relation on M = [x, y]_{5,3}. Hence, α^{−1} = [(x, x), (y, y), (y, x), (x, y)]_{(5,5),(3,3),(3,2),(5,1)} and α ∩ α^{−1} = [(x, x), (y, y), (x, y), (y, x)]_{(5,5),(3,3),(2,1),(1,2)} . It is not transitive, since (x, y) ∈^{(2,1)} α ∩ α^{−1} and (y, x) ∈^{(1,2)} α ∩ α^{−1} , but it does not hold that (x, x) ∈^{(2,2)} α ∩ α^{−1} .

4. Partial orders described by multisets

Let A be a finite set and let G = {G_{1}, …, G_{n}} be a set of subsets of A ordered by set inclusion. We will show that some partial orders can be represented by the additive union M_{G} = G_{1} ⨄ G_{2} ⨄ …⨄ G_{n} of all the elements of G.

In the following Lemma, M_{G} completely describes a chain, i.e., multiplicities of elements in the multiset M_{G} determine the depth to which elements belong.

Lemma 4.1. Let G be such that G_{n} ⊆ G_{n−1} ⊆ … ⊆ G_{1} and M_{G} = G_{1} ⨄ G_{2} ⨄ … ⨄ G_{n}. Then, for each i ∈ {1, …, n}, x ∈^{i} M_{G} if and only if x ∈ G_{i} and x ∉ G_{i+1} .

Proof. The proof follows directly from the property of the total order that x ∈ G_{i} implies that x ∈ G_{j} for each j ∈ {1, …, i − 1}. □

Theorem 4.1. Let A = {e, a, …, (p^{k} − 1)a} be a cyclic group of order p^{k}, for a prime p and a positive integer k. Let M_{G} be defined by: x ∈^{j+1} M_{G} if there is j ∈ {0, …, k} such that x is generated by p^{j} a and x is not generated by p^{j+1} a. M_{G} = G_{1}⊎ G_{2}⊎⋯ ⊎ G_{k+1} for a chain {G_{1}, …, G_{k+1} } iff the chain is the subgroup lattice of the cyclic group of order p^{k}.

Proof. It is well-known that a subgroup lattice is a chain of length k + 1 if and only if the group is cyclic of order p^{k}. Each subgroup is generated by p^{j} a, for some 0 ⩽ j ⩽ k. □

Theorem 4.2. For |A| = n, let G_{1} = {e} be the least and G_{n} = A the greatest element of (G, ⊆) and let M_{G} = G_{1} ⨄ G_{2} ⨄ …⨄ G_{n}. If e ∈^{n} M_{G} and x ∈^{2} M_{G}, x ≠ e, then G_{i} ⊈ G_{j} and G_{j} ⊈ G_{i}, for all i, j ∈ {2, …, n − 1}.

Proof. Consider the partition of M_{G} onto subsets from G. Since e ∈^{n} M_{G} there are at least n such subsets, each containing e. Since G_{1} is the least element, there are exactly n such subsets. The greatest element G_{n} contains all the elements from A, so the remaining n − 2 elements have to be assigned to other n − 2 subsets. In order to obtain n − 2 subsets, they have to be pairwise distinct, each having the cardinality 2. □

5. Algebras on multisets

We introduce the concept of an algebra on a multiset, which will bring us to the study of the properties that are common to all such algebras and also to those that make distinctions between them.

Definition 5.1. Let M be a non-void multiset with the root set M^{∗}, n a positive integer and f^{∗} an n-ary operation on M^{∗}. The n-ary operation on the multiset M determined by f^{∗} is the n-ary relation f defined by: if (x_{1}, …, x_{n}, y) ∈ f^{∗} and (x_{1}, …, x_{n}, y) ∈^{(m_{1} ,...,m_{n} ,l)} M^{n+1} , then (x_{1}, …, x_{n}, y) ∈^{(m_{1} ,...,m_{n} ,l)} f.

Notice that the previous definition can be extended to the case n = 0, which defines the nullary operation f : {∅} → M. If f^{∗}(∅) = a and a ∈^{m} M then f(∅) = [a]_{m}. We usually avoid nullary operations and replace them with unary operations with constant values.

The number n is called the arity of f and denoted by ar(f).

Definition 5.2. An algebra on a multiset is an ordered pair (M; F), where M is an arbitrary non-void multiset and F is a set of finitary operations on M. The set M is called the underlying multiset of M.

If F = {f_{1}, …, f_{n}}, we write (M; f_{1}, …, f_{n}), or (M; {f_{i} : i ∈ I}) for a cer-

tain index set I. We will denote the corresponding set {f_{1}^{∗}, …, f_{n}^{∗}} of operations on the root set by F^{∗}. As usual, the type of the algebra M is the sequence (ar(f_{1}), …, ar(f_{n})) of the arities of the fundamental operations. For the algebra (M; F) we say that its root algebra is (M^{∗}; F^{∗}).

Definition 5.3. Let (M_{A}; F_{A}) and (M_{B}; F_{B}) be two algebras of the same type and F_{A} = {f_{i} : i ∈ I} and F_{B} = {g_{i} : i ∈ I} with ar(f_{i}) = ar(g_{i}) = n_{i} for every i ∈ I. We say that the mapping φ from M_{A} to M_{B} is a homomorphism from M_{A} into M_{B} if φ^{∗} is a homomorphism from M_{A}^{∗} into M_{B}^{∗}, for the corresponding algebras (M_{A}^{∗}; F_{A}^{∗}) and (M_{B}^{∗}; F_{B}^{∗}).

If φ is a bijection from M_{A} to M_{B}, then φ is said to be an isomorphism and we write (M_{A}; F_{A}) ≅ (M_{B}; F_{B}). Hickman [7] has shown that the Schröder-Bernstein theorem does not hold for multisets. We show that there are non-isomorphic algebras on multisets for which the corresponding algebras on their root sets are isomorphic.

Theorem 5.1. Let (A; F_{A}) and (M_{B}; F_{B}) be algebras on multisets. The necessary, but not sufficient, condition for (M_{A}; F_{A}) ≅ (M_{B}; F_{B}) is (M_{A}^{∗}, F_{A}^{∗}) ≅ (M_{B}^{∗}, F_{B}^{∗}).

Proof. If (M_{A}; F_{A}) ≅ (M_{B}; F_{B}) it follows directly from the definition that (M_{A}^{∗}; F_{A}^{∗}) ≅ (M_{B}^{∗}, F_{B}^{∗}). We shall prove that the reverse is not true. Let M_{A}^{∗} = {a_{1}, a_{2}, …}, M_{B}^{∗} = {b_{1}, b_{2}, …} and let us define unary operations p^{∗} on M_{A}^{∗} and q^{∗} on M_{B}^{∗} as follows:

p^{∗}(a_{i}) = a_{i+1} and q^{∗}(b_{i}) = b_{i+1} for every i ∈ {1, 2, …}.

Let us consider algebras (M_{A}; p) and (M_{B}; q), where

M_{A} = [a_{1}, a_{2}, …, a_{k}, …]_{{2,4,...,2k,...}} and M_{B} = [b_{1}, b_{2}, …, b_{l}, …]_{{1,3,...,2l−1 ,...}} .

We will show that the function f^{∗} : M_{A}^{∗} → M_{B}^{∗} defined by f^{∗}(a_{i}) = b_{i}, i ∈ {1, 2, …}, is an isomorphism from (M_{A}^{∗}, p^{∗}) to (M_{B}^{∗}, q^{∗}). It is obvious that f^{∗} is a bijection from M_{A}^{∗} to M_{B}^{∗} and it holds

f^{∗}(p^{∗}(a_{i})) = f^{∗}(a_{i+1} ) = b_{i+1} = q^{∗}(b_{i}) = q^{∗}(f^{∗}(a_{i})).

However, there is no bijection between the multiset M_{A} and M_{B}, since |x|_{M_{A}} ≠ |y|_{M_{B}} for all x ∈ M_{A}^{∗} and y ∈ M_{B}^{∗} (see [7]). □

6. Conclusion and future work

The main aim of this study was a comparison of some results that hold on sets with the corresponding extensions on multisets. Some results can be extended to the multiset case, whereas there are characteristics that are specific for multisets. In the future work we will put emphasis on the investigation of multialgebra properties. An interesting problem would be to study the possibilities to derive properties of a structure of algebra from a given multiset, as it was done in the present paper for the subgroup lattice of the cyclic group of order p^{k}. If we are given a multiset, the question is to determine the necessary and sufficient conditions for a multiset to have a unique partition, corresponding to a specific characterization of an algebra.

References

1. W. D. Blizard, Multiset theory, Notre Dame J. Formal Logic 30 (1989), 36–66.

2. , Dedekind multisets and function shells, Theor. Comput. Sci. 110 (1993), 79–98.

3. R. Dedekind, Essays in the Theory of Numbers, 1901.

4. S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974.

5. J. Engelfriet, A Multiset Semantics for the pi-Calculus with Replication, CONCUR 1993, Lect. Notes Comput. Sci. 715, 1993, 7–21.

6. K. P. Girish, S. J. John, Relations and functions in multiset context, Inf. Sci. 179 (2009), 758–768.

7. J. L. Hickman, A note on the concept of multiset, Bull. Aust. Math. Soc. 22 (1980), 211–217.

8. D. E. Knuth, The Art of Computer Programming, Volume III: Sorting and Searching, Addison-Wesley, 1973.

9. J. L. Peterson, Petri Net Theory and the Modelling of Systems, Englewood Cliffs, N.J.: Prentice-Hall, 1981.

10. R. Piskac, V. Kuncak, Decision procedures for multisets with cardinality constraints, VM-CAI’08 Proc. 9th Int. Conf. on Verification, Model Checking, and Abstract Interpretation, 2008, 218–232.

11. R. R. Yager, On the theory of bags, Int. J. Gen. Syst. 13 (1986), 23–37.

Faculty of Technical Sciences (Received 13 12 2012) University of Novi Sad (Revised 25 03 2013) Novi Sad, Serbia

   gsilvia@uns.ac.rs
   pantovic@uns.ac.rs

Faculty of Science University of Novi Sad Novi Sad, Serbia

   vojvodic@dmi.uns.ac.rs