Skip to main content

Section 5.6 Bijections

One important kind of map is the bijection. When mathematicians are presented with a set, for many purposes, they won't be too very worried about what the elements are, but what structures they have.

The idea is that a bijection of sets is meant to be a “mere labelling” of the elements of a set \(S\) by the elements of a set \(T\text{.}\) That labelling is meant to be a perfect match of information: you should never use the same label twice, and all the labels should be used. So a bijection of sets is a map \(f\colon S \to T\) such that for any \(t\in T\text{,}\) there exists a unique \(s\in S\) such that \(f(s)=t\text{.}\)

Let \(S\) and \(T\) be two sets. There is a bijection \(\sigma \colon S \times T \to T \times S\text{,}\) which is given by \(\sigma(\angs{s,t}) = \angs{t,s}\text{.}\)

If \(f \colon S \to T\) is a bijection, then there exists a map \(g \colon T \to S\) such that \(g \circ f = \id\text{,}\) and \(f \circ g = \id\text{.}\) To prove this, let us construct \(g\text{:}\) the function \(f\) gives us a subset \(\Gamma(f) \subseteq S \times T\) such that for any \(s \in S\text{,}\) there exists a unique \(t \in T\) such that \(\angs{s, t} \in \Gamma(f)\text{.}\) So now let's define \(g = \angs{T, S, \Gamma(g)}\text{,}\) where \(\Gamma(g) = \{ \angs{t,s} \in T \times S : \angs{s, t} \in \Gamma(f) \}\text{.}\) Of course \(\Gamma(g)\) makes perfect sense as a subset, but we aren't done: we have to show it is a map from \(S\) to \(T\text{.}\) For this we can use the fact that, since \(f\) is a bigjection, for every \(t \in T\text{,}\) there exists a unique \(s \in S\) such that \(\angs{s,t} \in \Gamma(f)\text{.}\) In other words, for every \(t \in T\text{,}\) there exists a unique \(s \in S\) such that \(\angs{t,s} \in \Gamma(g)\text{.}\) Thus if \(t \in T\text{,}\) then \(g(t) \in S\) is the unique element such that \(f(g(t) = t\text{.}\) Thus \(f \circ g = \id\text{.}\) To see that \(g \circ f = \id\text{,}\) let \(s \in S\text{;}\) then \(g(f(s)) \in S\) is the unique element such that \(f(g(f(s))) = f(s)\text{.}\) But since this element of \(S\) is unique with this property, it follows that \(g(f(s)) = s\text{.}\)

The converse is also correct: if \(f \colon S \to T\) is a map such that there exists a function \(g \colon T \to S\) such that \(g \circ f =\id\) and \(f \circ g = \id\text{,}\) then \(f\) is a bijection. Indeed, let \(t \in T\) be an element; we aim to prove that there exists a unique element \(s \in S\) such that \(t = f(s)\text{.}\) The function \(g\) provides us with exactly such an element: \(g(t) \in T\) is an element, and \(t = f(g(t))\text{.}\) Now suppose that \(s'\in S\) is an element such that \(t = f(s')\text{;}\) we see that \(g(t) = g(f(s')) = s'\text{,}\) so we have the uniqueness we sought!

In this case, we say that \(g\) is the inverse of \(f\text{,}\) and we sometimes write \(f^{-1}\) for \(g\text{.}\)

Let \(S\) and \(T\) be two sets. Assume that \(f \colon S \to T\) is a bijection between them. Now let \(U\) be another set. We can define a map \(F \colon \Map(T, U) \to \Map(S, U)\) by the assignment \(\alpha \mapsto \alpha \circ f\text{.}\) Let's see that this is a bijection. If \(g = f^{-1} \colon T \to S\) is the inverse to \(f\text{,}\) then we can define a map \(G \colon \Map(S, U) \to \Map(T, U)\) by the assignment \(\beta \mapsto \beta \circ g\text{.}\) Now \(F \circ G = \id\) and \(G \circ F = \id\text{.}\)