「前回の授業で，印象に残った言葉を，配付資料に書かれていない中から3つ選んで記入し，提出してくださいとしたところ，これまでにない多彩な解答を得ることができました．
それで，答案の中に，『加算集合』というのを見かけました．
しかし，集合の足し算は，とくに行っていません．
こちらで話したことを思い出してみると，『可算集合』のことでした．
自然数全体からなる集合は，可算集合です．そしてそれに一対一で対応付けられる集合も，可算集合です．英語ではcountable setです．
一方向ハッシュ関数を考える際の入力（メッセージ）の集合，『メッセージ空間』は，任意の長さのビット列であり，その集合は，可算集合と言えます．列挙するなら，長さ0のビット列---εまたはλと書かれることが多いのですが---から始まって，0，1，00，01，10，11，000，001，あとはいいですね．いくらでも順に言うことができます．ビット長の小さいものから大きいものへ，そして同じ長さなら2進数とみなして値が大きくなるように，並べることで，漏れなく，重なりなく，ビット列を書き表すことができます．10101010というビット列は，この系列の先頭から何番目か，というのは，実際に列挙することなく，高校数学の知識で求めることができます．
もう少し，いくつか知っておいてください．一方向ハッシュ関数の出力のほう，『ハッシュ値』は，入力となるメッセージのサイズにかからわず，固定長とするのが一般的です．SHA-1なら160ビットです．この場合，ハッシュ値空間は，そのサイズが2の160乗の，有限集合となります．
有限集合と無限集合，どちらが大きいか，というのを真剣に考える必要はありません．無限集合からは，与えられた有限集合よりも大きな要素数の部分有限集合を得ることができるので，素朴に『無限集合のほうが大きい』と思えばいいのです．
実数全体からなる集合は，可算集合ではなく，より大きな集合であることが証明されていて，『非加算集合』と呼ばれます．可算集合と有限集合を合わせて，『たかだか可算』といいます」
