全単射

1 定義

全単射は、集合どうしの対応を記述する写像の基本概念である。ある集合から別の集合へ各要素を割り当てるとき、重複なく、しかも取りこぼしなく対応が成立していれば、その写像は全単射と呼ばれる。これは単射と全射の両方を満たす場合に当たる。

1.1 写像の基礎

写像とは、始域の各元に対して、終域のちょうど一つの元を対応させる規則である。たとえば、集合 \(A\) の各要素に対し、集合 \(B\) の要素を一つずつ割り当てるとき、その対応全体を \(A\) から \(B\) への写像という。ここで重要なのは、始域の各元に対する対応が一意である点である。

1.2 単射の定義

単射は、異なる元が異なる像をもつ写像である。つまり、始域で別々の二つの元をとると、終域でも同じ元に対応しない。言い換えると、像の重なりが起こらないような写像である。

1.3 全射の定義

全射は、終域のすべての元が少なくとも一度は像として現れる写像である。始域からの対応によって、終域に「使われない」元が残らない。この性質は、対応が終域全体を覆うことを意味する。

1.4 全単射の定義

全単射は、単射であり同時に全射でもある写像である。したがって、始域の各元は互いに区別されて終域の各元へ対応し、終域側の各元も必ずどれか一つの始域の元に結びつく。結果として、両集合の要素が一対一で対応する。

2 性質

全単射には、逆向きの対応を作れること、写像の合成で安定に振る舞うこと、恒等写像と深く関係することなど、基本的だが重要な性質がある。これらは、集合の比較や構造の同一視において中心的な役割を果たす。

2.1 逆写像の存在

全単射では、各終域の元に対応する始域の元がただ一つ定まるため、逆向きの写像を定義できる。この逆写像は、もとの写像と組み合わせると元の要素をそのまま戻す働きをもつ。逆写像が存在することは、全単射を特徴づける重要な性質である。

2.2 合成写像との関係

全単射は、他の写像と合成しても性質を保ちやすい。前後に全単射を組み合わせると、全体としての対応関係も整然としたまま維持される。写像の合成は、変換を連続して行う操作として理解されるため、この安定性は実用上も有用である。

2.2.1 単射との関係

全単射の合成では、構成要素の単射性が結果に反映される。とくに、一方の写像が単射で、もう一方が全単射であるとき、合成写像の重複の有無を追跡しやすい。全単射は、単射の性質を壊さずに写像を変換する枠組みを与える。

2.2.2 全射との関係

全単射の合成では、終域全体を覆う性質も保たれる。写像の途中に全単射が入っていても、対応の漏れは生じにくい。こうした性質により、対象の範囲を保ったまま別の表現へ移し替えることができる。

2.3 恒等写像との関係

恒等写像は、各元を自分自身に対応させる写像である。全単射とその逆写像を合成すると、恒等写像が現れる。これは、全単射が完全な一対一対応であることを端的に示す関係である。

3 例

全単射は、有限集合でも無限集合でも見られる。具体例を通じて考えると、重複のない対応と漏れのない対応がどのように両立するかが理解しやすい。

3.1 有限集合における例

三つの要素をもつ集合 \(A=\{1,2,3\}\) から、別の三要素集合 \(B=\{a,b,c\}\) へ、1をa、2をb、3をcに対応させる写像は全単射である。各元が一度ずつ使われ、余りも重複もないためである。順序を入れ替えた対応でも、同じ条件を満たせば全単射になる。

3.2 無限集合における例

自然数全体の集合と偶数全体の集合は、一見すると後者の方が小さく見えるが、\(n\mapsto 2n\) によって全単射が与えられる。これにより、無限集合では直感的な大小関係だけでは要素数を比較できないことがわかる。全単射は、無限集合の同じ「大きさ」を示す手段として機能する。

3.3 全単射でない写像の例

\(A=\{1,2,3\}\) から \(B=\{a,b\}\) への写像で、1と2をaに、3をbに対応させると、異なる元が同じ像をもつため単射ではない。一方、\(A=\{1,2\}\) から \(B=\{a,b,c\}\) へ1をa、2をbに対応させる場合は、cが対応しないので全射ではない。いずれも全単射にはならない。

4 応用

全単射は、集合の要素数比較だけでなく、数学的対象の同一性や計算上の対応付けを考える場面でも使われる。対象を別の形に置き換えても本質が変わらないことを示す道具として重要である。

4.1 集合の濃度の比較

二つの集合の間に全単射が存在するとき、それらは同じ濃度、すなわち同じ要素数の「大きさ」をもつとみなされる。有限集合では通常の個数比較に一致し、無限集合では集合の大きさを定義する基準として働く。全単射は、濃度の等しさを厳密に表現する。

4.2 数学的構造の同値性

群、環、ベクトル空間などでは、全単射が構造を保つ条件と結びつくと、二つの対象が本質的に同じであると判断できる。単なる要素の置き換えではなく、演算や関係を保ったまま対応づけられるとき、同型性の議論が成立する。全単射は、その基礎となる対応の形を与える。

4.3 計算機科学における対応付け

計算機科学では、全単射はデータの再番号付け、符号化、索引変換などに利用される。入力と出力の対応を重複なく整理したい場合や、ある表現を別の表現へ一対一で移したい場合に有効である。アドレス変換や置換処理の理解にもつながる。