Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T15:09:53.618Z Has data issue: false hasContentIssue false
  • English
  • Français

Multisets, heaps, bags, families: What is a multiset?

Published online by Cambridge University Press:  27 January 2020

Helmut Jürgensen
Helmut Jürgensen*
Affiliation:
Department of Computer Science, The University of Western Ontario, London, Ontario, N6C 5B7, Canada
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Is the current formulation of multiset theory, which is based on sets and multiplicities of their elements, adequate? We exhibit both mathematical and metamathematical reasons which should cause one to rethink the definition. Some problems with multiset theory in its accepted formulation concern even the basic operations of union, intersection, and complement; others, more deeply rooted, concern Cartesian products, relations, or morphisms. We compare current definitions and conclude that the problems of multiset theory need to be resolved at the fundamental level of sets and mappings (or equivalent constructs) with multiplicities introduced only as a secondary concept. As a consequence, we propose to define multisets as families. A mapping establishes the connection to the familiar theory of multisets. Without losing anything, our proposal is simple and provides for an elegant mathematical theory.

Keywords

Multisetgeneralised multisetcategories
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 2 , February 2020 , pp. 139 - 158
Copyright
© The Author(s) 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

‡

A preliminary version of this paper, without proofs and details, was presented at the International Conference on Recent Advances in Pure and Applied Mathematics, ICRAPAM 2016, held on 19–23 May, 2016, in Bodrum, Turkey (Jürgensen 2016).

†

Deceased.

References

