Sözlük

Soldaki anahtar kelimelerden birini seçin…

Sets and functionsFunctions

Okuma zamanı: ~25 min

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 A and B are sets, then a function f:A \to B is an assignment to each element of A of some element of B.

The set A is called the domain of f and B is called the codomain of f.

Potato-and-arrow diagrams can be helpful for visualizing the relationship between a function, its domain, and its codomain.

The domain and codomain of a function should be considered part of the data of the function: to fully specify f, we must specify (i) the domain A, (ii) the codomain B, and (iii) the value of f(x) for each x \in A.

Two functions f and g are considered equal if (i) they have the same domain and codomain and (ii) f(x) = g(x) for all x in the domain of f and g.

Exercise.
Consider the function f from the set of real numbers to the set of real numbers which square its input, as well as the function g 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 A' of A, we define the image of f—denoted f(A')—to be the set of elements which are mapped to from some element in A':

\begin{align*}f(A') = \{b \in B \, : \, \text{there exists }a \in A' \text{ so that } f(a) = b\}.\end{align*}

The range of f is defined to be the image of the domain of f. 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 \mathbb{N} represented by the following table. It contains elements.

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 \{1,3\}.

Exercise
Consider the social-security-number function f from the set of US citizens and permanent residents to the set of integers \{000000000,000000001,\ldots,999999999\}. For each person x, f(x) is defined to be the social security number of person x.

  • What are the largest and smallest possible values of the ratio \frac{|f(A)|}{|A|} for any nonempty subset A of the domain of f? Largest: Smallest:
  • Estimate the ratio of the cardinality of the range of f to the cardinality of the codomain of f. (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 \frac{|f(A)|}{|A|} is 1 for any set A: since no two people are issued the same social security number, the number of elements in f(A) is equal to the number of elements in A.

(ii) There are 10^{9} elements in the codomain of f, 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 0.45. 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 B'\subset B, then the preimage f^{-1}(B') of B' is defined by

\begin{align*}f^{-1}(B') = \{a \in A \, : f(a) \in B'\}.\end{align*}

This is the subset of A consisting of every element of A that maps to some element of B'.

Exercise

  1. The statement "the preimage of a nonempty subset of the codomain of a function may be empty" is .
  2. The statement "the preimage of B' can have more elements than B'" 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) f(A \cap B) \stackrel{?}{=} f(A) \cap f(B)

(ii) f(A \cup B) \stackrel{?}{=} f(A) \cup f(B)

(iii) f^{-1}(C \cap D) \stackrel{?}{=} f^{-1}(C) \cap f^{-1}(D)

(iv) f^{-1}(C \cup D) \stackrel{?}{=} f^{-1}(C) \cup f^{-1}(D)

Which of the are true for all functions f and all subsets A and B of the domain of F and subsets C and D of the codomain of f?

(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) f(A \cup B) = f(A) \cup f(B), we note that if y \in f(A \cup B), then y = f(x) for some x \in A \cup B. This element x is in either A or B, which means that y = f(x) is in either f(A) or f(B). Thus, y \in f(A) \cup f(B). So f(A \cup B) \subset f(A) \cup f(B). Similar reasoning shows that f(A) \cup f(B) \subset f(A \cup B) as well. Statements (iii) and (iv) may likewise be confirmed.

To see that (i) may fail, consider the function from \{-1,0,1\} to \{0,1\} which squares its input. Let A = \{-1,0\} and B = \{0,1\}. Then f(A \cap B) = \{0\}, while f(A) \cap f(B) = \{0,1\}.

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.

Bruno
Bruno Bruno