可算集合

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "可算集合" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年10月)

可算集合（かさんしゅうごう、英語: countable set または denumerable set）または可付番集合とは、おおまかには、自然数全体と同じ程度多くの元を持つ集合のことである。各々の元に 1, 2, 3, … と番号を付けることのできる、すなわち元を全て数え上げることのできる無限集合と表現してもよい^[1]。

有限集合も、数え上げることができる集合という意味で、可算集合の一種とみなすことがある^[1]。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を可算無限集合 (countably infinite set) と呼び、可算無限集合と有限集合を合わせて高々可算 (at most countable) の集合と呼ぶ^[2][3]。可算でない無限集合を非可算集合 (uncountable set) という^[4]。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができない。そのような集合の存在は、カントールによって初めて示された。

可算集合とは N と濃度が等しい集合のことである^[1]。すなわち、集合 S が可算であるとは、自然数全体の集合 N との間に全単射が存在することをいう^[2][3]。

また、高々可算な集合とは、N の濃度以下の濃度を持つ集合のことである。すなわち、集合 S が高々可算であるとは、S から N へ単射が存在することをいう。これは、N から S へ全射が存在することと同値である。

慣例では、可算集合の濃度を ${\displaystyle \aleph _{0}}$（アレフゼロ、aleph-null）で表す。例えば、N の濃度が可算であることを ${\displaystyle |\mathbb {N} |=\aleph _{0}}$ などと表す。

無限集合においては、その真部分集合と濃度が等しいことがあり得る。^[3]例えば、偶数の自然数全体の集合 2N は N との間に次の全単射が存在する。

${\displaystyle f\colon \mathbb {N} \ni n\mapsto 2n\in 2\mathbb {N} .}$

よって、2N は可算集合である。また、整数全体の集合 Z や有理数全体の集合 Q も可算である^[1][4]。しかし、実数全体の集合 R は非可算である。この事実はカントールの対角線論法によって示される^[1][4]。R の濃度は連続体濃度と呼ばれ、${\displaystyle \aleph }$ または ${\displaystyle {\mathfrak {c}}}$ で表される。

選択公理を認めるならば、可算濃度は無限集合の濃度のうち最小のものであることが示される。可算濃度と連続体濃度の間に他の濃度が存在するか否かは、ZFC とは独立であり、通常は存在しないと仮定する。この仮定を連続体仮説という。

可算個の可算集合の和集合や、有限個の可算集合の直積集合はまた可算である^[3]。これより、代数的数全体の集合 Q は可算であることが従う。しかし、可算個の可算集合の直積集合や、可算集合の冪集合は非可算であり、その濃度は連続体濃度である^[4]。

可算個の可算集合の直積集合の濃度は、濃度不等式

${\displaystyle 2^{\aleph _{0}}\leq \aleph _{0}^{\aleph _{0}}\leq (2^{\aleph _{0}})^{\aleph _{0}}=2^{\aleph _{0}}}$

によって、${\displaystyle \aleph }$　と等しいことが示される。

• 濃度 (数学)
• 連続体仮説
• ヒルベルトの無限ホテルのパラドックス

表 話 編 歴 集合論
基本	集合 元 包含関係 内包と外延 クラス ベン図
演算	和集合 非交和 共通部分 素集合 直積集合 分割 補集合 差集合 対称差 冪集合 ド・モルガンの法則 集合の代数学
関係	性質 反射関係 推移関係 推移閉包 対称関係 非対称関係 反対称関係 完全関係 同値関係 同値類 well-defined 整礎関係 逆関係 関係の合成 写像 定義域 終域 値域 単射 全射 全単射 逆写像 像と逆像 恒等写像 制限 包含写像 合成 射影 商写像 指示関数 配置集合 族 添字集合 順序対 順序組 列 集合族 グラフ 部分写像 対応 順序 前順序 有向 半順序 全順序 整列 稠密 有界 単調写像 順序同型 辞書式順序 順序型 推移的集合 順序数 0 後続 極限 自然数 ハッセ図 超限帰納法 ツォルンの補題 整列可能定理 整礎的集合 フォン・ノイマン宇宙
濃度	有限集合 空集合 単集合 遺伝的 可算集合 非可算集合 連続体濃度 始順序数 共終数 基数 正則 到達不能 巨大 一覧 ベルンシュタインの定理 カントールの対角線論法 カントールの定理 連続体仮説
公理化	素朴集合論 ラッセルのパラドックス 公理的集合論 ツェルメロ＝フレンケル集合論 フォン・ノイマン＝ベルナイス＝ゲーデル集合論 モース-ケリー集合論 新基礎集合論 外延性の公理 空集合の公理 分出公理 対の公理 和集合の公理 冪集合公理 置換公理 無限公理 正則性公理 選択公理 可算 従属
研究者	ゲオルク・カントール リヒャルト・デーデキント バートランド・ラッセル エルンスト・ツェルメロ アドルフ・フレンケル ジョン・フォン・ノイマン クルト・ゲーデル ポール・コーエン
カテゴリ

この項目は、集合論に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集