On Wed, 30 Mar 2016 09:28 pm, Jussi Piitulainen wrote: > Steven D'Aprano writes: > >> On Wed, 30 Mar 2016 06:12 pm, Jussi Piitulainen wrote: >> >>> Steven D'Aprano writes: >>> >>>> Given a surjection (many-to-one mapping) >>> >>> No. And I doubt that Wikipedia says that. >> >> No to what? What are you disagreeing with? > > Surjection does not mean many-to-one mapping. It means something else.
Oh, if only I had linked to the Wikipedia page earlier... oh wait, I did. Here it is again: https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection The relevant definition is: The function is surjective (onto) if every element of the codomain is mapped to by at least one element of the domain. (That is, the image and the codomain of the function are equal.) A surjective function is a surjection. Notationally: \forall y \in B, \exists x \in A \text{ such that } y = f(x).\ and the relevant diagram is the image labelled "Non-injective and surjective", also seen here: https://en.wikipedia.org/wiki/File:Surjection.svg Why is a mapping (such as a dict) best described as a surjection? Consider: d = {1: None, 2: 'a', 3: 'b', 4: None} Every key has exactly one value. There are no values without a key, and every value has *at least* one key. To be an injection or a bijection, it must be one-to-one. Since multiple keys can map to the same value, it's not an injection or a bijection. Every value must have a key: there are no values in the dict without a key. Hence, it's a surjection. Although Wikipedia don't use the description, "many-to-one" is a good way of describing surjections, since you can have many keys mapped to a single value. To be precise, some surjections may be one-to-one, and not all many-to-one relations are surjections. But the distinguishing feature of a surjection is that each value must have *at least* one key, which describes dicts and other such mappings. And for those who don't trust Wikipedia: http://mathsforall.co.uk/userfiles/SECTION%203B%20Injective%20and%20Surjective%20functions%2027_11_06.pdf -- Steven -- https://mail.python.org/mailman/listinfo/python-list
