properties of bijections
Let be sets. We write when there is a bijection from to . Below are some properties of bijections.
- 1.
. The identity function
is the bijection from to .
- 2.
If , then . If is a bijection, then its inverse function
is also a bijection.
- 3.
If , , then . If and are bijections, so is the composition
.
- 4.
If , , and , then .
Proof.
If and are bijections, so is , defined by
Since , is a well-defined function. is onto since both and are. Since are one-to-one, and , is also one-to-one.∎
- 5.
If , , then . If and are bijections, so is , given by .
- 6.
. The function given by is a bijection.
- 7.
If and , then .
Proof.
Suppose and are bijections. Define as follows: for any function , let . is a well-defined function. It is one-to-one because and are bijections (hence are cancellable). For any , it is easy to see that , so that is onto. Therefore is a bijection from to .∎
- 8.
Continuing from property 8, using the bijection , we have , , and , where , , and are the sets of injections, surjections
, and bijections from to .
- 9.
, where is the powerset of , and is the set of all functions from to .
Proof.
For every , define by
Then , defined by is a well-defined function. It is one-to-one: if for , then iff , so . It is onto: suppose , then by setting , we see that . As a result, is a bijection.∎
Remark. As a result of property 9, we sometimes denote the powerset of .