基本編第4話で説明した通り、写像が「全射」であるとは「すべての元に対応付けられていること」で、「単射」であるとは「対応付けに重複がないこと」で、「全単射」であるとは「全射かつ単射であること」でした。
特に、全単射であるとき、写像は元が1対1で対応付けられることになるのでした。
ただ、元の個数が有限である「有限集合」のときは問題ありませんでしたが、元の個数が無限である「無限集合」の場合には、そのような元の対応付けを1つずつ行えるとは限らないため、より一般化した定義で扱われます。
今回は、無限集合における全射、単射、全単射について説明します。
1写像の像
さて、全射、単射、全単射を一般化する前に、準備として写像の「像」というものを考えます。
写像「
」の「像」とは、「写像によって対応付けられたの元を集めた集合」のことです(図1-1)。
」の「像」とは、「写像によって対応付けられたの元を集めた集合」のことです(図1-1)。
このの像を、「
」と表記します。
の像を、「」と表記します。補足
写像の像は「f(X)」と表記されることもありますが、元と元の対応と混同しやすいため、本講座では「f[X]」で統一します。
の像「」は、当然ながらに含まれます。 すなわち、「
」です。また正確には、の像「」とは「
」のように定義されます。 「のすべての元に対し、を集めた集合」という意味です。
の像「」とは「」のように定義されます。 「のすべての元に対し、を集めた集合」という意味です。2全射、単射、全単射
それでは、全射、単射、全単射を一般化して定義しましょう。
2.1全射
写像が全射であるとは、図2-1と定義されます。
写像が全射であるとは、以下が成り立つことである。
つまり、写像の像がと一致していることを全射といいます。 写像の像がと一致していることは、のすべての元に対応付けられていることといえます。
がと一致していることを全射といいます。 写像の像がと一致していることは、のすべての元に対応付けられていることといえます。2.2単射
写像が単射であるとは、図2-2と定義されます。
写像が単射であるとは、以下が成り立つことである。
つまり、の任意の元
に対し、「のときが必ず成り立つこと」を単射といいます。 言い換えると、対応付けの先が重複している()のに、対応付けの根本が異なる(
)ものがあれば、単射ではないとしています。
の任意の元に対し、「のときが必ず成り立つこと」を単射といいます。 言い換えると、対応付けの先が重複している()のに、対応付けの根本が異なる()ものがあれば、単射ではないとしています。2.3全単射
写像が全単射であるとは、図2-3と定義されます。
写像が全単射であるとは、以下が成り立つことである。
- が全射かつ単射である。
有限集合では、全単射は「元が1対1で対応する」と言えましたが、無限集合ではそのように感覚的に考えられない場合があります。
2.4例
例えば、整数全体の集合
から、偶数全体の集合
への写像「」があり、「
」だとします(図2-4)。
から、偶数全体の集合への写像「」があり、「」だとします(図2-4)。
この場合、写像の像は偶数全体の集合と一致するため、は全射です。 また、任意の整数に対し、「のとき」が成り立つため、は単射です。 よっては全射かつ単射のため、結局は全単射です。
は偶数全体の集合と一致するため、は全射です。 また、任意の整数に対し、「のとき」が成り立つため、は単射です。 よっては全射かつ単射のため、結局は全単射です。3空集合の写像
空写像についてはややこしいため、念のため確認しておきましょう。
このとき、空写像には対応付けがありませんので、がどんな集合であっても、空写像「
」の像は空集合となり、すなわち「」となります。
には対応付けがありませんので、がどんな集合であっても、空写像「」の像は空集合となり、すなわち「」となります。もしも空集合であれば、の像がと一致するため、は全射となります。 が空集合でなければ、の像がと一致しないため、は全射にはなりません。
も空集合であれば、の像がと一致するため、は全射となります。 が空集合でなければ、の像がと一致しないため、は全射にはなりません。また、の対応付けの先の元に重複はないため、が空集合かどうかにかかわらず、は単射です。
の対応付けの先の元に重複はないため、が空集合かどうかにかかわらず、は単射です。結局、空写像「」について、「が空集合のときは全単射」となり、「が空でないときは全射ではなく単射である」と言えます。
」について、「が空集合のときは全単射」となり、「が空でないときは全射ではなく単射である」と言えます。4重要な定理
最後に、写像にかかわる重要な定理を紹介します。
4.1全単射と逆写像の定理
まず、図4-1の定理です。
「写像が全単射であること」と「写像に逆写像が存在すること」は同値である。 また、写像の逆写像は全単射である。
つまり、写像が全単射であればに逆写像が存在し、に逆写像が存在すればは全単射といえます。
が全単射であればに逆写像が存在し、に逆写像が存在すればは全単射といえます。例えば、整数全体の集合から、偶数全体の集合への写像「」があり、「」だったとします。 このとき、先ほど確認した通り、は全単射になります。 この場合、この定理を使うと、は全単射なので「には逆写像が存在する」といえます。 そして、その「の逆写像は全単射である」といえます。
から、偶数全体の集合への写像「」があり、「」だったとします。 このとき、先ほど確認した通り、は全単射になります。 この場合、この定理を使うと、は全単射なので「には逆写像が存在する」といえます。 そして、その「の逆写像は全単射である」といえます。確かに「
」という写像を考えると、これはの逆写像で、が全単射であることも確認できるため、定理を満たしていることが分かります。
」という写像を考えると、これはの逆写像で、が全単射であることも確認できるため、定理を満たしていることが分かります。補足
証明は、付録に掲載しています。
4.2シュレーダー・ベルンシュタインの定理
次は、「シュレーダー・ベルンシュタインの定理」と呼ばれる図4-2の定理です。
集合に対し、単射「」「
」が存在するとき、全単射「
」が存在する。
つまり、「双方向に単射が存在するとき、全単射が存在する」という定理です。
例えば、集合を「
以上
以下の実数全体」とし、集合を「以上以下の実数全体」とします。 このとき、写像を考えて、「」「
」とすると、はそれぞれ対応付けに重複がないため単射となります。 すると、この定理により、とには全単射が存在するといえます。
を「以上以下の実数全体」とし、集合を「以上以下の実数全体」とします。 このとき、写像を考えて、「」「」とすると、はそれぞれ対応付けに重複がないため単射となります。 すると、この定理により、とには全単射が存在するといえます。