Injections単射たんしゃ, surjections全射ぜんしゃ, and bijections全単射ぜんたんしゃ

1Introduction

For a map写像しゃぞう $$f:A\to B$$f:A\to B, the next questions are whether the map collapses information情報じょうほう and whether it reaches the whole codomain終域しゅういき.

An injection単射たんしゃ sends distinct inputs入力にゅうりょく to distinct outputs出力しゅつりょく. A surjection全射ぜんしゃ reaches every element元げん of the codomain. A bijection全単射ぜんたんしゃ has both properties and has an inverse map逆写像ぎゃくしゃぞう as a one-to-one correspondence.

An injection does not collapse information, while a surjection leaves no element of the codomain unused. A bijection has both properties, so its arrows can be read backward.

2Terms and definitions

A map写像しゃぞう $$f:A\to B$$f:A\to B is an injection単射たんしゃ if for all $$a_1,a_2\in A$$a_1,a_2\in A,

Equivalently, $$a_1\ne a_2$$a_1\ne a_2 implies $$f\left(a_1\right)\ne f\left(a_2\right)$$f(a_1)\ne f(a_2).

A map $$f:A\to B$$f:A\to B is a surjection全射ぜんしゃ if for every $$b\in B$$b\in B there exists $$a\in A$$a\in A such that $$f\left(a\right)=b$$f(a)=b. This is equivalent to $$f\left(A\right)=B$$f(A)=B.

A map $$f:A\to B$$f:A\to B is a bijection全単射ぜんたんしゃ if it is both an injection and a surjection.

3Strategy

To prove injectivity単射性たんしゃせい, assume $$f\left(a_1\right)=f\left(a_2\right)$$f(a_1)=f(a_2) and derive $$a_1=a_2$$a_1=a_2. This proves the direction “same output implies same input.”

To prove surjectivity全射性ぜんしゃせい, take arbitrary $$b\in B$$b\in B and construct $$a\in A$$a\in A satisfying $$f\left(a\right)=b$$f(a)=b. The important point is to start with an arbitrary element元げん of the codomain終域しゅういき $$B$$B.

To prove bijectivity全単射性ぜんたんしゃせい, either check injection and surjection separately, or construct an explicit inverse map逆写像ぎゃくしゃぞう.

4Intuitive explanation

An injection単射たんしゃ preserves distinctions on the input side. Different inputs入力にゅうりょく do not collapse to the same output出力しゅつりょく, so the output can distinguish the input.

A surjection全射ぜんしゃ covers the codomain終域しゅういき. Every element元げん declared in the codomain must actually be reached from some input.

A bijection全単射ぜんたんしゃ is a correspondence対応たいおう with no collisions and no unused codomain elements. For finite sets, the existence of a bijection corresponds to the two sets having the same number of elements.

In an arrow diagram, injectivity means that two input arrows never merge at one output, while surjectivity means that every codomain point has at least one incoming arrow.

5Counting viewpoint for finite sets

Let $$A,B$$A,B be finite sets有限集合ゆうげんしゅうごう. For finite sets, if $$C\subseteq B$$C\subseteq B, then $$\left|C\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|C|\le |B|, and equality implies $$C=B$$C=B. Indeed, after listing the elements of $$B$$B, the subset $$C$$C selects some of them; selecting the same number requires selecting all of them.

Also, $$\left|A\right|=\left|B\right|$$|A|=|B| is equivalent to the existence of a bijection全単射ぜんたんしゃ between $$A$$A and $$B$$B: list both sets in sequences of the same length and match equal positions. Conversely, a bijection matches elements without duplication or leftovers, so the two finite sets have the same number of elements.

If an injection単射たんしゃ $$f:A\to B$$f:A\to B exists, then $$f$$f is a bijection全単射ぜんたんしゃ between $$A$$A and its image像ぞう $$f\left(A\right)$$f(A). Hence

If a surjection全射ぜんしゃ $$f:A\to B$$f:A\to B exists, every preimage逆像ぎゃくぞう

is nonempty. These preimages are pairwise disjoint and their union和集合わしゅうごう is $$A$$A. If $$B=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$B=\varnothing, the existence of a map $$A\to B$$A\to B forces $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing, and the conclusion is immediate. If $$B\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$B\ne\varnothing, then $$A$$A is partitioned into $$\left|B\right|$$|B| nonempty parts, so $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B|.

In particular, suppose $$\left|A\right|=\left|B\right|$$|A|=|B|. If $$f:A\to B$$f:A\to B is injective, then $$\left|f\right(A\left)\right|=\left|B\right|$$|f(A)|=|B| and $$f\left(A\right)\subseteq B$$f(A)\subseteq B, so $$f\left(A\right)=B$$f(A)=B and $$f$$f is surjective. Conversely, if $$f$$f is surjective, it partitions $$A$$A into $$\left|B\right|$$|B| nonempty preimages whose sizes sum to $$\left|A\right|=\left|B\right|$$|A|=|B|. Every preimage must therefore contain exactly one element, so $$f$$f is injective.

Hence injectivity and surjectivity are equivalent for finite sets of the same size. This conclusion uses both finiteness and the hypothesis $$\left|A\right|=\left|B\right|$$|A|=|B|.

6Warning for infinite sets

For infinite sets無限集合むげんしゅうごう, injectivity and surjectivity need not be equivalent even when the domain and codomain have the same cardinality濃度のうど. Here let $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\}. The map $$s\left(n\right)=n+1$$s(n)=n+1 is an injection単射たんしゃ $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N, but it is not a surjection全射ぜんしゃ because $$1$$1 is not reached.

Conversely, $$q\left(n\right)=\lceil n/2\rceil$$q(n)=\lceil n/2\rceil is a surjection $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N because $$q\left(2m\right)=m$$q(2m)=m for every $$m\in \mathbb{N}$$m\in\mathbb N. It is not injective because $$q\left(1\right)=q\left(2\right)=1$$q(1)=q(2)=1. These examples show that both implications fail when the finiteness hypothesis is removed.

7Worked example: decide injection単射たんしゃ and surjection全射ぜんしゃ

7.1Problem

Let $$f:\{1,2,3\}\to \{a,b,c\}$$f:\{1,2,3\}\to\{a,b,c\} be defined by $$f\left(1\right)=a$$f(1)=a, $$f\left(2\right)=b$$f(2)=b, and $$f\left(3\right)=b$$f(3)=b. Decide whether $$f$$f is an injection単射たんしゃ, a surjection全射ぜんしゃ, or a bijection全単射ぜんたんしゃ.

7.2Explanation

We have $$f\left(2\right)=b$$f(2)=b and $$f\left(3\right)=b$$f(3)=b with $$2\ne 3$$2\ne3. Different inputs入力にゅうりょく are sent to the same output出力しゅつりょく, so $$f$$f is not an injection単射たんしゃ.

Also, for the codomain終域しゅういき element $$c$$c, there is no $$x\in \{1,2,3\}$$x\in\{1,2,3\} such that $$f\left(x\right)=c$$f(x)=c. Therefore $$f$$f is not a surjection全射ぜんしゃ.

Since a bijection全単射ぜんたんしゃ must be both injective and surjective, $$f$$f is not a bijection.

8How to identify them and related links

• For an injection単射たんしゃ, check whether any output collision occurs.
• For a surjection全射ぜんしゃ, check whether any codomain終域しゅういき element is missed.
• For a bijection全単射ぜんたんしゃ, check for both no collisions and no missed codomain elements.
• Changing the codomain can change whether surjectivity全射性ぜんしゃせい holds.

9Exercise links