|| 何かと何かの結びつき
基本的な知識は『集合論』のページで解説してます
スポンサーリンク
目次
写像「感覚的にはフィルターみたいなもの」
単射「一個一個繋がってる感じの写像」
全射「被ってでも全部繋がってる写像」
全単射「被りもなく要素が一対一で繋がってる写像」
部分写像「部分的に写らせるやつ」
逆写像「写像と像から得られる逆の処理」
恒等写像「変化しない写像」
合成写像「経由する感じの写像」
概要
「写像」についての基本知識については
\begin{array}{lcl} 写像 && 集合と集合を結ぶヒモの集まり \\ \\ 関係 && 集合の中身同士の対応 \\ \\ 定義域と始域 && 写像の記号表現 \to の左側 \\ \\ 値域（像か終域） && 写像の記号表現 \to の右側 \\ \\ 逆像 && 像から写像を見た時の始域の一部 \end{array}
ざっと整理するとこんな感じです。
（この辺りの詳細は集合論の概要でまとめてます）
写像という概念の原型
これの「原型となる感覚」は『因果関係』で
\begin{array}{lcl} 因果関係の感覚 &\to& 前後の結び付き \\ \\ &\to& 数値で厳密化したのが関数 \\ \\ &\to&集合による関数の一般化が写像 \end{array}
「写像」はこの一般形になります。
（集合の文脈で厳密に整備された成果）
写像 Mapping
|| 何かの中身と何かの中身を接続するもの
「関数」の感覚を一般化したもの
\begin{array}{lcl} f(a)&=&b \\ \\ F(A)&=&B \end{array}
「関数 f 」は「１つの要素」しか出力しませんが
「写像 F 」は「集合」を出力することがあります。
（写像の存在は公理により保証される）
写像の中身と制限
この中身を定める要請は
「整論理式」で与えられていて
\begin{array}{ccc} (x,y)\in f &\Longleftrightarrow& φ(x,y) & \left\{ \begin{array}{cl} &x=1\to y=2 \\ \\ ∨ & x=2\to y=4 \\ \\ ∨ & x=3\to y=9 \\ \\ \vdots \end{array} \right. \end{array}
その中身はこんな感じになっています。
（厳密には論理式は要請であって集合ではない）
またこれには
\begin{array}{ccc} (x,y_1)\in f∧(x,y_2)\in f &\Longrightarrow& y_1=y_2 \end{array}
「ある x から同時に違う結果にならない」という
（定義域の要素 x 側から伸びる線は１本だけ）
\begin{array}{ccc} (x=1→y=2)∨(x=1\to y=3) && × \end{array}
『写像であるための要請』が与えられていて
「定義域の要素から」は『１つの像』しか得られません。
（写像かどうかはこれだけ確認すればいい）
意味のある写像
「写像」はとても広い意味を持つので
「大半の写像」には意味がありません。
\begin{array}{c} 1&→&10 \\ \\ 2&→&13 \\ \\ 3&&18 \end{array}
例えばこういう
「特に規則性の無い写像」は確かに存在しますが
「作れる」けど『使用用途が無い』
\begin{array}{ccc} 写像 & \left\{ \begin{array}{lcl} 使える写像 && 特定の性質持ち \\ \\ 使うかもしれない写像 && 具体的 \\ \\ 使えない写像 && 複雑で不規則 \end{array} \right. \end{array}
だから「写像」と言っても
実際に使われるのは少数で
\begin{array}{llllllllll} \displaystyle a_1≠a_2→f(a_1)≠f(a_2) &&\mathrm{Injection} & 単射 \\ \\ f(A)=B &&\mathrm{Surjection} &全射 \\ \\ f(a_n)=b_n && \mathrm{ Bijection } & 全単射 \\ \\ \\ f(a)=a && \mathrm{Identity} & 恒等写像\\ \\ f^{-1}(b)=a && \mathrm{ Inverse } & 逆写像 \\ \\ g(f(a)) = g(b)=c && \mathrm{Composition} &合成写像 \end{array}
この 6 つ以外を見ることはほとんどありません。
（無いことはないけどほぼこのどれか）
集合から見た写像
これは少し実感し辛いかもしれませんが
\begin{array}{ccc} f(x)=y&→&(x,y) \end{array}
「写像」という概念は
『対・組』の「集合」として実は定義されていて
（ x と y を接続するものであることから）
\begin{array}{ccc} x \in X &&→&& \exists y\in Y \,\, (x,y) \in f \\ \\ (x,y_1) \in f ∧(x,y_2) \in f &&→&& y_1=y_2 \end{array}
このような条件を満たす f として
（ x に対応する y は１つだけ）
\begin{array}{ccc} f&:=&\{ (x,y) \mid x\in X∧y\in Y \} \end{array}
「写像 f 」と「対の集合 f 」は同一視されています。
（同一視しなければ存在が保証されない）
写像の同一性と集合
この同一視は非常に都合が良くて
（都合が良くなるように整理されてる）
\begin{array}{ccc} \forall x\in X &f(x)=g(x) \end{array}
「対の集合の中身が同じ」である場合
「写像 f 」は「対の集合 f 」として
\begin{array}{ccc} (x,y) \in f &→& (x,y) \in g \\ \\ (x,y) \in f &←& (x,y) \in g \end{array}
『同一である』という評価が可能になります。
（外延性の公理で同一性を保証できる）
他は省略しますが
結果的に『全ての写像の性質』が満たされるので
（基礎が集合として定まってるのでほぼ明らか）
\begin{array}{ccc} f&:=&\{ (x,y) \mid x\in X∧y\in Y \} \end{array}
「写像」をこのように定義するのは妥当だと言えます。
（より正確にはこうなるよう公理が調整されている）
関係と写像
↑ の同一視による定義は
\begin{array}{ccc} R_f&=&\{ (x,y) \mid f(x)=y \} \end{array}
「二項関係 R 」でもそのまま適用できて
\begin{array}{ccc} x \in X &&→&& \exists y\in Y \,\, (x,y) \in R_f \\ \\ (x,y_1) \in R_f ∧(x,y_2) \in R_f &&→&& y_1=y_2 \end{array}
これもまた「関係 R を意味する集合」として
\begin{array}{ccc} f&:=& (X,Y,R_f) \end{array}
「３つ組」で定義できます。
確認しておくと
\begin{array}{ccc} x \in X &&→&& \exists y\in Y \,\, (x,y) \in R_f \\ \\ (x,y_1) \in R_f ∧(x,y_2) \in R_f &&→&& y_1=y_2 \\ \\ \\ x \in X &&→&& \exists y\in Y \,\, (x,y) \in R_g \\ \\ (x,y_1) \in R_g ∧(x,y_2) \in R_g &&→&& y_1=y_2 \end{array}
これも「写像」と同様
\begin{array}{lcl} R_f&=&\{ (x,y) \mid f(x)=y \} \\ \\ R_g&=&\{ (x,y) \mid g(x)=y \} \end{array}
『集合の同一性公理』により
\begin{array}{ccc} (X,Y,R_f)=(X,Y,R_g)&&→&&f=g \\ \\ (X,Y,R_f)=(X,Y,R_g)&&←&&f=g \end{array}
このような形で「同一性」が担保されます。
（ ↑ でも言いましたがこうなるように調整されている）
写像の具体的な中身
念のため具体的な話をしておくと
\begin{array}{ccl} N&=&\{1,2,3,...,n\} \\ \\ A&=&\{a_1,a_2,a_3,...,a_n\} \\ \\ R_f&=&\Bigl\{ (1,a_1),(2,a_2),(3,a_3),\cdots,(n,a_n) \Bigr\} \end{array}
これはこんな感じの
\begin{array}{ccc} f&:&N&\to&A \\ \\ && n&\to&a_n \end{array}
『好きな対応』を作れるので
\begin{array}{ccc} f &:=&\Bigl( f(1),f(2),...,f(n) \Bigr) \\ \\ &=& (a_1,a_2,...,a_n) \end{array}
かなり柔軟な操作を保証してくれます。
（ f の対応を個別に取り出して扱える）
単射 Injection, Injective Function
|| 一個一個が紐づいてるシンプルな感覚
「１対１の写像」と呼ばれることもある写像
\begin{array}{llllll} 1 & → & 5 \\ \\ 2 &→& 6 \\ \\ 3 &→& 7 \\ \\ &&8 \end{array}
\mathrm{Injection} だけではなく
\mathrm{One\,to\,One\,Mapping} という名前もあります。
（定義域の側だけで決められる写像）
単射の厳密な定義
最もシンプルかつ実用的で感覚的な写像
\begin{array}{ccc} a≠b &\to& f(a)≠f(b) \end{array}
その『整理した結果』が「単射」で
\begin{array}{c} ∀a,b \in S &\Bigl( & a≠b & \to & f(a)≠f(b) & \Bigr) \end{array}
「集合モデル」の範囲ではこの定義で良いです。
（感覚的にもこちらの方がベースになる）
補足しておくと
『集合モデルの範囲外』で考えるなら
\begin{array}{ccc} fは単射 &\Longleftrightarrow& fの像が一致するなら引数は一致 \\ \\ &\Longleftrightarrow& f(a)=f(b) \,\, ⇒ \,\, a=b \end{array}
このような『要請的定義』が必要になります。
（これはモデルの外で必要になる量化が許されない定義）
単射の定義手順
「否定の排除」はこれに限った話ではないんですが
\begin{array}{lcl} 否定がある形 && ドメイン内を全部調べる \\ \\ 否定が無い形 && 個別の比較ができる \end{array}
『単射』の厳密な定義の形もこの例に漏れず
\begin{array}{ccc} 1対1対応 &\to& 引数1つに像1つが対応 \\ \\ &\to& a≠b \,\, ⇒ \,\, f(a)≠f(b) \\ \\ &\to& 否定を排除する \\ \\ &\to& 像から引数を特定できる \\ \\ &\to& f(a)=f(b) \,\, ⇒ \,\, a=b \end{array}
「否定が取り除かれた形」が基本形になります。
（なので単射というとだいたいこっちの形を使う）
両者の定義の関係
確認しておくと
\begin{array}{ccc} \mathrm{N} && a≠b &\to& f(a)≠f(b) \\ \\ \mathrm{P} && f(a)=f(b) &\to& a=b \end{array}
『 \mathrm{N}\to \mathrm{P} \to \mathrm{N} の順で確認する』とするなら
\begin{array}{ccl} \mathrm{N}を真とする &\to& a≠bが前提 \\ \\ &\to& f(a)=f(b)になると仮定する \\ \\ &\to& この仮定は\mathrm{N}に矛盾する \\ \\ &\to& f(a)=f(b)になるにはa=b 以外無い \\ \\ &\to& \mathrm{P} が導かれる \end{array}
まずこちら側はこうなり
\begin{array}{ccl} \mathrm{P}を真とする &\to& f(a)=f(b)が前提 \\ \\ &\to& a≠bになると仮定する \\ \\ &\to& この仮定は\mathrm{P}に矛盾する \\ \\ &\to& a≠bになるにはf(a)≠f(b)以外無い \\ \\ &\to& \mathrm{N} が導かれる \end{array}
こっちはこうなるので
結果、同値であることが導かれます。
補足しておくと
\begin{array}{ccc} a≠b &∨& a=b \\ \\ f(a)=f(b) &∨& f(a)≠f(b) \end{array}
やってることは２分割の総当たりで
（片側から見たもう片側の話をしてる）
\begin{array}{lcl} \mathrm{N} & ⇒& f(a)=f(b) になるならa=bのパターンしかない \\ \\ \mathrm{P} &⇒& a≠bになるならf(a)≠f(b) のパターンしかない \end{array}
証明の手順はこのようになっています。
（１方向の保証が両側で確認できるから同値）
全射 Surjection, Onto Function
|| なんでも良いから全部繋がってる感覚
「被っても良い」から『全部写る』ような写像
\begin{array}{c} α & → & β \\ \\ a &→& b \end{array}
こういう形の写像や
（全単射の解体の結果）
\begin{array}{c} a & → & α \\ \\ b &→& β \\ \\ c &→& α \end{array}
こういう写像が「全射」になります。
（ \mathrm{ Onto\,Mapping } とも呼ばれる）
全射の厳密な定義
これは少しややこしいですが
\begin{array}{ccc} f(A)&=&B \end{array}
大雑把にはこんな感じなので
\begin{array}{ccc} 全てのAの要素 &\to& 全てのBの要素 \end{array}
「全ての b に」対して
「 b に紐づく a が必ず存在する」
\begin{array}{c} ∀b∈B & ∃a∈A & \Bigl( & f(a)=b & \Bigr) \end{array}
これが厳密な定義になります。
（全に制限が無ければモデル外では扱えない）
全射と写像の定義
この『全射』という形は
だいたい「写像 f の定義段階」で決まるもので
\begin{array}{ccc} Y&=&\mathrm{Image}(f) \\ \\ && \mathrm{Image}(f) &=& \{ y\in U \mid \exists x \in X \,\, (x,y)\in f \} \end{array}
例えばこのように『像 f(x) の集合』とすれば
自動的に「全射」になります。
これは一見すると循環定義に見えますが
（ f の終域 Y を f で定義してるように見える）
\begin{array}{ccl} 定義域Xが決まる &\to& 写像fが決まる \\ \\ &\to& 像f(x)を全て持つ終域を選択 \\ \\ &\to& 仮の終域の最大範囲は宇宙U \\ \\ &\to& f \subset X\times U で定義できる \\ \\ \\ &\to& 終域を狭めて無駄を省きたい \\ \\ &\to& 仮の終域から像yだけ抜き出す \\ \\ &\to& f\subset X\times Y で定義できる \end{array}
順序としてはこんな感じです。
（つまり像の集合 Y による定義は終域の再定義）
全単射 Bijection, Bijective Function
|| １つ１つが全部繋がってる感覚
「全て」「被りなく」繋がってる写像
\begin{array}{c} 1&\to&5 \\ \\ 2&\to&6 \\ \\ 3&\to&7 \end{array}
「一対一対応」と呼ばれることもあります。
（ \mathrm{ One\,to\,One\,Onto\,Mapping } とも呼べるが見ない）
全単射の厳密な定義
これは整理された結果ですが
「全射であり」かつ「単射である」写像が
\begin{array}{c} ∀b∈B & ∃_1a∈A&\Bigl( &f(a)=b &\Bigr) \end{array}
「全単射」と呼ばれる写像の定義になります。
（ ∃!,∃_1 は唯一存在することを表す記号）
使用頻度と原型感覚
これは使用頻度を比較すると
\begin{array}{c} \mathrm{ one\,to\,one\,onto } &>& \mathrm{ one\,to\,one } &>>& \mathrm{ onto } \end{array}
こんな感じなんですが
\begin{array}{lcl} 要素が全て一致 &\to& ２つが同じ \\ \\ 要素が全て一致 &←& 欲しい結論 \end{array}
これは「全単射の感覚」が
『同じという感覚』の根拠になるためで
（何かを何かで説明する時に同一視を用いる）
\begin{array}{lcl} ほぼ同じ &\to& 対応付けできない要素がある \\ \\ &\to& どうあっても同じにはならない \end{array}
逆に「単射」は『違う』の根拠になるためです。
（確定で単射だから違うと分かる）
同じと全単射
人間の「同じ」という感覚は
「全単射」の感覚に近いですが
\begin{array}{ccc} 同じ &\Longleftrightarrow& 両者の要素が全て一致 \end{array}
『全単射の成立条件』は「非常に厳しい」です。
（集合モデル上でしか成立しない上に更に厳しい）
\begin{array}{ccc} 同じという錯覚 & \left\{ \begin{array}{lcl} ほとんど全射の単射 \\ \\ 被りがほとんどない全射 \end{array} \right. \end{array}
なのでこの事実を写像の文脈で考えると
実際的な「同じ」が『錯覚』であることが分かります。
（現実的には似ているだけで「同じ」はまず成立しない）
部分写像 Partial Mapping
|| 写像の一部を切り抜いたやつ
これは「全域写像」と区別するための概念で
\begin{array}{ccc} 写像fが存在 &\to& 定義域が狭いfも存在 \end{array}
「集合」の「部分集合」という概念を
\begin{array}{lcl} xの定義域X &\to& Xの部分集合 \\ \\ yのドメインY &\to& Xの部分集合からの像f(x)のみ \end{array}
『写像に』適用した概念になります。
（写像が集合であるなら部分集合の存在により明らか）
写像の詳細な形成手順
改めて整理しておくと
\begin{array}{ccc} X\times Y&=&\{ (x,y) \mid x\in X∧y\in Y \} \end{array}
『写像』は「直積集合 X\times Y の部分集合」なので
（ x と紐づいてる y が１つだけという制限がある）
\begin{array}{lcl} 集合X,Yが存在 &\to& 直積集合X\times Yの存在 \\ \\ &\to& f\subset X\times Y のfが写像公理を満たす \\ \\ &\to& fの部分集合は存在する \\ \\ &\to& fの部分写像が存在する \end{array}
その生成手順はこのような感じになっています。
（これの最初の出発点は「写像を集合で形成したい」）
部分写像は必ず写像になる
これは「逆写像」とは異なり
『必ず写像になる』もので
\begin{array}{ccl} fの部分写像f| &\to& f|の要素は全てfの要素 \\ \\ &\to& (x,y_1)\in f|∧(x,y_2)\in f| \,\,\to \,\, y_1=y_2 \\ \\ &\to& f| は写像の要請を満たす \end{array}
「写像の要請的定義」を必ず満たします。
（そもそも写像の部分集合なので直感的に明らか）
逆写像 Inverse Mapping
|| 矢印の向きを変えたら？
「写像」の『逆向き操作』のこと
\begin{array}{lcrcr} f(x)&=&y&=&2x \\ \\ f^{-1}(y)&=&\displaystyle\frac{1}{2}y &=&x \end{array}
具体的にはこの f^{-1} のことで
（根本的に逆関数の一般化だと思って良い）
\begin{array}{c} f^{-1} &=& \{ (y,x) \mid (x,y)\in f \} \end{array}
『最初は写像 f に対して』定義されます。
（ f への適応以降は f^{-1} にも適用できる）
逆写像は常に存在する
これは『写像の存在』から導かれる事実で
\begin{array}{lcl} 写像fの存在 &\to& 写像fは集合 \\ \\ &\to& fが空でないなら要素(x,y)\in f は存在 \\ \\ &\to& (x,y)の定義に必要なx,yも存在 \\ \\ &\to& x,yを使って順序対が作れる \end{array}
「写像 f が存在するなら」常に成立します。
（ x,y が存在することから公理により保証される）
補足しておくと
\begin{array}{lcl} x,y &\to& \left\{ \begin{array}{lcl} \{ y,y \} && \because\mathrm{Pair} \\ \\ \{ y,y \}=\{ y \} && \because\mathrm{Extension} \\ \\ \{ y,x \} && \because\mathrm{Pair} \\ \\ \{\{y\},\{y,x\}\} && \because\mathrm{Pair} \\ \\ \{\{y\},\{y,x\}\}=(y,x) && \because\mathrm{Order} \end{array} \right. \end{array}
（この辺りの詳細は長くなるので別記事にまとめてます）
論理式による要請と集合の構成
「同値」と「同じ」の違いについては
\begin{array}{lcl} (x,y) \in f &\Longleftrightarrow& (y,x) \in f^{-1} \end{array}
これについて深堀してみると分かり易いです。
（この論理式の定義では『同値』になる）
というのも
\begin{array}{lcl} f &\subset & \{ (x,y) \mid (x\in X∧ y\in Y) \} \\ \\ f^{-1} &=& \{ (y,x) \mid (x,y)\in f \} \end{array}
「要請的定義からできあがる集合」は
『論理式の段階』で「同値」だとしても
\begin{array}{ccc} x\in\{1,2\} ∧ y\in \{3,6\} &\to& f=\{(1,3),(2,6)\} \\ \\ f^{-1}=\{(3,1),(6,2)\} &←& f=\{(1,3),(2,6)\} \end{array}
『要素が一致しない状態』を簡単に作れます。
（つまり逆写像は元の写像と一致するとは限らない）
なので『実際にできあがるもの』は
「同じとは限らない」んですが
\begin{array}{ccc} (x,y) \in f &\Longleftrightarrow& (y,x) \in f^{-1} \end{array}
『作りたいものへの要請』については
\begin{array}{ccc} (1,3) &\to& (3,1) \\ \\ (1,3) &←& (3,1) \end{array}
『片側の要素からもう片方が特定できる』ので
（ f^{-1} は f の順番反転要素を全て持つ）
\begin{array}{ccc} (x,y) \in f &\Longrightarrow& (y,x) \in f^{-1} \\ \\ (x,y) \in f &\Longleftarrow& (y,x) \in f^{-1} \end{array}
「片側からもう片方を導ける」関係にあると言えます。
（これが「同値」の感覚で『相等関係 = 』とは異なる）
逆写像の要請と量化による一般化
整理しておくと
\begin{array}{ccl} fの量化を外す &\to& Y から好きに定数β を取り出す \\ \\ &\to& Xから好きに定数αを取り出す \\ \\ &\to& 関係を整理する \\ \\ &\to& 一般化する \end{array}
↑ の話はこの「関係を整理する」段階の話で
\begin{array}{lcccr} {}& {}& (α,β) \in f &\Longrightarrow& (β,α) \in f^{-1} \\ \\ {}& {}& (α,β) \in f &\Longleftarrow& (β,α) \in f^{-1} \\ \\ {}& {}& (α,β) \in f &\Longleftrightarrow& (β,α) \in f^{-1} \\ \\ {} & \forall y\in Y & (α,y) \in f &\Longleftrightarrow& (y,α) \in f^{-1} \\ \\ \forall x\in X & \forall y\in Y & (x,y) \in f &\Longleftrightarrow& (y,x) \in f^{-1} \end{array}
『任意に取り出している』ことから
「全称化による一般化」はこのような手順で行われます。
（ \forall x\in X \,\, \forall y\in Y が前提の時点で確定している）
まとめると
\begin{array}{cccl} 同値 & ⇔ && 情報の量が保存されている \\ \\ 相等 & = && 集合による構成が完全に一致する \end{array}
この２つはこのような感じになっていて
『それぞれ別の性質を意味する』ものになっています。
（つまり同値であれば片方からもう片方を復元できる）
逆写像の対称性
「逆写像 f^{-1} への逆写像操作」については
\begin{array}{lcl} f^{-1} &=& \{ (y,x) \mid (x,y)\in f \} \\ \\ (f^{-1})^{-1} &=& \{ (x,y) \mid (y,x)\in f^{-1} \} \end{array}
『 f の要素が失われていない』ことから
（ (a,b) は必ず (b,a) として f^{-1} に含まれる）
\begin{array}{ccc} (f^{-1})^{-1} &=& f \end{array}
「操作起点の写像 f 」になると言えます。
（逆写像が写像でない場合も起点の制限からこうなる）
厳密にはちょっとややこしいですが
\begin{array}{lcl} (x,y) \in X\times Y &\Longleftrightarrow& x\in X ∧ y\in Y && 一般 \\ \\ (x,y) \in f &\Longrightarrow& x\in X ∧ y\in Y && 一般 \\ \\ (x,y) \in f &\Longleftrightarrow& x\in X ∧ y\in Y && 個別 \\ \\ (y,x) \in f^{-1} &\Longleftrightarrow& (x,y) \in f \\ \\ (x,y) \in (f^{-1})^{-1} &\Longleftrightarrow& (y,x) \in f^{-1} \end{array}
論理式による厳密な表現はこんな感じです。
（最後の行を全称量化で一般化すれば完成）
逆写像は写像であるとは限らない
「逆写像」は『写像の逆操作』であるため
「写像」という名前が付いてはいますが
\begin{array}{lcl} gは重複する全射 &\to& gの逆写像はとれる \\ \\ &\to& (β_1,α)と(β_2,α)を要素にとれる \\ \\ &\to& g^{-1}は写像の定義を満たさない \end{array}
「写像よりも広い」概念になります。
（出発点 α_1,α_2 から同じ終点 β への接続を写像は許す）
典型的な例としては
\begin{array}{lcl} f&=&\{(1,3),(2,3)\} \\ \\ f^{-1}&=&\{(3,1),(3,2)\} \end{array}
このような例が考えられるため
\begin{array}{lclc} (x,y_1)\in f &∧ & (x,y_2)\in f &\Longrightarrow& y_1=y_2 \\ \\ (3,1)\in f^{-1} &∧ & (3,2)\in f^{-1} &\Longrightarrow& 1≠2 \end{array}
『逆写像という操作による構成結果』は
「写像になるとは限らない」状態にあります。
逆写像が写像になるには
「写像である」ためには
\begin{array}{ccc} (x,y_1)\in f ∧ (x,y_2)\in f &\Longrightarrow& y_1=y_2 \end{array}
この条件を満たす必要がある。
（各変数は X,Y から任意に取っている）
これが分かり易い着地であることから
\begin{array}{lcl} f&=&\{(1,3),(2,3)\} \\ \\ f^{-1}&=&\{(3,1),(3,2)\} \end{array}
まず「典型例を否定できる」形の
『分かり易い条件を予想』してみると
\begin{array}{ccc} (3,1),(3,2)にならない &\to& (1,3),(2,3) ではダメ \\ \\ &\to& 3の一致がダメ \end{array}
この観察結果から
\begin{array}{ccc} 像が一致しない &\to& 単射であればいい？ \end{array}
こういった条件を導くことができます。
（この時点ではまだ予想の段階）
逆写像と単射
比較しておくと
\begin{array}{ccc} 写像の前提 && (α,β_1)\in f ∧ (α,β_2)\in f \\ \\ 単射の前提 && (α_1,β_2)\in f ∧ (α_2,β_2)\in f \\ \\ 単射の前提 && (α_1,β)\in f ∧ (α_2,β)\in f \end{array}
これを分離して前提として置く場合
\begin{array}{ccc} 写像 && x=αの前提 &\Longrightarrow& β_1=β_2 \\ \\ 単射 && α_1≠α_2の前提 & \Longrightarrow & f(α_1)≠f(α_2) \\ \\ 単射 && y=βの前提 & \Longrightarrow & α_1=α_2 \end{array}
「写像」と「単射」はこのような感じになります
（ α,β は両方とも X,Y から任意にとったとする）
この形から分かるように
\begin{array}{lcl} (x,y)\in f &\Longleftrightarrow& (y,x)\in f^{-1} \end{array}
「逆写像の定義との入れ替え」で
（ ⇔ は入れ替え可能なのでこうなる）
\begin{array}{ccc} (α_1,β)\in f ∧ (α_2,β)\in f& \Longrightarrow & α_1=α_2 \\ \\ (β,α_1)\in f^{-1} ∧ (β,α_2)\in f^{-1} & \Longrightarrow & α_1=α_2 \end{array}
この結論はすぐに得ることができます。
（ f が写像という前提から f^{-1} が写像であると分かる）
また同様の理屈で
『逆写像は写像である』から
\begin{array}{ccc} (β,α_1)\in f^{-1} ∧ (β,α_2)\in f^{-1} & \Longrightarrow & α_1=α_2 \\ \\ (α_1,β)\in f ∧ (α_2,β)\in f& \Longrightarrow & α_1=α_2 \end{array}
『写像 f は単射である』が導かれます。
（これで『 f が単射である』が条件として得られる）
逆写像が写像なら
また直感的にも分かる通り
\begin{array}{ccl} fが単射 &\to& 1対1対応 \\ \\ fが単射 &\to& f^{-1}が写像 \\ \\ &\to& f^{-1}も1対1対応 \\ \\ &\to& f^{-1}も単射？ \end{array}
「単射の定義」と同様の理屈を用いれば
（否定形と否定除去形の定義は同値）
\begin{array}{l} (β,α_1)\in f^{-1} ∧ (β,α_2)\in f^{-1} & \Longrightarrow & α_1=α_2 \end{array}
『逆写像 f^{-1} は写像である』という前提から
（ f^{-1} が写像であるためには f が単射である必要がある）
\begin{array}{ccc} \mathrm{P} &⇒& a≠bになるならf(a)≠f(b) のパターンしかない \end{array}
このパターンを使うことで
\begin{array}{ccc} α_1≠α_2 &\Longrightarrow& f(α_1)≠f(α_2) \end{array}
『逆写像 f^{-1} は単射である』を導くことができます。
（これを導くためにはこの否定形の定義が必要になる）
逆写像と全単射
整理すると
\begin{array}{ccc} fが単射 &\Longleftrightarrow& f^{-1}も単射 \end{array}
この結論が得られることから
\begin{array}{ccc} Y&=&\mathrm{Image}(f) \\ \\ && \mathrm{Image}(f) &=& \{ y\in U \mid \exists x \in X \,\, (x,y)\in f \} \end{array}
「像集合 \mathrm{Image}(f) による終域の定義」と
（これにより f を定義時点で全射にできる）
\begin{array}{lcl} (x,y)\in f &\Longleftrightarrow& (y,x)\in f^{-1} \end{array}
『逆写像の定義』を用いることで
\begin{array}{ccc} & & (α,β)\in f \Longleftrightarrow (β,α)\in f^{-1} \\ \\ & \forall y\in Y & (α,y)\in f \Longleftrightarrow (y,α)\in f^{-1} \\ \\ \forall x\in X & \forall y\in Y & (x,y)\in f \Longleftrightarrow (y,x)\in f^{-1} \end{array}
「 f が全単射である」と
「 f^{-1} が単射である」ことから
\begin{array}{ccc} f^{-1} &=& \{ (y,x) \mid (x,y)\in f \} \end{array}
『逆写像は全単射である』を導くことができます。
（全単射 f の要素の反転要素が逆写像にある）
起点写像 f が全単射なら f^{-1} は全射
補足しておくと
「 f^{-1} が全射ではない」と仮定した場合
\begin{array}{lcl} 仮定 &\to& f^{-1}は単射 \\ \\ &\to& 定義域Yの要素yは全て対応 \\ \\ &\to& X側にYと対応しない要素cがある \\ \\ &\to& 全単射fから見たcを考える \end{array}
このような流れから
\begin{array}{ccl} 仮定 &\to& fは全単射である \\ \\ &\to& 定義域Xの要素cはYの要素となる像を持つ \\ \\ &\to& fが全単射という事実に矛盾する \\ \\ &\to& f^{-1}が全射ではないが矛盾を導く \\ \\ &\to& f^{-1}は全射でなければならない \end{array}
これはこういう形で矛盾が導かれてしまいます。
（つまり単射かつ全射なので全単射）
ちなみに形式的には
\begin{array}{ccr} f^{-1}は全射ではない &\to& f^{-1}(y)≠c \\ \\ &\to& \forall y\in Y \,\, f^{-1}(y)≠c \\ \\ &\to& \exists x\in X \,\, \forall y\in Y \,\, f^{-1}(y)≠x \end{array}
この「否定したい仮定」と
（全射ではないという仮定からの導出）
\begin{array}{ccc} \forall x\in X & \exists y\in Y & f(x)=y \end{array}
『 f が全単射であるという前提』から
（これは「 f は全射である」の定義）
\begin{array}{ccc} & (x,y)\in f &\Longleftrightarrow& (y,x)\in f^{-1} \end{array}
これで変形すると矛盾してしまうという形で
\begin{array}{cclcl} \forall x\in X & \exists y\in Y & f(x)=y && 前提 \\ \\ \forall x\in X & \exists y\in Y & f^{-1}(y)=x && 前提からの導出 \\ \\ \exists x\in X & \forall y\in Y & f^{-1}(y)≠x && 導出と矛盾する仮定 \end{array}
『全射ではないの否定』という形から導かれます。
（この定義からの導出が仮定からの導出と矛盾する）
双方向の単射と全単射
この事実から
\begin{array}{ccl} 双方向に単射がある &\to& 両方から1対1対応 \\ \\ &\to& 要素数が同じになるはず \end{array}
明らかにこうなりそうで
（結論としては必ずこうなる）
\begin{array}{ccc} 1&\rightleftarrows&2 \\ \\ 2 &\rightleftarrows& 4 \\ \\ 3& \rightleftarrows &9 \end{array}
実際「有限集合同士」ならこの結論は明らかなんですが
（定義可能な範囲なら有限集合は確認できる）
\begin{array}{ccc} 双方向単射 &\to& 全単射 \end{array}
これについては
\begin{array}{ccl} 有限集合の双方向単射 &\to& 要素数の一致を確認できる \\ \\ &\to& 全単射になると確認できる \\ \\ \\ 無限集合の双方向単射 &\to& X,Yを全て調べる必要が \\ \\ &\to& 全射段階で一般化が困難 \end{array}
『無限集合同士』がネックになります。
（これの詳細はベルンシュタインの定理で解説）
恒等写像 Identity Function
|| 自分から自分に写る感じ
『変化しない』を実現する「写像」
\begin{array}{lcl} \mathrm{Id}_A(x)=x &&1_A(x)=x \\ \\ \mathrm{Id}_S(x)=x &&1_S(x)=x \end{array}
「掛け算の × 1 」「足し算の +0 」のような
（これらが恒等写像の原型になる感覚）
\begin{array}{ccc} \mathrm{Id}_A &=& \{ (x,x) \mid x\in A \} \end{array}
『変化しない操作』を「恒等写像 \mathrm{Id} 」と言います。
（ x の存在が確定すれば (x,x) の存在も確定）
恒等写像の存在条件
これは『集合 X の存在』さえ確定していれば
\begin{array}{lcl} x\in X &\to& \left\{ \begin{array}{lcl} \{ x,x \} && \because\mathrm{Pair} \\ \\ \{ x,x \}=\{ x \} && \because\mathrm{Extension} \\ \\ \{ x,x \} && \because\mathrm{Pair} \\ \\ \{\{x\},\{x,x\}\} && \because\mathrm{Pair} \\ \\ \{\{x\},\{x,x\}\}=(x,x) && \because\mathrm{Order} \end{array} \right. \end{array}
\begin{array}{ccc} 集合Xの存在 &\to& 恒等写像 \mathrm{Id}_X が存在 \end{array}
基本的には存在していると考えて良いです。
（公理と集合の存在が否定された状況なら存在しない）
恒等写像は写像である
これは直感的にも当然ですが
念のために確認しておくと
\begin{array}{ccc} (x,y_1)\in 1_A∧(x,y_2)\in 1_A &\Longrightarrow& y_1=x=y_2 \end{array}
こうなりますから
「写像の要請的定義」は明らかに満たされます。
恒等写像は単射である
直感的に「全単射」だと分かるので
まあこの結論は当然なんですが
\begin{array}{ccl} x&=&\mathrm{Id}(x) \\ \\ y&=&\mathrm{Id}(y) \end{array}
念のため確認しておくと
『 \mathrm{Id}(x) と \mathrm{Id}(y) を比較したい』から
\begin{array}{ccc} x≠y &\Longrightarrow& \mathrm{Id}(x)=x≠y=\mathrm{Id}(y) \\ \\ &\Longrightarrow& \mathrm{Id}(x)≠\mathrm{Id}(y) \end{array}
これはこのような形で示されることになります。
（左の前提と恒等写像の定義から右が導かれる）
恒等写像は全射である
これも直感的には明らかです。
\begin{array}{ccl} 全て映る &\to& まず好きにAの要素aをとる \\ \\ &\to& 恒等写像の定義より(a,a)\in\mathrm{Id}_A \\ \\ &\to& 値域のaに対し定義域は必ずaになる \\ \\ &\to& 対応を持たない値域側のaは存在しない \\ \\ &\to& 全射の定義が満たされる \end{array}
厳密にはこのような流れで示され
（ \mathrm{Id}_A=\{ (x,x) \mid x\in A \} の定義が前提になる）
\begin{array}{ccr} a\in A &\to& \mathrm{Id}_A(a)=a \\ \\ &\to& \exists x\in A \,\, \mathrm{Id}_A(x)=a \\ \\ &\to& \forall y\in A \,\, \exists x\in A \,\, \mathrm{Id}_A(x)=y \end{array}
これを論理式で表現するとこんな感じになります。
（これにより単射かつ全射になるので全単射だと言える）
恒等写像と自己逆性
またこれも当然ではありますが
\begin{array}{c} f^{-1} &=& \{ (y,x) \mid (x,y)\in f \} \end{array}
「逆写像」の定義がこうなっている以上
\begin{array}{lcl} \mathrm{Id}_A &=& \{ (x,x) \mid x\in A \} \\ \\ \mathrm{Id}_A^{-1} &=& \{ (x,x) \mid (x,x)\in \mathrm{Id}_A \} \end{array}
『要素に一切の変更が無い』ので
（ (a,a) の順番を入れ替えても (a,a) ）
\begin{array}{ccc} \mathrm{Id}_A&=&\mathrm{Id}^{-1}_A \end{array}
『恒等写像の逆写像 \mathrm{Id}^{-1}_A 』はこのようになります。
（この逆操作でも一致する感じが自己逆性）
補足しておくと
\begin{array}{lcl} (x,x)\in \mathrm{Id}_A &\Longleftrightarrow& x\in A \\ \\ (x,x)\in \mathrm{Id}_A^{-1} &\Longleftrightarrow& (x,x)\in \mathrm{Id}_A \end{array}
形式的にはこんな感じです。
（ ↑ の逆写像の対称性と同様にまず変数を固定）
合成 Composition
|| 写像と写像を繋げる感覚
「複数の写像」を考えるためもの
\begin{array}{c} f&:&A&→&B \\ \\ g&:& {} && B&→&C \\ \\ \\ g \circ f&:&A&→&B&→&C \\ \\ f;g&:&A&&→&&C \\ \\ fg &:&A&&→&&C \end{array}
これは ↓ のような
\begin{array}{lcl} (g\circ f)(x)&=&g\Bigl(f(x)\Bigr) \end{array}
『複数の関数』で考えると分かり易いです。
（この形をそのまま一般化したのが写像の合成）
写像合成の厳密な定義
写像の「合成 g\circ f 」の定義は
\begin{array}{ccc} (x,z)\in g\circ f &\Longleftrightarrow& \exists y & (x,y)\in f ∧ (y,z)\in g \end{array}
こんな感じでちょっと複雑なんですが
（存在量化の部分がちょっと分かり辛いかも）
\begin{array}{ccl} 写像で g\Bigl( f(x) \Bigr) &\to& f(x)はgの定義域の要素 \\ \\ &\to& (x,y)\in f と (y,z)\in g の yが共通する \end{array}
感覚的な部分を補完すると
（ ↑ が着地なので逆算から ↓ が得られる）
\begin{array}{ccr} (x,z)\in g\circ f &\Longleftrightarrow& & (x,β)\in f ∧ (β,z)\in g && 具体 \\ \\ && {}& \Downarrow \\ \\ (x,z)\in g\circ f &\Longleftrightarrow& \exists y & (x,y)\in f ∧ (y,z)\in g && 一般 \end{array}
わりとすんなり理解できると思います。
（共通する β は g\circ f 側からするとなんでもいい）
補足しておくと
\begin{array}{ccc} x\in X & y\in Y & z\in Z \end{array}
前提になる記号の定義は
\begin{array}{ccc} f &\subset& X\times Y \\ \\ g&\subset & Y\times Z \end{array}
それぞれこんな感じです。
（写像の合成という着地で使う材料として導かれる）
合成と結合律
「群」などで確認することがあるので
\begin{array}{ccc} (f\circ g)\circ h &=& f\circ (g\circ h) \end{array}
これについて確認しておくと
\begin{array}{lcl} (f\circ g) (x) &=& f\Bigl(g(x)\Bigr) \\ \\ (f\circ g) &=& f\Bigl( g \Bigr) \end{array}
この記号操作の定義から
\begin{array}{ccc} \Bigl((f\circ g)\circ h\Bigr)(x) &=& (f\circ g)\Bigl( h(x) \Bigr) &=& f\left( g\Bigl( h(x) \Bigr) \right) \\ \\ \Bigl(f\circ (g\circ h)\Bigr)(x) &=& f \Bigl( (g\circ h)(x) \Bigr) &=& f\left( g\Bigl( h(x) \Bigr) \right) \end{array}
「結合律」はこのような形で示されます。
（単純に定義を適用していくだけ）
合成による逆写像と恒等写像の関係
これも直感的には明らかですが
\begin{array}{lcl} f & \circ & f^{-1} &=& \mathrm{Id} \\ \\ f^{-1} & \circ & f &=& \mathrm{Id} \end{array}
厳密には少し複雑なので確認しておきます。
（量化周りが慣れてないと分かり辛いかも）
\begin{array}{lccl} (x,z)\in g\circ f &\Longleftrightarrow& \exists y & (x,y)\in f ∧ (y,z)\in g \\ \\ (y,y)\in f\circ f^{-1} &\Longleftrightarrow& \exists x & (y,x)\in f^{-1} ∧ (x,y)\in f \\ \\ (x,x)\in f^{-1}\circ f &\Longleftrightarrow& \exists y & (x,y)\in f ∧ (y,x)\in f^{-1} \end{array}
まず着地としてはこんな感じで
（これは左が直感の話で右が直感に合わせた定義）
\begin{array}{lcl} (x,y)\in f&\Longleftrightarrow& x\in X∧y\in Y \\ \\ (y,x)\in f^{-1} &\Longleftrightarrow& (x,y)\in f \\ \\ (x,x) \in\mathrm{Id}_X &\Longleftrightarrow& x\in X∧x\in X \\ \\ (y,y)\in \mathrm{Id}_Y &\Longleftrightarrow& y\in Y∧ y\in Y \end{array}
材料となる写像の定義はこうですから
（ここから ↑ の着地が導かれる）
着地を目指して
\begin{array}{ccc} (x,x)\in f^{-1}\circ f &\Longleftrightarrow& \exists y & (x,y)\in f ∧ (y,x)\in f^{-1} \end{array}
「 y を定数として考える」と
（正確には共通する定数 y の存在を仮定する）
\begin{array}{lcl} (y,x)\in f^{-1} &\Longleftrightarrow& (x,y)\in f \\ \\ (y,x)\in f^{-1}∧(x,y)\in f &\Longleftrightarrow& (x,y)\in f∧(x,y)\in f \end{array}
「逆写像の定義」を使えば
（ ⇔ は入れ替えを許すので下の左辺の書き換えが右辺）
\begin{array}{ccc} x\in X &\Longleftrightarrow& x\in X ∧ y\in Y \end{array}
後は『 y が y\in Y となる定数』という前提と
（前提で y\in Y としているので y\in Y は必ず真になる）
\begin{array}{ccc} (y,x)\in f^{-1} ∧ (x,y)\in f&\Longleftrightarrow& (x,y)\in f \\ \\ (x,x)\in f^{-1}\circ f &\Longleftrightarrow& (x,y)\in f \\ \\ \\ x\in X &\Longleftrightarrow& (x,y)\in f \\ \\ (x,x) \in\mathrm{Id}_X &\Longleftrightarrow& (x,y)\in f \end{array}
「 (x,y)\in f を経由する」という形から
（ ↑ の証明は最初に x を X から任意にとっている）
\begin{array}{ccc} (x,x) \in\mathrm{Id}_X &\Longleftrightarrow& (x,x)\in f^{-1}\circ f \end{array}
この結論を得ることができます。
（ここから x,y を量化していけば完成）
量化と定数の整理
変数と定数についての詳細は
\begin{array}{lcl} 量化を外す &\to& x\in X となる 定数を任意にとる \\ \\ &\to& 着地となる合成の式を確認できる \\ \\ &\to& y \in Yとなる定数yが存在すると仮定 \\ \\ &\to& ↑ の量化が外れた式が成立 \\ \\ &\to& yを量化してxを量化する \end{array}
「 ↑ の量化が外れた式が成立」の地点から見るなら
（言い換えるなら後は量化するだけの時点）
「 y の量化」については
\begin{array}{ccr} (x,x) \in\mathrm{Id}_X &\Longleftrightarrow& (x,x)\in f^{-1}\circ f \\ \\ &\Longleftrightarrow& (y,x)\in f^{-1} ∧ (x,y)\in f \\ \\ &\Longleftrightarrow& \exists y \,\, (y,x) \in f^{-1} ∧ (x,y)\in f \end{array}
正確にはこのようになっていて
（ ↑ の量化は ⇔ ではなく ⇒ だが合成の定義で一致）
\begin{array}{ccc} \forall x\in X & \Bigl( & (x,x) \in\mathrm{Id}_X &\Longleftrightarrow& (x,x)\in f^{-1}\circ f &\Bigr) \end{array}
「 x の量化」はこうなっています。
（ x は「任意に X からとっている」のでこうできる）