Angelelli, I. (1965). Leibniz’s misunderstanding of Nizolius’ notion of ‘multitudo’. Notre Dame Journal of Formal Logic 6 (4), 319–322.CrossRefGoogle Scholar
Angelelli, I. (2001) Nizolius’ notion of class (multitudo). Anales de la Acad. Nacional de Ciencias de Buenos Aires 35 (2), 575–595.Google Scholar
Blizard, W. D. (1986) Generalizations of the Concept of Set: A Formal Theory of Multisets. Doctoral thesis, Mathematics Institute, University of Oxford.Google Scholar
Blizard, W. D. (1989) Multiset theory. Notre Dame Journal of Formal Logic 30 (1), 36–66.CrossRefGoogle Scholar
Blizard, W. D. (1990) Negative membership. Notre Dame Journal of Formal Logic 31 (3), 346–368.CrossRefGoogle Scholar
Blizard, W. D. (1991) The development of multiset theory. Modern Logic 1 (4), 319–352. Corrections, errata and update in Modern Logic 2 (2), (1991), 219 and 7 (3–4), (1997), 434.Google Scholar
Blizard, W. D. (1993) Dedekind multisets and function shells. Theoretical Computer Science 110 (1), 79–98.CrossRefGoogle Scholar
Bogatiryova, J. A. (2011) Teoriya mul126timnozhin ta zastosuvannya (The Theory of Multisets and its Applications). Doctoral thesis, Kiev National University, in Ukrainian.Google Scholar
Brink, C. (1988) Multisets and the algebra of relevance logic. Journal of Non-Classical Logic 5 (1), 75–95.Google Scholar
Calude, C. S., Păun, G., Rozenberg, G. and Salomaa, A. (eds.) (2001) Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View, Lecture Notes in Computer Science, vol. 2235, Berlin, Springer-Verlag.Google Scholar
Cantor, G. (1883) Grundlagen einer allgemeinen Mannigfaltigkeitslehre: Ein mathematisch-philosophischer Versuch in der Lehre des Unendlichen. Teubner, Leipzig. Reprinted as (1962, p. 165 sqq.).Google Scholar
Dedekind, R. (1888) Was sind und was sollen die Zahlen? Braunschweig, Vieweg.Google Scholar
Eilenberg, S. (1974) Automata, Languages, and Machines, Pure and Applied Mathematics, vol. 59A. New York, Academic Press.Google Scholar
Grothendieck, A. and Verdier, J. L. (1972) Prefaisceaux. In: Artin, M., Grothendieck, A. and Verdier, J. L. (eds.) Théorie des Topos et Cohomologie Étale des Schémas. Séminaire de géométrie algébrique du Bois-Marie, 1963–1964 (SGA). Tome 1: Théorie des topos (exposés I à IV), Lecture Notes in Mathematics, vol. 269, Berlin, Springer-Verlag, 1–217.Google Scholar
Hailperin, T. (1986) Boole’s Logic and Probability, 2nd edn., Studies in Logic and the Foundations of Mathematics, vol. 85, Amsterdam, North-Holland.Google Scholar
Hickman, J. L. (1980) A note on the concept of multiset. Bulletin of the Australian Mathematical Society 22 (2), 211–217.CrossRefGoogle Scholar
Ibrahim, A. M. (2010) A Study of Multiset Algebras. Phd thesis, Ahmadu Bello University, Zaria, Nigeria. http://kubanni.abu.edu.ng:8080/jspui/bitstream/123456789/2416/1/A%20STUDY%20OF%20MULTISET%20ALGEBRAS.pdf (The link may change, and one amy have to search the DSpace site.). Also published as “A Study of Multiset Algebras: A Systematization of Fundamentals of Multiset Theory,” Saarbrücken, Lambert Academic Publishing, 2011.Google Scholar
Jena, S. P., Ghosh, S. K. and Tripathy, B. K. (2001) On the theory of bags and lists. Information Sciences 132 (1–4), 241–254.CrossRefGoogle Scholar
Jürgensen, H. (2016) What is a multiset? In: Third International Conference on Recent Advances in Pure and Applied Mathematics (ICRAPAM 2016), Abstract Book, 19–23 May, 2016, Bodrum, Turkey, 116–117. Istanbul Commerce University, Istanbul Medeyinet University, Institute of Mathematics of National Academy of Science of Ukraine. 2016.icra-pam.org/images/AbsBook2016.pdf. The abstract book was distributed on CD at the conference with a different page numbering. There the page numbers are 130–131.Google Scholar
Jürgensen, H. (2017) Higher-level constructs for families and multisets. Theoretical Computer Science 682, 138–148.CrossRefGoogle Scholar
Kauppi, R. (1966) Einige Bemerkungen zum principium identitatis indiscernibilium bei Leibniz. Zeitschrift für philosophische Forschung 20 (3–4), 497–506.Google Scholar
Knuth, D. E. (1997) The Art of Computer Programming, 3rd edn., Boston, Addison-Wesley Publishing Company.Google Scholar
Kümmel, F. (2016) Zum Verhältnis von Leibniz’ Prinzip der Identität des Ununterscheidbaren (principium identitatis indiscernibilium) und seinem Gedanken der Individualität, or earlier. Unpublished manuscript, available at www.friedrich-kuemmel.de/doc/Leibniz.pdf.Google Scholar
Leibniz, G. W. (1961) Primæ veritates. In: Couturat, L. (ed.) Opuscules et fragments inédits de Leibniz. Extraits des manuscrits de la Bibliothèque royale de Hanovre. Hildesheim, Georg Olms Verlagsbuchhandlung, 518–523. Reprint of the 1903 edition by Presses Universitaires de France, Paris.Google Scholar
Marcus, S. (2001) Tolerance multisets. In: (2001), 217–223.CrossRefGoogle Scholar
Menzel, Chr. (1984) Cantor and the Burali-Forti paradox. The Monist 67 (1), 92–107.CrossRefGoogle Scholar
Monro, G. P. (1987) The concept of multiset. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 33 (2), 171–178.CrossRefGoogle Scholar
Peeva, K. and Kyosev, Y. (2004) Fuzzy Relational Calculus; Theory, Applications and Software, Advances in Fuzzy Systems – Applications and Theory, vol. 22, New Jersey, World Scientific.CrossRefGoogle Scholar
Plato (1925) The Statesman, Philebus (with an English Translation by Harold N. Fowler), Ion (with an English Translation by W. R. M Lamb), Loeb Classical Library, vol. 164, Cambridge, Massachusetts, Harvard University Press.Google Scholar
Red’ko, V. N., Bui, D. B. and Grishko, Y. A. (2015) Современное состояние теории мул тимножеств с сущностоноῐ точки зрения. Kibernetika i Sistemnyi Analiz 2015 (1), 171–178. English translation: Current state of the multisets theory from the essential viewpoint, Cybernetics and Systems Analysis 51 (1), 150–156.Google Scholar
Singh, D. (1994) A note on “The development of multiset theory [Blizard 1991]”. Modern Logic 4 (4), 405–406.Google Scholar
Singh, D., Ibrahim, A. M., Yohanna, T. and Singh, J. N. (2007) An overview of the applications of multisets. Novi Sad Journal of Mathematics 37 (2), 73–92.Google Scholar
Singh, D., Ibrahim, A. M., Yohanna, T. and Singh, J. N. (2008) A systematization of fundamentals of multisets. Lecturas Matemáticas 29 (1), 33–48.Google Scholar
Singh, D., Ibrahim, A. M., Yohanna, T. and Singh, J. N. (2011) Complementation in multiset theory. International Mathematical Forum 6 (38), 1877–1884.Google Scholar
Singh, D., Ibrahim, A. M., Yohanna, T. and Singh, J. N. (2016) Multisets: a new paradigm of science. Unpublished manuscript.Google Scholar
Singh, D. and Isah, A. I. (2013) A note on category of multisets (MUL). International Journal of Algebra 7 (2), 73–78.CrossRefGoogle Scholar
Singh, D., Isah, A. I. and Alkali, A. J. (2013) Does the category of multisets require a larger universe than that of the category of sets? Pure Mathematical Sciences 2 (3), 133–146.CrossRefGoogle Scholar
Singh, D. and Singh, J. N. (2008) A note on the definition of a multisubset. News Bulletin of Calcutta Mathematical Society 31 (4–6), 19–20.Google Scholar
Singh, D., Singh, J. N. and Chinyio, D. T. (2002) An outline of multiset theory. Papua New Guinea Journal of Mathematics, Computing and Education 6 (1), 1–14.Google Scholar
Syropoulos, A. (2001) Mathematics of multisets. In: (2001), 347–358.CrossRefGoogle Scholar
Syropoulos, A. (2003) Categorical models of multisets. Romanian Journal of Information Science and Technology 6 (3–4), 393–400.Google Scholar
Tella, Y. and Daniel, S. (2011) Computer representation of multisets. Scientific World Journal 6 (1), 21–22.Google Scholar
Wildberger, N. J. (2003) A new look at multisets. School of Mathematics, University of New South Wales, Sydney, Australia; unpublished manuscript, available at web.maths.unsw.edu.au/Ÿnorman/papers/NewMultisets5.pdf.Google Scholar
Yager, R. R. (1986) On the theory of bags. International Journal of General Systems 13 (1), 23–37.CrossRefGoogle Scholar
Zermelo, E. (ed.) (1962) Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Hildesheim, Georg Olms Verlagsbuchhandlung.Google Scholar