# 濃度 ## 定義 有限集合Aの濃度(cardinality)|A|は、Aに含まれる要素の個数として定義され、非負整数の値を取る(空集合の濃度は0)。有限集合の濃度は、[[関数]]・[[二項関係]]の性質と結びつけて特徴づけられる。二項関係R: A → Bが関数であれば、Aの各要素が高々1本の矢印しか出さないため矢印の総数は|A|以下であり、さらにRが全射であれば余域Bの各要素に矢印が少なくとも1本入るため矢印の総数は|B|以上になる。この2つの不等式を組み合わせると、A surj B(AからBへの全射関数が存在する)ならば |A| ≥ |B| であることが示せる(補題4.5.3)。A inj B(AからBへの全域単射関係が存在する)、A bij B(AからBへの全単射が存在する)についても同様の対応が成り立つ。この3つの対応を合わせたものがMapping Rule(定理4.5.4)で、有限集合A, Bについて (1) |A| ≥ |B| iff A surj B、(2) |A| ≤ |B| iff A inj B、(3) |A| = |B| iff A bij B、が成り立つ。逆方向(サイズの大小・相等から全射・単射・全単射の存在を導く方向)は、余りの要素を余域の1つの要素にまとめて割り当てるといった具体的な関数の構成によって示される。応用として、n要素の集合Aについて、Aの部分集合SをAの要素の並びに対するnビット列(要素が含まれるかどうかを0/1で表す)へ対応づける明示的な全単射を構成し、全単射版のMapping Ruleを適用することで、|pow(A)| = 2ⁿ(定理4.5.5)が証明される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]]) ### 無限集合への拡張 有限集合限定のMapping Ruleを無限集合へ拡張するため、第7章 Infinite Sets は「大きさ」の絶対的な定義(数として何個か)を放棄し、「同じ大きさ」・「以上の大きさ」という相対的な比較関係だけを再定義する。A strict B(AはBより真に小さい)を NOT(A surj B) と定義すると(定義7.1.1)、有限集合上ではこれが |A| < |B| と一致する(系7.1.2、Mapping Ruleから直接導かれる)。「同じ大きさ」= A bij B、「以上の大きさ」= A surj B という関係そのものを主役に据えることで、「大きさ」を測る数値を経由せずに無限集合を比較できるようになる。この定義のもとで、有限集合の直観の多くが無限集合にも引き継がれる(surj/bijの推移性・対称性、Schröder-Bernsteinの定理、任意の2集合の比較可能性)一方、「要素を1つ追加すると真に大きくなる」という直観は無限集合では成立しない(Aが無限集合でb ∉ Aならば A bij (A ∪ {b}))。さらにCantorの定理(A strict pow(A))により、無限集合どうしにも真の大小関係が存在することが示される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]] §7.1) ## 横断的知見 - 第4章(有限集合)と第7章(無限集合)を突き合わせると、「濃度の比較」という営みの一貫した骨格が見える。第4章はMapping Rule(定理4.5.4)により |A| ≥ |B| iff A surj B という同値を数値|A|・|B|の側から証明するが、第7章はこの同値関係の右辺(A surj Bによる比較)だけを取り出し、それを無限集合における比較の定義そのものへ格上げする(定義7.1.1)。つまり第4章では「数えられるから比較できる」のに対し、第7章では「比較できることを先に定義し、数えられる場合(有限集合)にはそれが元の数値比較と一致することを後から確認する」という、証明の方向が逆転した構成になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]]) - 第4章で確立されたMapping Ruleの成分(surj/inj/bijと大小関係の対応、全射↔単射の双対性 A surj B iff B inj A)は、第7章のLemma 7.1.3としてほぼそのまま無限集合に引き継がれる。ただし第7章はこれを無条件に信用せず、「有限集合で成り立つ性質のうちどれが無限集合にも成り立ち、どれが成り立たないか」を逐一検証する姿勢を取る(例: 「要素を1つ足すと真に大きくなる」は不成立)。これは第1章 [[公理的方法]] が強調する「直観を無条件に信用せず、成り立つことを毎回証明する」という方針が、濃度という具体的な題材で実践されている例になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]]) - 第14章(Cardinality Rules)は、第4章のMapping Ruleの2つの成分をそれぞれ独立した「原理」として再利用し、数え上げの実践的な道具箱へ展開する。全単射版(A bij B iff |A|=|B|)は「全単射の規則(Bijection Rule)」と改名され、未知の集合を数えやすい数列に帰着させる第14章全体の戦略の出発点になる(§14.1.1)。単射版(A inj B iff |A|≤|B|)は対偶を取ることで「鳩の巣原理(Pigeonhole Principle)」になり、|A|>|B|ならば全域関数f: A→Bは単射になり得ないという非構成的証明の道具に転じる(§14.8)。つまり第4章が抽象的な濃度比較のために用意した1つの定理(Mapping Rule)が、第14章では用途に応じて2つの異なる名前の「原理」に分岐して実践投入される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.1.1, §14.8) ## 未解決の問い - Mapping Ruleの単射版(A inj B iff |A| ≤ |B|)は、A surj B iff B inj A という対応を経由して全射版から導かれている。第14章では単射版が鳩の巣原理として、全単射版が全単射の規則として再利用されることを確認できたが、**全射版**(A surj B iff |A|≥|B|)が数え上げでどう再利用されるかは第14章では明示的に現れなかった。第14章の除法の規則(k-to-1写像による補正)がこの全射版の実践的な特殊化に当たる可能性があり、後続章または再確認時に検討したい。 - 第7章は無限集合の「大きさ」そのもの(基数, cardinal number)の定義を意図的に避け、比較関係(strict/bij/surj)だけを扱う(「Warning: We haven't, and won't, define what the 'size' of an infinite set is」)。第14章 Cardinality Rules がこの比較関係をどこまで数え上げの道具として一般化するか、また基数そのものの定義に踏み込むかを確認する必要がある。 - Cantorの定理により N strict pow(N) strict pow(pow(N)) strict ... という無限に続く濃度の階層が存在することが示された。この階層のどこに一般の可算集合・非可算集合(例えば実数R)が位置づけられるかは、連続体仮説(N と pow(N) の間に濃度を持つ集合が存在するか)という未解決問題に直結する(第7章§7.4、[[公理的方法]] を参照)。 ## 関連 - 概念: [[関数]] / [[二項関係]] / [[集合]] / [[対角線論法]](Cantorの定理の証明技法) / [[停止性問題]] / [[公理的方法]] / [[数え上げ]](全単射の規則として再利用) / [[鳩の巣原理]](単射版の対偶として再利用) - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 7 Infinite Sets]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] - 実体: [[Georg Cantor]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 4, Chapter 7, Chapter 14.