EnglishSets and functionsFunctions
The grocery lists you make for yourself probably don't look quite like a set or a list, because the quickest way to indicate how many of each item to purchase is to make a separate column:
item | count |
apple | 3 |
bread | 1 |
squash | 3 |
We have two sets here: the set of grocery items and the set of positive integers. For each element in the former set, we want to associate with it some element of the latter set.
Note that this construction is asymmetric in the two sets: every grocery item should have exactly one number associated with it, while some positive integers will be omitted and others may be associated with multiple grocery items.
The idea of attaching a piece of data to each element of a set arises very often throughout the quantitative disciplines, and it deserves its own vocabulary:
Definition (Function, domain, and codomain)
If and are sets, then a function is an assignment to each element of of some element of .
The set is called the domain of and is called the codomain of .
The domain and codomain of a function should be considered part of the data of the function: to fully specify , we must specify (i) the domain , (ii) the codomain , and (iii) the value of for each .
Two functions and are considered equal if (i) they have the same domain and codomain and (ii) for all in the domain of and .
Exercise.
Consider the function from the set of real numbers to the set of real numbers which square its input, as well as the function from the set of real numbers to the set of nonnegative real numbers which also squares its input. Are these functions equal?
Solution. The functions are unequal, since their codomains are not the same.
Images
Given a subset of , we define the image of —denoted —to be the set of elements which are mapped to from some element in :
The range of is defined to be the image of the domain of . Thus, the range may be obtained from the codomain by removing all the elements that don't get mapped to.
Exercise
Find the range of the function from {apple, bread, squash} to represented by the following table. It contains
item | count |
apple | 3 |
bread | 1 |
squash | 3 |
Solution. The range is the set of quantity counts which get mapped to from some grocery item, so the range is the two-element set .
Exercise
Consider the social-security-number function from the set of US citizens and permanent residents to the set of integers . For each person , is defined to be the social security number of person .
- What are the largest and smallest possible values of the ratio for any nonempty subset of the domain of ? Largest:
Smallest: - Estimate the ratio of the cardinality of the range of to the cardinality of the codomain of . (You can estimate the number of social security numbers issued to be about 40% more than the current US population).
What implications does this have for the Social Security Administration?
Solution. (i) The value of is 1 for any set : since no two people are issued the same social security number, the number of elements in is equal to the number of elements in .
(ii) There are elements in the codomain of , and about 450 million numbers have been issued. Therefore, the ratio of the cardinality of the range to the cardinality of the codomain is about . Since a macroscopic percentage of possible SSNs have been used, it's clear that eventually the SSA will eventually have to either issue duplicate SSNs or increase the number of digits they use for each one.
Preimages
Definition
If , then the preimage of is defined by
This is the subset of consisting of every element of that maps to some element of .
Exercise
- The statement "the preimage of a nonempty subset of the codomain of a function may be empty" is
. - The statement "the preimage of can have more elements than " is
.
Solution. The first statement is true; for example, consider the squaring function from the real number line to itself. The preimage of any set of negative numbers is empty.
The second statement is also true, since multiple input elements may map to the same codomain element.
Exercise
Consider the following purported equalities.
(i)
(ii)
(iii)
(iv)
Which of the are true for all functions and all subsets and of the domain of and subsets and of the codomain of ?
(a) all of them
(b) none of them
(c) (i) and (ii) only
(d) (iii) and (iv) only
(e) (ii), (iii), and (iv) only
Solution. The correct answer is (e). To show that (ii) , we note that if , then for some . This element is in either or , which means that is in either or . Thus, . So . Similar reasoning shows that as well. Statements (iii) and (iv) may likewise be confirmed.
To see that (i) may fail, consider the function from to which squares its input. Let and . Then , while .
The squaring function on $\{-1,0,1\}$ shows that the equality $f(A \cap B) = f(A) \cap f(B)$ does not hold in general.
