Tutorial: Functions

2025-05-14

1 Injective, Surjective, Bijective

1.1 What classes are you taking?

Let \(C\) be the set of all classes offered at U of T in the summer.

Let \(S\) be the set of all students enrolled in U of T in this summer.

Let \(f: S \to \wp(C)\) be the function that maps a student \(x\) to the set of courses they are taking this summer.

  1. What is \(f(\)you\()\)? Dicuss with the person next to you.
  2. Is \(f\) injective?
  3. Is \(f\) surjective?
Solution
  1. Hopfully |\(f(\)you\()\)| is not too large so that you can still enjoy the summer!
  2. Probably not!
  3. Almost surely not!

1.2 Norm

Fix some \(n \in \mathbb{N}\), with \(n \geq 1\). Let \(||\cdot|| : \mathbb{R}^n \to \mathbb{R}_{\geq 0}\) defined by \[ ||\vec{x}|| = \sqrt{\sum_{i = 1}^n x_i^2} \]

  1. is \(||\cdot||\) injective?
  2. is \(||\cdot||\) surjective?
  3. is \(||\cdot||\) bijective?
Solution
  1. No, for example, if \(x = [0,1]\), and \(y = [1,0]\), then \(||x|| = ||y|| = 1\).
  2. Yes. Let \(a \in \mathbb{R}\). Then the vector \(\vec{x}\) have all zeros except for one non-zero value, \(a\). Then \(||\vec{x}|| = \sqrt{a^2} = a\). Hence \(||\cdot||\) is surjective.
  3. No, since it’s not injective.

2 Applications of the Pigeonhole Principle

2.1 Sock Picking

Imagine you have ten colors of socks in your sock drawer. You pull out one sock from the drawer at a time. What is the minimum number of socks you pull out before you are guaranteed two socks of the same color? Suppose the socks came in pairs so that you have at least 20 socks in total.

Solution
  1. Apply the Pigeonhole Principle with socks as pigeons and colors as pigeonholes.

2.2 Hand Shaking

Consider a social event with \(n\) people. Each person shakes hands with a certain number of other people throughout the event. Prove that there are always two people that have shaked hands with the same number of people.

You can try this out in small groups! You don’t actually have to shake hands - just pretend.

Solution

A person can shake hands with between \(0\) and \(n-1\) (inclusive) other people. Think of these numbers as the pigeonholes. Think of the people as pigeons. Note that there are \(n\) pigeonholes and \(n\) pigeons, so the Pigeonhole Principle doesn’t directly apply.

If you shook hands with \(n-1\) people, you shook everyone’s hand (except for your own). Therefore, no one shakes hands with \(0\) people because they at least shook your hand! Similarly, if you shook hands with \(0\) people, then no one shook hands with \(n-1\) people because they at least have not shook your hand! Therefore, at least one of the pigeonholes corresponding to \(0\) and \(n-1\) is empty.

Now apply the Pigeonhole Principle with \(n-1\) pigeonholes and \(n\) pigeons.

2.3 Birthdays

There are around 150 in CSC236. Show that at least 2 of us are born in the same month.

Apply the Pigeonhole Priciple to 150 pigeons and 12 months.

There are around 150 in CSC236 (including staff). Show that at least 13 of us are born in the same month.

3 Generalized Pigeonhole Principle

3.1 Generalized Pigeonhole Principle

Notation: \(\lceil x \rceil\) means \(x\) rounded up to the nearest integer.

Theorem 1 If there are \(m\) pigeons and \(n\) pigeonholes, no matter how we assign pigeons to pigeonholes, at least one pigeonhole will have at least \(\lceil m/n \rceil\) pigeons

Proof

Abbreviate \(\{1,...,n\}\) by \([n]\). Assign the \(m\) pigeons into the \(n\) pigeonholes.

Let for \(i \in [n]\) let \(x_i\) denote the number of pigeons in the \(i\)th pigeonhole. Note that \(m = x_1 + x_2 + ... + x_n\).

By contradiction, assume that for every \(i \in [n]\), \(x_i < \lceil m/n \rceil\). Since each of the \(x_i\) are integral (no fractional part), \(x_i < \lceil m/n\rceil\) implies \(x < m/n\). Then we have \[\begin{align} m &= x_1 + x_2 + ... + x_n\\ &< \underbrace{m/n + m/n +...+m/n}_{(n \text{ times})}\\ &= m. \end{align}\] \(m < m\) is a contradiction, so we are done.

3.2 Number of birthdays in the same month

There are around 150 in CSC236 (including staff). Show that at least 13 of us are born in the same month.

Solution

Think of the 150 people as pigeons and the 12 months as pigeonholes.

Apply the Generalized Pigeonhole Principle: No matter how we assign people to months, at least one month has at least \(\lceil 150/12 \rceil = 13\) people. In particular, this holds true when we assign people to their birth months.

4 Too few pigeons

4.1 Too few pigeons

The Pigeonhole Principle says that if there are more pigeons than pigeonholes, some pigeonhole will have at least two pigeons.

What if there are fewer pigeons than pigeonholes?

Solution No matter how you assign pigeons to pigeonholes, some pigeonhole will not have any pigeons!

4.2 Reverse Pigeonhole Principle*

Theorem 2 Let \(A, B\) be finite sets such that \(|A| < |B|\). Then there is no surjection from \(A\) to \(B\).

*This is not standard terminology

4.3 Contrapositives

Let \(A, B\) be finite sets

  • Pigeonhole Principle: \(|A|>|B| \implies \neg \exists\) injection \(f:A \to B\).
  • Reverse Pigeonhole Principle: \(|A|<|B| \implies \neg \exists\) surjection \(f:A \to B\).

Question: What are the contrapositives of the Pigeonhole Principle and the Reverse Pigeonhole Principle?

Solution

Pigeonhole Principle: \(\exists\) injection \(f:A \to B \implies |A| \leq |B|\)

Reverse Pigeonhole Principle: \(\exists\) surjection \(f:A \to B \implies |A| \geq |B|\)

4.4 A new way to compare sizes of sets

Given this, If I wanted to show that a set \(A\) is smaller than another set \(B\) without calculating the size of the sets, I could just find an injective function from \(A\) to \(B\).

In fact existing an injective function from \(A\) to \(B\) is how we define \(|A| \leq |B|\) for general (potentially infinite) sets.