1 可算無限集合の定義と基本概念
1.1 数え上げ可能性（可算性）の定義
集合が「数え上げ可能」と呼ばれるのは、その要素を重複なく順番に並べられる場合である。形式的には、集合 A が自然数の集合 N（0 から始めるか 1 から始めるかは流儀による）に対して、全要素を漏れなく割り当てできることを意味する。つまり、A の各要素が自然数のいずれかと対応し、しかも同じ自然数が複数の要素に対応しないようにできるなら、A は可算である。
可算性には二つの一般的な分類がある。ひとつは「有限」で、もう一つは「無限だが可算」である。可算無限集合とは、有限集合ではないが可算である集合を指す。
1.2 1対1対応と全射・単射の関係
可算性を扱う際に中心となるのは、単射（1対1の写像）と全射（全要素を覆う写像）の関係である。写像 f が単射であれば、異なる入力が異なる出力に写るため、要素の重複が生じない。全射であれば、対象側のどの要素も写像の値として実現され、漏れがない。
可算性の判定では、A と N の間に全単射（単射かつ全射）が存在することを示すのが典型的である。これは「対応を作る」ことが「並べ上げ」を意味し、集合の大きさが自然数と同程度の規模であることを保証する。
1.3 可算無限と可算（有限を含む）の違い
「可算」という語はしばしば広い意味で用いられ、有限集合も含めた概念として扱われることが多い。その場合、可算集合とは有限または可算無限のどちらかである。
一方で「可算無限」は、集合が無限であることを明示的に要求する。したがって可算無限の例は、自然数全体や整数全体のように無限だが番号付けできる集合である。有限集合は番号を付けられる点では同様だが、「数え上げが終わる」性質をもつため、可算無限との直感的な性格が異なる。
1.4 基数の直観的理解（濃度としての位置づけ）
集合論では「基数（cardinality）」を用いて集合の大きさを比較する。可算無限集合は、自然数と基数が一致するため、基数としては最小の無限である（有限とは区別されるが、非可算無限よりは小さい）。
直観的には、ある空間に点がどれほど詰まっているかを考える比喩がある。可算無限は、点を順番に数えていけば最後は尽きないが、それでも「番号を振って整理できる」密度と見なせる。非可算無限は、どれほど丁寧に番号付けしようとしても、取り切れない種類の大きさを持つという位置づけになる。
2 可算無限集合の代表例
2.1 自然数全体
自然数全体 N は可算無限の典型例である。理由は、自然数自身が「自然数と全単射で対応できる」からである。対応としては恒等写像を取ればよく、これは重複なく漏れなく並べ上げできることを意味する。
ここで重要なのは、基準集合としての役割である。自然数が可算の基準となるため、可算性の主張はしばしば「自然数と同じ大きさ」であることを言い換える形で表される。
2.2 整数全体
整数 Z も可算無限である。直感的には、負の数と非負の数が混在するため、自然数と同じように単純な順序で並べるのは難しそうに見える。しかし実際には、行き先が尽きない番号付けを設計できる。
たとえば、0 を最初に置き、続いて 1, -1, 2, -2, 3, -3, … のように交互に並べる対応が可能である。この並べ方は重複がなく、すべての整数がいつかは現れるので全要素の漏れがない。したがって Z は可算無限である。
2.3 有理数全体
有理数 Q（分数で表せる数全体）も可算無限である。分子と分母の組は整数の組として扱えるが、そのままでは同じ有理数を複数回表す可能性がある。そこで、重複を避ける工夫や、格子状に区画化して段階的に列挙する手順が用いられる。
代表的には、分数を「分子・分母の組」として格子に配置し、対角線状に走査することで、すべての分数（最終的に簡約された形に対応づけられるもの）を順番に拾い上げる方法が知られている。これにより有理数が自然数と全単射により対応でき、可算であることが示される。
2.4 正の有理数・負の有理数などの分割
有理数全体 Q が可算であれば、その部分集合としての正の有理数や負の有理数も可算である。これは、可算集合の部分集合が可算である場合が多く、さらに分割された各部分も同様の整理を行えるためである。
負の有理数は、正の有理数に -1 を掛けることで対応を作れる。正の側も同様に、全体から一方を取り出す手続きにより番号付けを保てる。結果として、正の有理数のみ、負の有理数のみ、あるいはそれらを組み合わせた有理数の扱いは、可算性の枠内で一貫した振る舞いを示す。
3 可算性に関する代表的な性質
3.1 部分集合と可算性
可算集合の部分集合は、多くの場合で可算である。直観的には「数え上げ可能なリストから一部の要素を抜き出す」ことに相当するためである。自然数に対応付けられた要素列から、条件に合うものだけを選び出しても、残った要素は依然として番号付けできる。
ただし、部分集合が無限かどうかは別問題である。抜き出し方によって有限になったり、可算無限になったりする。可算性の判定は「その部分が有限であるか可算無限であるか」で分岐する。
3.2 和集合（可算個の可算集合の合併）
可算個の可算集合の和集合は可算である。これは、各集合ごとに番号付けできるなら、集合番号と要素番号の二段構えで整理できるという発想に基づく。
具体的には、集合の添字（どの集合から取るか）を自然数で番号付けし、さらに各集合内での要素の番号も自然数により与える。こうして得られる二つの自然数の組を、再び自然数一つへと符号化する手順が可能である。符号化ができれば、合併後の全要素も重複なしに列挙できる。
3.3 階乗・直積に対する可算性
直積に関する性質は、可算性の実用性を示す中心的な話題である。たとえば、二つの可算集合の直積は可算になる。これは「格子の点を順番に訪れる」発想で説明できる。
格子上の座標を考え、例えば和が一定の対角線上を順に処理するようにすれば、すべての組がいつかは現れる。各方向に無限が含まれていても、走査の順序を工夫することで全体を数え上げ可能にできる。
また、直積を有限回繰り返した場合も同様に可算性が保たれる。階乗という語がここでは冗長な比喩として使われることがあるが、要点は「有限回の直積操作が可算性を崩さない」点にある。
3.4 有限回の演算と可算性の保存
可算性は、有限回の合成操作に対して比較的安定である。たとえば、可算集合に対して有限個の選択肢を持つ構成（有限個の可算集合の合併、有限個の可算集合の直積、または有限回の段階的な列挙に相当する操作）では、全体が再び可算になる。
この性質は「情報量の増え方が制御されている」ことに対応する。可算無限は最小の無限であり、有限段階では基数の飛躍が起こりにくい。そのため、操作の回数が有限である限り、可算性の枠内で整理できる場合が多い。
4 可算性の証明手法
4.1 列挙（明示的な対応関数の構成）
可算性の証明の基本形は、具体的に対応関数を作り、全単射が成立することを示すことである。列挙とは、自然数に対応する一覧を明示して、各要素がどこかの番号で必ず現れることを保証する手法である。
対応関数を「定義して終わり」ではなく、単射であること（同じ番号に二つが割り当てられない）、全射であること（すべての要素が番号に現れる）を確認するのが重要となる。列挙型の証明は直感に合いやすいが、複雑な対象では対応の作り方が難しくなる。
4.2 対角線型の考え方とその位置づけ
対角線型の考え方は、表や配列を俯瞰して「見落としがない順序付け」を設計する際に用いられる。可算性の証明では、主に格子状に並べた対象を対角線方向に走査することで、直積の可算性などを示すのに役立つ。
一方で、対角線型の発想は非可算性の議論にも現れる。つまり同じ手法の“方向”が、可算側では整理のために使われ、非可算側では「どんな対応を作っても抜けが生じる」ことを示すために転用される。両者を混同しないことが理解の要点である。
4.3 表・格子状の整理による証明
表・格子状の整理は、直積や多変数の対象の可算性を扱う際に有効である。対象を座標（例えば第一成分と第二成分）に分解し、各座標を格子上の点として配置する。次に、格子の点を列挙する順序を定めることで、全体を自然数へ結び付ける。
例えば、二次元の格子では対角線の順番が典型である。三次元以上でも同様の工夫が可能で、一般に「一定の合計や段階で区切っていく」設計が採られる。ここでの本質は、走査が全領域を覆うことと、同じ点を何度も数えないことを保証する点にある。
4.4 矛盾による非可算性との対比（境界の理解）
可算性の議論は、非可算性との対比によって理解が深まる。非可算集合の代表例として実数全体が挙げられるが、そこで用いられる典型的な議論は「どんな番号付けも成立しない」ことを示す構成になる。
証明の雰囲気としては、仮に全単射が存在すると仮定し、その仮定から矛盾が導かれる流れが多い。これは、可算性の証明が「全単射を構成する」方向であるのに対し、非可算性では「構成できない」ことを示す方向だと言える。
したがって境界の理解とは、可算性が可能な状況と不可能な状況の差を、証明戦略の違いとして捉えることである。列挙や格子の走査で対応が作れる限り可算であり、それが根本的に崩れる場合には非可算が現れる。