（※内輪向けのメモです。）
特性関数および「集合から特性関数への写像」が初めはイメージしにくいと思うので、解説を書いてみました。
aさん、bさん、cさん、dさん、eさんという5人のグループがあって、とある勉強会に出席するかどうかを調査したところ、aさん、cさん、dさんが出席、bさん、eさんが欠席することが分かった。このとき、出欠に関する情報を書き記す方法はいくつか考えられる。例えば\[\{a,c,d\}\]のように出席者だけをすべて書き並べてもよいし、
| a | b | c | d | e |
| 1 | 0 | 1 | 1 | 0 |
と、全員の出欠を表にしてもよい。後者の出欠表は、\(X=\{a,b,c,d,e\}\)から\(\{0,1\}\)への写像になっている。この写像を「\(\{a,c,d\}\)の特性関数」と呼び、\(\chi_{\{a,c,d\}}\)と書く。\(X\)の部分集合\(A\)をいろいろ変えてとれば、その\(A\)ごとに特性関数\(\chi_A\)がひとつ定まる。そこで、\(A\)に\(\chi_A\)を対応させる写像を考えることもできる。いわば、「『出席者のみのリスト』を『出欠表』のフォーマットに変換する写像」である。\(A\)は\(X\)の部分集合、すなわち\(X\)の冪集合の要素であり、いっぽう\(\chi_A\)は「\(X\)から\(\{0,1\}\)への写像の（ひとつひとつをすべて集めた）集合」の要素である。つまり、この写像は\[\chi:\mathcal{P}(X)\to{\rm Map}(X,\{0,1\}),\quad\chi(A)=\chi_A\]と書ける。「写像でうつる個々の値が再び写像になっている」という、非常に「荷物の重い」ものを想像しないといけないのが初心者には辛いところ（私は今でも辛い）。
さて、出欠表のイメージを持っていれば、逆に出欠表から出席者リストを復元するのは容易に見える。実際、出欠表の値が「1」になっているメンバーだけを漏れなく集めればよい。しかし、\(X\)が無限集合の場合なども考慮に入れると、これは決して自明なことではない。\({\rm Map}(X,\{0,1\})\)の要素（個々の写像）のなかには、\(X\)のいかなる部分集合の特性関数にもなっていないような、得体の知れない写像があるかもしれないし、よしんば何らかの特性関数になっていたとしても、ただひとつに復元できるという保証もない。\(\chi\)の全射性・単射性をきちんと証明することによって、これらの「いっけん自明なこと」が確認される。
（全射性の証明）任意の\(f\in{\rm Map}(X,\{0,1\})\)をとり、\(X\)の部分集合に\(f\)を特性関数とするものがあることを導く。\(f^{-1}[\{1\}]\)を考えると、実は\(f\)はこの集合の特性関数になっているので、そのことを示す。任意の\(x\in X\)をとる。(1)\(x\in f^{-1}[\{1\}]\)のとき、逆像の定義から\(f(x)=1\)である。(2)\(x\notin f^{-1}[\{1\}]\)のとき、やはり逆像の定義から\(f(x)\neq1\)すなわち\(f(x)=0\)である。(1)(2)により、\(f\)は\(f^{-1}[\{1\}]\)の特性関数の定義を満たしている。■
※この証明を見ると、結局のところ\(f^{-1}[\{1\}]\)という集合の存在が決め手になっている。これは集合論的には裏付けることのできる話であるが、そこを避けて通ってしまっているので、「結局、わざわざ証明した意義が分からない」と感じる人がいても不思議ではない。
（単射性の証明）\(X\)の部分集合\(A,B\)を任意にとり、\(\chi(A)=\chi(B)\)を仮定して\(A=B\)を導く。任意の\(a\in A\)をとると\(\chi_A(a)=1\)である。仮定により\(A,B\)の特性関数\(\chi_A,\chi_B\)が写像として等しいから\(\chi_B(a)\)の値も\(1\)であり、したがって\(a\in B\)である。全く同様にして、\(b\in B\)をとると\(b\in A\)が導かれる。■
※ゼミでは\(A\neq B\)から\(\chi(A)\neq\chi(B)\)を導いたが、ここでは対偶を示した。
