Product Design, Manufacturing & Innovation Resources
家 » 有理数の可算性

有理数の可算性

1874
  • Georg Cantor
19th-century mathematician studying countability of rational numbers in an office.

(画像はイメージです)

有理数の集合 [latex]mathbb{Q}[/latex] は、任意の異なる 2 つの有理数の間に別の有理数が存在するという稠密性を持つにもかかわらず、可算無限です。これは、すべての有理数を自然数 [latex]mathbb{N} = {1, 2, 3, …}[/latex] と 1 対 1 で対応させることができることを意味します。この驚くべき結果は、[latex]mathbb{Q}[/latex] が [latex]mathbb{N}[/latex] および [latex]mathbb{Z}[/latex] と同じ濃度を持つことを示しています。

ゲオルク・カントールの有理数の可算性の証明は、集合論の発展と無限の理解における画期的な出来事でした。その証明は構成的かつ優雅です。一般的な方法の一つは、すべての正の有理数[latex]p/q[/latex]を、行インデックス[latex]p[/latex]、列インデックス[latex]q[/latex]の2次元グリッドに配置することです。そして、[latex]1/1[/latex]から始めて、[latex]2/1, 1/2[/latex]、[latex]3/1, 2/2, 1/3[/latex]、といったように、このグリッドを対角線に沿って辿ることができます。この経路はカントールの対角線論法として知られていますが(ただし、この用語は実数の非可算性の証明でより有名です)、すべての正の有理数を体系的に列挙します。 有理数.

走査中、各有理数が一度だけカウントされるように、既約分数でない分数 ([latex]2/2[/latex] や [latex]2/4[/latex] など) はスキップされます。このプロセスにより、すべての正の有理数の順序付きリストが作成されます。すべての有理数を含めるには、正のリストと負のリストを交互に配置し、先頭にゼロを配置します。[latex]0, 1, -1, 1/2, -1/2, 2, -2, …[/latex]。これにより、自然数の集合と有理数の集合の間に全単射が明示的に構築され、[latex]mathbb{Q}[/latex] が可算であることが証明されます。

この結果は、有理数が密であることから直感に反する。任意の2つの有理数の間には必ず別の有理数(例えば、それらの平均値)が存在するため、有理数は明確なギャップを持つ整数よりも「数が多い」ように思われる。カントールの証明は、この直感が誤解を招くものであり、無限集合の「大きさ」(濃度)はより微妙なものであることを示す。彼は後に実数の集合が非可算集合であることを証明し、無限の階層構造を確立した。

UNESCO Nomenclature: 1101
代数学、数論、群論

タイプ

抽象システム

混乱

増分

使用法

概念的/理論的

前駆物質

  • 一対一対応(全単射)の概念
  • ボルツァーノによる無限集合に関する初期の研究
  • 厳密な数学的解析の発展
  • 集合の概念

アプリケーション

  • 集合論の基礎
  • コンピュータ科学における計算理論(例:可能なすべてのコンピュータプログラムの集合が可算集合であることを示す)
  • 可算集合の測度がゼロである測度論
  • 無限集合の異なるサイズを区別する(例:有理数と実数)

特許:

NA

潜在的なイノベーションのアイデア

  • a task scheduling algorithm for distributed computing that uses a Cantor-like enumeration to assign jobs to an infinite-seeming stream of processors
  • a data serialization format that can uniquely encode any rational-based data structure into a single integer
  • a theoretical model for a universal computing machine with a countably infinite number of states
  • a network addressing protocol that can assign a unique address to a potentially infinite number of devices using a rational number enumeration
  • a method for indexing elements in a dynamically growing, multi-dimensional database by mapping coordinates to a single countable index
  • a procedural content generation algorithm for ビデオゲーム that creates an infinitely large but navigable world by mapping locations to rational numbers
  • a formal language definition where valid statements correspond to rational numbers, allowing for unique enumeration of all possible programs
  • a proof-of-stake blockchain protocol where validator selection is based on a deterministic traversal of the set of rational numbers
  • a compression scheme for sparse matrices by mapping non-zero element coordinates to a single integer index
  • a genetic algorithm that explores a solution space by traversing a rational grid, ensuring all potential fractional parameters are eventually tested
関連: 可算性、集合論、ゲオルク・カントール、無限集合、濃度、全単射、自然数、稠密集合、対角線引数、アレフヌル。

歴史的背景

有理数の可算性

1790
1800
1844
1874
1893
1900
1779
1799
1801
1850
1875
1897
1950

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

10年目 周年

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。