Ways to prove a bijection

You have a function $f : A \to B$ and want to prove it is a bijection. What can you do?

By the book

A bijection is defined as a function which is both one-to-one and onto. So prove that $f$ is one-to-one, and prove that it is onto.

This is straightforward, and it’s what I would expect the students in my Discrete Math class to do, but in my experience it’s actually not used all that much. One of the following methods usually ends up being easier in practice.

By size

If $A$ and $B$ are finite and have the same size, it’s enough to prove either that $f$ is one-to-one, or that $f$ is onto. A one-to-one function between two finite sets of the same size must also be onto, and vice versa. (Of course, if $A$ and $B$ don’t have the same size, then there can’t possibly be a bijection between them in the first place.)

Intuitively, this makes sense: on the one hand, in order for $f$ to be onto, it “can’t afford” to send multiple elements of $A$ to the same element of $B$ , because then it won’t have enough to cover every element of $B$ . So it must be one-to-one. Likewise, in order to be one-to-one, it can’t afford to miss any elements of $B$ , because then the elements of $A$ have to “squeeze” into fewer elements of $B$ , and some of them are bound to end up mapping to the same element of $B$ . So it must be onto.

However, this is actually kind of tricky to formally prove! Note that the definition of “ $A$ and $B$ have the same size” is that there exists some bijection $g : A \to B$ . A proof has to start with a one-to-one (or onto) function $f$ , and some completely unrelated bijection $g$ , and somehow prove that $f$ is onto (or one-to-one). Also, a valid proof must somehow account for the fact that this becomes false when $A$ and $B$ are infinite: a one-to-one function between two infinite sets of the same size need not be onto, or vice versa; we saw several examples in my previous post, such as $f : \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 2n$ . Although tricky to come up with, the proof is cute and not too hard to understand once you see it; I think I may write about it in another post!

Note that we can even relax the condition on sizes a bit further: for example, it’s enough to prove that $f$ is one-to-one, and the finite size of $A$ is greater than or equal to the finite size of $B$ . The point is that $f$ being a one-to-one function implies that the size of $A$ is less than or equal to the size of $B$ , so in fact they have equal sizes.

By inverse

One can also prove that $f : A \to B$ is a bijection by showing that it has an inverse: a function $g : B \to A$ such that $g(f(a)) = a$ and $f(g(b)) = b$ for all $a \in A$ and $b \in B$ . As we saw in my last post, these facts imply that $f$ is one-to-one and onto, and hence a bijection. And it really is necessary to prove both $g(f(a)) = a$ and $f(g(b)) = b$ : if only one of these hold then $g$ is called a left or right inverse, respectively (more generally, a one-sided inverse), but $f$ needs to have a full-fledged two-sided inverse in order to be a bijection.

…unless $A$ and $B$ are of the same finite size! In that case, it’s enough to show the existence of a one-sided inverse—say, a function $g$ such that $g(f(a)) = a$ . Then $f$ is (say) a one-to-one function between finite equal-sized sets, hence it is also onto (and hence $g$ is actually a two-sided inverse).

We must be careful, however: sometimes the reason for constructing a bijection in the first place is in order to show that $A$ and $B$ have the same size! This kind of thing is common in combinatorics. In that case one really must show a two-sided inverse, even when $A$ and $B$ are finite; otherwise you end up assuming what you are trying to prove.

By mutual injection?

I’ll leave you with one more to ponder. Suppose $f : A \to B$ is one-to-one, and there is another function $g : B \to A$ which is also one-to-one. We don’t assume anything in particular about the relationship between $f$ and $g$ . Are $f$ and $g$ necessarily bijections?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

7 Responses to Ways to prove a bijection

Callan says:

March 17, 2020 at 12:31 pm

Cheeky example: S: Nat -> Nat is injective so take f = g = S!
- Brent says:
  
  March 17, 2020 at 7:49 pm
  
  By S do you mean the successor function? That’s a good example, not cheeky at all!
Pingback: Not injective, not surjective, but bijective – The nth Root
designerspaces says:

March 18, 2020 at 4:00 pm

I did mean successor, yes!
blaisepascal2014 says:

March 18, 2020 at 9:32 pm

If $f:A\to B$ is one-to-one, then $|A| \geq |B|$ . Similarly, if $g:B\to A$ , then $|B| \leq |A|$ . If both are true, then $|A| = |B|$ and a bijection exists between $A,B$ , but there’s no guarantee that either $f,g$ are bijections.

If $A,B$ are finite, then (as you argued in “By Size”), both $f,g$ are bijections. But if they are infinite, then there are $f$ that are one-to-one, but not onto. Proof: Since $B$ is infinite, there exists a $h:B\to B$ that is one-to-one but not onto, so if $f':A\to B$ is one-to-one, then $f:A\to B = h\circ f'$ is one-to-one, but not onto.

This is one of my favorite ways to show $|A| = |B|$ . It usually isn’t hard to come up with the necessary injections, even if it is hard to find a bijection. It is easy to show that $f:\mathbb{N}\to\mathbb{N}^2, f(n) = (n,0)$ and $g:\mathbb{N}^2\to\mathbb{N}, g(a,b) = 2^a3^b$ are both one-to-one, It is harder to come up with an easy-to-describe bijection.
- Brent says:
  
  March 19, 2020 at 8:56 am
  
  Indeed! I think I will probably write about this in an upcoming post. One fun thing is that the proof of the Schröder-Bernstein theorem is actually constructive, so in theory you can take any two injections and actually use them to construct a bijection. But indeed, there is no guarantee that the resulting bijection is easy to describe. I am still trying to work out how to describe the one generated by your pair of injections between $\mathbb{N}$ and $\mathbb{N}^2$ . It’s something like this: any number can be written in the form 2^2^…^m where $m$ is not a power of two, that is, a tower of zero or more 2’s with a final power of $m$ on top. (If $n$ is not a power of two then $m = n$ .) If $m = 0$ or $m$ has prime factors other than 2 or 3, then send $n$ to $(n,0)$ . Otherwise, if $n$ is a power of two, send it to $\log_2(n)$ ; finally, if $n = m = 2^j 3^k$ , send it to $(j,k)$ . It’s very non-obvious that this is a bijection (and I might have even gotten the description wrong)!
Pingback: Competitive programming in Haskell: permutations | blog :: Brent -> [String]