Massachusetts Institute of Technology Lecture 14 6.042J/18.062J: Mathematics for Computer Science October 26, 2000 Professors Nancy Lynch and Srinivas Devadas

Functions, Counting, and the Pigeonhole Principle

1 Self Study: Functions

1.1 Basic definitions

Definition A function f : A ↦ B is a way of relating every element of A to exactly one element of B.

If a ∈ A, write f(a) for the corresponding element of B.

A = domain, B = range.

More formally, a function f : A ↦ B is a binary relation from A to B such that, for every a ∈ A, there is exactly one b ∈ B such that (a, b) ∈ f.

Example: Draw a function (not onto).

Example: Draw a non-function (two values for some particular domain element).

Example: In the matching algorithm, at any particular point in time, each boy had a current girl he was pursuing. Function from boys to girls, giving current girl. Inverse is not a function.

And some examples from continuous math. In each case, f : ℝ ↦ ℝ.

Example: f(x) = x^{2} + 3x + 2

Example: f(x) = |x| (define as x if x ≥ 0, −x if x < 0.

Example: f(x) = \sqrt{x} not a function. Not uniquely defined. Even if I mean the positive square root, still not a function: Not defined everywhere on ℝ.

Example: f(x) = cube root of x is a function.

Definition The image of a function f : A ↦ B is the set {b | ∃ a f(a) = b} and is denoted f(A).

Values actually taken on, subset of range.

Example: First example above, image = ...

Example: f(x) = x^{2} + 3x + 2. Draw graph. Min point is (−\frac{3}{2}, −\frac{1}{4}). Image = [−\frac{1}{4}, ∞).

Example: Absolute value. Image = nonnegative reals.

Example: Cube root. Image = reals.

1.2 Special kinds of functions

Classification relevant for counting: surjective, injective, bijective

Definition Surjective (“onto”) Image = range. ∀ b ∈ B, ∃ a ∈ A(f(a) = b).

Examples: Diagrams, surjective and not surjective.

Example: At end of matching algorithm, current girl function is surjective.

Example: Cube root is surjective, as a function : ℝ ↦ ℝ.

Example:

Absolute value not surjective as function : ℝ ↦ ℝ. But could regard as function : ℝ ↦ ℝ^{≥0}, then surjective. Depends on what’s defined as the range.

Definition Injective (“one-to-one”) ∀ a, a′ ∈ A, a ≠ a′ ⇒ f(a) ≠ f(a′)

Examples: Diagrams, injective and not injective.

Example: Cube root injective.

Example: Absolute value not injective.

Definition Bijective = surjective + injective. AKA one-to-one correspondence.

Examples: Diagrams Cube root

1.3 Proving that functions are surjective and injective

Example: f : ℝ ↦ ℝ, f(x) = \sqrt[3]{x}

To prove injective, can show contrapositive:

Prove: f is injective, that is, a ≠ a′ ⇒ \sqrt[3]{a} ≠ \sqrt[3]{a′}.

1. \sqrt[3]{a} = \sqrt[3]{a′} ⇒ a = a′.

1. Assume \sqrt[3]{a} = \sqrt[3]{a′}.

2. (\sqrt[3]{a})^{3} = (\sqrt[3]{a′})^{3}. Algebra (cube both sides)

3. a = a′ Algebra

4. QED Implication

2. QED Contrapositive

To prove surjective, can fix any element of the range and show how to construct a corresponding element of the domain. (That’s enough, because of EG and UG.)

Prove: f is surjective, that is, ∀ b ∈ ℝ, ∃ a ∈ ℝ(\sqrt[3]{a} = b).

1. Fix b ∈ ℝ.

2. Define a = b^{3}.

3. \sqrt[3]{a} = b

4. QED EG, UG

Example: f : ℕ ↦ ℕ, f(n) = n^{2}.

Show injective, this time using a direct proof:

Prove: f is injective, that is, n ≠ n′ ⇒ n^{2} ≠ (n′)^{2}.

1. Assume n ≠ n′.

2. n > n′ or n′ > n Basic property of ℕ.

3. If n > n′ then n^{2} > (n′)^{2}. Algebra.

4. If n < n′ then n^{2} < (n′)^{2}. Algebra.

5. n^{2} ≠ (n′)^{2}. Cases, 3. and 4.

6. QED Implication, 1. and 5.

Not surjective. Show this by exhibiting a particular value that has nothing mapping to it (go over the quantifier manipulation):

Prove: f is not surjective, that is, ¬(∀ b ∈ B, ∃ a ∈ ℕ, a^{2} = b)

1. ∃ b ∈ ℕ, ∀ a ∈ ℕ, a^{2} ≠ b.

1. ∀ a ∈ ℕ[a^{2} ≠ 3].

1. Fix a ∈ ℕ.
2. a^{2} ≠ 3

1. Assume a^{2} = 3.

2. a is not rational. Proofs earlier in term.

3. a ∉ ℕ.

4. QED Contradiction, 1.1.1 vs. 1.1.2.3 3. QED UG 2. QED EG

2. QED Quantifier manipulation

2 Self Study: Using Functions for Determining Cardinalities

Theorem 2.1 Suppose A and B are finite sets, f : A ↦ B.

1. If f is an injection then |A| ≤ |B|.

2. If f is a surjection then |A| ≥ |B|.

3. If f is a bijection then |A| = |B|.

Proof.

1. Prove by letting n be the number of elements in A, and finding n distinct elements of B.

Prove: |A| ≤ |B|

1. Define n ∈ ℕ, n = |A|. Define A = {a_{1}, a_{2}, …, a_{n}}.

2. ∀ i ∈ {1, …, n} , f(a_{i}) ∈ B Definition of function.

3. All the f(a_{i}) are distinct. Injectivity.

4. |B| ≥ n By 2. and 3.

5. QED Algebra, 1. and 4.

Finiteness assumption used in step 1. Funny situations can arise if sets aren’t finite:

Consider f : ℕ ↦ perfect squares, given by f(n) = n^{2}. f is injective (no 2 have same square). But A has all the elements of B, and many more.

Suggests that A is strictly larger than B. Apparent paradox will be resolved in an upcoming lecture on infinite sets.

2. Prove by letting n be the number of elements in B, and finding n distinct elements of A.

Prove: |A| ≥ |B|

1. Define n ∈ ℕ, n = |B|. Define B = {b_{1}, b_{2}, …, b_{n}}.

2. ∀ b_{i} ∈ B, ∃ a_{i} ∈ A, f(a_{i}) = b_{i} Surjectivity.

3. ∀ b_{i} ∈ B, choose a_{i} ∈ A such that f(a_{i}) = b_{i} EI

4. All the a_{i} are distinct. Definition of function.

5. |A| ≥ n By 3. and 4.

6. QED Algebra, 1. and 5.

3. Could go through the same kind of proofs, but don’t have to:

Consequence of first two parts of the theorem.

2.1 Example: Counting subsets of a finite set

A counting problem that can be solved by finding a bijection.

Definition The power set of a set A, denoted by P(A), is the set of all subsets of A, that is, {S | S ⊆ A}.

Also written sometimes as 2^{A}. Looks strange, but we’ll see why.

Example: A = {a_{1}, a_{2}, a_{3}}. P(A) = {∅, {a_{1}}, {a_{2}}, {a_{3}}, {a_{1}, a_{2}}, {a_{1}, a_{3}}, {a_{2}, a_{3}}, {a_{1}, a_{2}, a_{3}}, }.

8 elements.

Theorem 2.2 If A is a finite set with |A| = n, then |P(A)| = 2^{n}.

Proof. Use bijection to a set we already know has size 2^{n}: the set B of n-bit binary strings, B = {b_{1}b_{2} … b_{n} | b_{i} ∈ {0, 1}}. Then Theorem...will imply |P(A)| = 2^{n}.

Defining bijection f : 2^{A} ↦ B:

Write A = {a_{1}, a_{2}, … a_{n}}.

Let f(C), where C ⊆ A, be the string b_{1}b_{2} … b_{n}, where b_{i} = 1 if and only if a_{i} ∈ C. Use bit i to encode membership of element a_{i}.

Examples: Above, if C = {a_{1}, a_{3}}, then f(C) = 101. If C = ∅ then f(C) = 000.

f is a well-defined function — it’s possible to encode every set in this way. Claim f is a bijection. Must prove injective and surjective.

Injective:

Prove: f is injective, that is, if C ≠ C′ then f(C) ≠ f(C′).

1. Assume C ≠ C′.

2. ∃ a ∈ C − C′ or ∃ a ∈ C′ − C.

3. If ∃ a ∈ C − C′ then f(C) ≠ f(C′).

1. Assume ∃ a ∈ C − C′.

2. Fix a ∈ C − C′. . 3. Bit i of f(C) = 1.

Bit i of f(C′) = 0. Definition of f.

4. f(C) ≠ f(C′).

5. QED Implication.

4. If ∃ a ∈ C′ − C then f(C) ≠ f(C′). Analogous.

5. f(C) ≠ f(C′) Cases, 3. and 4.

6. QED Implication.

Surjective:

Prove: f is surjective, that is, for every length n bit string b_{1}b_{2} … b_{n}, ∃ C ⊆ A, such that f(C) = b_{1}b_{2} … b_{n}.

1. Fix b_{1}b_{2} … b_{n}.

2. Choose C = {a_{i}|b_{i} = 1}.

3. f(C) = b_{1}b_{2} … b_{n}

4. QED EG, UG

Exercise: Show P(A) = 2^{n} another way, by induction on n, without using bijections.

2.2 Counting numbers of functions

The ideas involved in counting the number of subsets of a set can be generalized to help in counting the number of functions from one set to another:

Question: How many different functions are there from finite set A to finite set B? Say |A| = n, |B| = m.

Example: |A| = 3, |B| = 2.

Draw all the possibilities. 8 of them.

Theorem 2.3 If A and B are finite sets, with |A| = n and |B| = m, then the cardinality of the set of functions from A to B is m^{n}.

Proof. Use bijection to M, the set of length n strings of symbols from the alphabet {1, …, m}. Use position i to encode the value of f(i).

Example: The first function above is encoded by 111 Second by 121. Etc. Last is 222.

Prove bijection:

Injective: Same rep means same function. Prove by contrapositive, showing different function means different rep. LTTR.

Surjective: Every string encodes some function. LTTR.

Exercise: What if we wanted to count the number of injective functions from A to B?

Requires |B| ≥ |A|, by Theorem...

Again, can see this using a bijection with a set of length n strings, but now it’s not all the length n strings, but only those where no number is repeated.

How many? m(m − 1)(m − 2) ⋯ (m − n + 1).

Needs m ≥ n to make sense.

Return to this later.

Exercise: Number of surjective functions? Needs m ≤ n, by Theorem.

Bijection with strings of length n in which every element appears at least once.

Will have to come back to this later...(try it).

3 The Pigeonhole Principle

3.1 The theorem

Theorem 3.1 If n pigeons are put into m holes, n > m, then at least one hole contains two or more pigeons.

Actually this isn’t really about pigeons and holes. Restate in terms of functions:

Theorem 3.2 Let A and B be finite sets, |A| > |B|. If f : A ↦ B then there exist distinct elements a and a′ in A such that f(a) = f(a′).

Why this says the same thing: A: pigeons B: holes f: says where each pigeon gets put

Proof. In other words, says if |A| > |B| then f is not injective. Follows immediately from Theorem, contrapositive.

Example: 32 people, exist 2 born on same day of month (1-31). Pigeons: the 32 people Holes: The 31 days. Rule for putting pigeons in holes: Birth date

3.2 Example: Divisibility

Theorem: In every set of 1000 integers, there exist two, x and y, such that x − y is divisible by 699.

Seems hard.

Use Pigeonhole: Try 1000 pigeons and 699 holes: Pigeons: the 1000 integers Holes: ? Rule: ?

We would like to arrange things so that x and y in same hole implies that 699 divides x − y. How?

Holes: numbers 0, 1, …, 698

Rule: Integer x goes into hole r if r is the remainder when x is divided by 699.

Pigeonhole principles says some two integers x and y must have the same remainder mod 699. x mod 699 = y mod 699. 699 divides x − y.

Works for any m, n, m < n, not just 699 and 1000.

3.3 Example: Weighing Balls

Given 12 balls, know that 11 are same weight and one is different. May be heavier or lighter. Want to discover which is the odd ball, and if it’s heavy or light.

Do by weighings of a balance scale. Can do in 3 weighings.

Can solve by algorithm, represent with tree: (Draw part, go over.)

Example: Prove impossible to solve with 14 balls, 3 weighings.

Pigeons: Possible initial situations: 1L, 2L, . .. 14L, 1H, 2H, ...14H 28 situations

3 comparisons yields height 3 tree, with 3 children for each internal node.

27 leaves.

Figure 1: A strategy for the weighing problem can be represented by a ternary tree. Each internal node represents a weighing. Each leaf node represents a result. A run of the algorithm corresponds to a path from the root to a leaf. At each internal node, we perform the weighing associated with the node and descend to a child based on the result. At a leaf, we output the indicated result.

Holes: The 27 leaves

Rule: Map each initial situation to the leaf it reaches.

Pigeonhole principle says exist two initial situations leading to the same leaf. But leaf has only one decision. So the two situations give the same answer, wrong in at least one case.

Example: 5 weighings, 122 balls Yields 244 situations, 243 leaves, same problem, impossible.

Example: 5 weighings, 121 balls Yields 242 situations, 253 leaves, so ???

Well, Pigeonhole doesn’t rule this out, but it also doesn’t tell us it’s possible. For that, we’d have to construct an algorithm. LTTR

For here, consider easier case:

Example: 3 weighings, 13 balls 26 situations, 27 leaves, so Pigeonhole doesn’t say impossible.

But it turns out there’s still no algorithm. Reasons involve more detailed analysis: Proof by casees, based on first weighing.

First weighing can put some number n = 1, 2, 3, 4, 5, 6 on each pan.

n = 1: 11 balls not used. If first weighing comes out equal, leaves 22 possible situations. But only 2 weighings (9 leaves, could distinguish at most 9 situations).

n = 2, 3, 4: Same argument. n = 4 leaves 5 balls unused, 10 situations.

n = 6: If unbalanced, have 12 situations left (one of 6 L or one of other 6 H). Too many.

n = 5: Same argument.

3.4 Binary search

Random (living) person in the world is chosen randomly, by game server. Players ask yes/no questions to discover who it is. Fewest questions wins. HM questions needed?

Model game as a tree (draw)

Max number of questions is max length path in tree. Need each person alone at some leaf.

Binary, so need height at least ⌈log_{2}(N)⌉, where N is number of people (about 6 billion?). About 32 questions?

Is this sufficient? Yes. Unlike in weighing example, where questions were of a constrained form, here we can ask anything we like. E.g., order everyone in the world alphabetically, or some other way. Ask if in first half or second, split in half repeatedly. Boring questions, but does work in ⌈log_{2}(N)⌉.

Leads to binary search algorithm to find an element in a sorted list, w.r.t. a total order. Compare with middle element, and let result tell whether to proceed to look (recursively) in the top or bottom piece. Uses ⌈log_{2}(N)⌉ comparisons.

Can also show that this is approximately optimal (fudge factor because of the = case).

3.5 Example: Subsets of a List of Numbers

Show that any given 10 distinct positive numbers less than 100, that two completely different subsets sum to the same quantity.

The numbers all vary between 1 and 99. Therefore the maximum sum of any 10 chosen numbers is 90 + 91 + 92 + … 99 = 945. The number of different subsets of the 10 numbers is 2^{10} − 1 (excluding the null set) = 1023. We have 1023 pigeons and 945 holes. Using the pigeonhole principle, we can argue that two different subsets map to the same sum. If these subsets have a common number or numbers, we can always remove the common numbers to produce two completely different subsets that sum to the same quantity.