Authors:

• Andrei Alexandru, Institute of Computer Science, Romanian Academy, Iasi Branch

• Gabriel Ciobanu, Institute of Computer Science, Romanian Academy, Iasi Branch

Abstract:

A multiset over X is a function from a set X to the set N of positive integers, indicating that each element of X has associated a positive multiplicity. This notion was generalized by introducing the hybrid sets which also allow negative multiplicities. Since the set of all integers are denoted by Z, the hybrid sets can be named Z-multisets. The set Z of integers is a group under the operation of addition. Starting from this observation, we introduce a generalization of the hybrid sets by defining the group-valued multisets. These multisets over a set X are functions from X to an arbitrary group G, ensuring an inverse for each multiplicity (not necessarily a number) of the elements of X (together with other features derived from the group properties). We denote them by G-multisets. In particular, Z-multisets are G-multisets; in general, Z can be replaced by any group G, and this aspect allows to get deeper relationships and correlations among the quantitative attributes (multiplicities) for elements of X, useful for various models and optimizations (e.g., in economy). For instance, whenever we use elements of X having certain (quantitative) attributes, we can precisely describe and use the elements of X having the inverse (quantitative) attributes.
In our books [Springer 2016, Springer 2020], we studied the multisets allowing negative multiplicities both in the Zermelo-Fraenkel framework and in the finitely supported framework (where only finitely supported sets are allowed), analyzing the correspondence between some properties of these generalized multisets obtained in finitely supported framework and those obtained in the classical ZermeloFraenkel framework.
Finitely supported sets are related to the permutation models of Zermelo-Fraenkel set theory with atoms. These models were introduced in 1930s by Fraenkel, Lindenbaum and Mostowski to prove the independence of the axiom of choice from the other axioms of Zermelo-Fraenkel set theory with atoms (ZFA). More recently, finitely supported sets have been developed in Zermelo-Fraenkel (ZF) set theory by equipping ZF sets with actions of a group of one-to-one and onto transformations of some basic elements called atoms. Sets with permutation actions were used to investigate the variables binding, renaming and choosing fresh names in the theory of programming since the notions of structural recursion and structural induction can be adequately transferred into this new framework, as well as in describing automata, languages and Turing machines that operate over infinite alphabets. The notions of invariant set and finitely supported structure are introduced and described in previous papers of the authors. An invariant set is defined as a usual ZF set endowed with a group action of the group of all one-to-one and onto transformations of certain fixed infinite ZF set A of basic elements (called atoms) satisfying a finite support requirement. This requirement states that any element in an invariant set has to be finitely supported, i.e. for any such element x there should exist a finite set of atoms S_x such that any permutation of atoms fixing S_x pointwise also leaves the element x invariant under the related group action. A finitely supported set is defined as a finitely supported element in the powerset of an invariant set. A finitely supported structure is defined as a finitely supported set equipped with a finitely supported internal algebraic law or relation (which should be finitely supported as a subset of a Cartesian product of finitely supported sets).
The theory of finitely supported structures allows a discrete representation of possibly infinite sets containing enough symmetries to be concisely handled. More specifically, this theory allows us to treat as equivalent the objects that have a certain degree of similarity and to focus only on those objects that are “really different” by involving the notion of finite support.
The framework of finitely supported structures contains both the family of non-atomic ZF structures which are proved to be trivially invariant (i.e. all their elements are empty supported) and the family of atomic structures with f inite (possibly non-empty) supports. We have to analyze whether a ZF result preserves its validity when reformulating it by replacing ‘non-atomic ZF structure’ with ‘atomic and finitely supported structure’. The meta-theoretical technique for the translation of ZF results into the framework of atomic finitely supported structures is based on a closure property for finite supports in an hierarchical construction, called ‘S-finite support principle’ claiming that “for any finite set S of atoms, anything that can be defined in higher-order logic from structures supported by S, by using each time only constructions supported by S, is also supported by S”. The formal involvement of the related S-finite support principle implies a step-by-step construction of the support of a structure by using, at every step, the previously constructed supports of the substructures of the related structure. However, there are ZF results that cannot be translated into an atomic framework as we proved in [Springer 2020].
In this tutorial, by extending the results in [Springer 2016] and [Springer 2020], we define and investigate the group-valued multisets, also in the framework of finitely supported sets. By involving the theory of finitely supported sets, we are able to study group-valued multisets over infinite sets X in a finitary manner.
We introduce finitely supported groups and provided some relevant examples of these structures. The finitely supported groups are finitely supported sets equipped with finitely supported internal group laws. We prove that the set of all finitely supported bijections of a finitely supported set, the set of all finitely supported automorphisms of a finitely supported group, the set of all finitely supported inner automorphisms of a finitely supported group, and the set of all equivalence classes of finite words with letters belonging to a finitely supported set, all are finitely supported groups. We prove an isomorphism theorem for finitely supported groups and a result showing that the finitely supported group of all finitary permutations of atoms coincide with the finitely supported group of all bijections of atoms. We also prove some counting properties for the supports of free groups. Then we introduce and study finitely supported group-valued multisets (called G-multisets). For each G-multiset we provide a relationship result between its support and its algebraic support (formed by the family of elements with a non-empty multiplicity). The set of all G-multisets on a finitely supported universe of discourse X can be organized as a finitely supported group and satisfies some (Cayley-type) embedding results, as well as isomorphism and universality theorems. We provide some examples of infinite finitely supported groups that are Dedekind finite (i.e. they do not contain infinite, finitely supported countable subsets). Finally, we connect the concepts of G-multiset, free group and hybrid set (Z-multiset with finite algebraic support) via some universality properties.

[Springer 2016] A. Alexandru, G. Ciobanu. Finitely Supported Mathematics:  An Introduction, Springer-Nature, 185 pages, 2016. 

[Springer 2020] A. Alexandru, G. Ciobanu. Foundations of Finitely Supported  Structures: A set theoretical viewpoint, Springer-Nature, 210 pages, 2020.

Short Bio:

Gabriel Ciobanu is a member of Academia Europaea. He has wide-ranging  interests in mathematics and computer science. During the last dozen years, he worked in the foundations of mathematics (mainly, finitely supported structures).