In this question, we will prove the following version of the pigeonhole principl

Question

In this question, we will prove the following version of the pigeonhole principle: For all n greaterthanorequalto 2, if f: {1, ..., n} rightarrow {1, ..., n - 1} is a function, then f is not injective. Consider the following predicate: P (n) = (For all f) (if f: {1, ..., n} rightarrow {1, ..., n - 1} is a function, then f is not injective) We will prove the claim by weak induction on n. The base case is n = 2. Write out all possible functions from {1, 2} to {1}. Show that P(2) is true. Fix n > 2. If f: {1, ..., n} rightarrow {1, ..., n - 1} is function, define the function g: {1, ..., n - 1} rightarrow {1, ..., n - 2} as follows: g (x) = {f (x) if f (x) 2 that P(n - 1) implies P(n) by showing the contrapositive.

Explanation / Answer

(a) When n = 2, there is only one possible mapping 1->1 and 2 -> 1.
(b) In the this case f is not injective, So P(2) is true. Let us assume we can prove it for n-1 and P(n-1) is true.
(c) f : {1,...,n} -> {1,....,n-1} and g:{1,...,n-1} -> {1,....,n-2}

   g(x) = (f(x) if f(x) < n-1) or (f(n) if f(x) = n-1}

As f is injective, g must be injective as for all values of x, we are mapping it with distinct values.

(d) From the above statement if P(n) is false then P(n-1) is false. But P(n-1) is true, so P(n) should be false.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.