You have a function and want to prove it is a bijection. What can you do?

## ssr节点论坛

A bijection is defined as a function which is both one-to-one and onto. So prove that 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.

## ssr节点论坛

If and are finite and have the same size, it’s enough to prove *either* that is one-to-one, or that 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 and *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 to be onto, it “can’t afford” to send multiple elements of to the same element of , because then it won’t have enough to cover every element of . So it must be one-to-one. Likewise, in order to be one-to-one, it can’t afford to miss any elements of , because then the elements of have to “squeeze” into fewer elements of , and some of them are bound to end up mapping to the same element of . So it must be onto.

However, this is actually kind of tricky to formally prove! Note that the definition of “ and have the same size” is that there exists some bijection . A proof has to start with a one-to-one (or onto) function , and some *completely unrelated* bijection , and somehow prove that is onto (or one-to-one). Also, a valid proof must somehow account for the fact that this becomes false when and 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 defined by . 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 is one-to-one, and the finite size of is *greater than or equal to* the finite size of . The point is that being a one-to-one function implies that the size of is less than or equal to the size of , so in fact they have equal sizes.

## ssr节点论坛

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

…unless and are of the same finite size! In that case, it’s enough to show the existence of a one-sided inverse—say, a function such that . Then is (say) a one-to-one function between finite equal-sized sets, hence it is also onto (and hence 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 and 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 and are finite; otherwise you end up assuming what you are trying to prove.

## ssr节点论坛

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