Sets are unibags

There is a one-to-one correspondence between the so-called "bags" of elements from a domain and the natural functions on that domain. A natural function bf corresponds to a bag b - or: is b's so-called "characteristic function" - means that for any d in the domain

• bf(d) is called "the number of times d occurs in bag b" or "the number of instances of d in bag b";
• bf(d) ≥ 1 is called "d occurs in bag b" and is denoted by "d in b";
• changing the function bf by increasing bf(d) by 1 is described as "adding one d (or: one instance of d) to bag b" - an operation, which can be undone by "removal of one (instance of) d from bag b" - ;
• the function bf being zero everywhere on the domain is denoted by "bag b is empty";
• etc.

Bags are a useful metaphor when dealing with natural functions on all sorts of domains: bags of positive integers, bags of characters from a given alphabet, bags of differently coloured pebbles, etc. can come in quite handy.

Bags with characteristic functions whose range

is restricted to {0,1}, i.e. bags all elements in which are distinct, are quite well-known to mathematicians, who call them "sets".

* * *

Sets are, in fact, so well-known that when, later, bags were discovered as a useful concept they were originally called "multisets". This was, of course, a misnomer, since, like an adjective, a prefix should restrict. (Hence the title of this little note.)

The purpose of this note, however, is to record a recent discovery, which amazed me greatly and the significance of which is, as yet, unfathomed: of about 10 grown-up mathematicians I asked, only 1½ had ever heard of multisets and only 1 of them had heard of bags (and that had been the other week). My question had been prompted by my observation of the difficulties an otherwise brilliant mathematician had with EWD785. The notion of a bag was profoundly unfamiliar to him! Since I can hardly think of anything more "natural" than a natural function, I am completely baffled. Does the mathematical community have more of such streaks?

Plataanstraat 5 5671 AL NUENEN The Netherlands

15 April 1981 prof.dr. Edsger W. Dijkstra Burroughs Research Fellow

---

Transcription by John C Gordon

Last revised on Wed, 09 Jul 2003 .