HOME

Sets are unibags

Show original manuscript

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

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

EWD786a - 1

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 .