数学的基盤（集合・論理・計算）

総合・百科・序論 — 数学的基盤（集合・論理・計算） 概要

総合・百科・序論分野の数学的基盤（集合・論理・計算）領域の概要と入門ガイド

集合の概念

ゲオルク・カントールの1874年論文から、明確に区別できる対象を一つの集合として扱う方法を学ぶ

要素と部分集合

カントールの集合論を基に、所属記号と包含記号で要素と集合間の異なる関係を表す方法を学ぶ

集合演算

ジョン・ヴェンの1880年図式から、和集合・共通部分・補集合を領域の重なりとして理解する

濃度と対角線論法

カントールの1891年対角線論法から、実数集合が自然数集合より大きいことを証明する

ラッセルのパラドックス

バートランド・ラッセルが1901年に発見した自己包含集合の矛盾から、素朴集合論の限界を学ぶ

公理的集合論

ツェルメロの1908年公理系から、集合の生成規則を制限してパラドックスを避ける方法を読む

選択公理

ツェルメロが1904年に用いた選択公理から、無限個の非空集合より代表元を選ぶ原理を学ぶ

関係と直積

デカルトの1637年座標幾何を起点に、順序対の集合として二項関係を表す方法を理解する

関数

ディリクレの1837年定義から、各入力へただ一つの出力を対応させる写像の概念を学ぶ

同値関係

ガウスの1801年合同式を例に、反射・対称・推移を満たす関係が集合を類へ分割する仕組みを読む

順序関係

リヒャルト・デーデキントの1872年切断を例に、全順序を用いて実数を構成する方法を学ぶ

命題論理

ジョージ・ブールの1854年論理代数から、真偽命題を否定・連言・選言で計算する方法を学ぶ

述語論理

ゴットロープ・フレーゲの1879年概念記法から、対象・述語・量化を形式化する仕組みを学ぶ

真理値表

ウィトゲンシュタインの1921年論理哲学論考から、複合命題の真偽を表で決める方法を理解する

全称量化と存在量化

フレーゲの1879年概念記法を基に、すべてとあるものを変項の範囲として表す方法を学ぶ

自然演繹

ゲルハルト・ゲンツェンの1934年推論体系から、論理結合子の導入・除去規則で証明を組み立てる

モデル理論

アルフレト・タルスキの1935年真理定義から、形式言語を満たす数学的構造としてモデルを捉える

完全性定理

クルト・ゲーデルの1930年完全性定理から、意味的に妥当な一階論理式が証明可能であることを学ぶ

不完全性定理

ゲーデルの1931年定理から、十分強い無矛盾な形式体系に証明不能な命題が存在することを学ぶ

チューリング機械

アラン・チューリングの1936年論文から、読み書きヘッドとテープで計算手続きを形式化する

ラムダ計算

アロンゾ・チャーチの1936年ラムダ計算から、関数の抽象化と適用だけで計算を表す方法を学ぶ

再帰関数

スティーヴン・クリーネの1936年研究から、初期関数と再帰規則で計算可能性を定義する

チャーチ＝チューリング・テーゼ

チャーチとチューリングの1936年成果から、実効的計算と形式機械の計算能力を同一視する構想を読む

停止性問題

チューリングの1936年証明から、任意のプログラムが停止するかを判定する万能手続きの不可能性を学ぶ

アルゴリズム

ユークリッド原論の最大公約数計算法から、有限の明確な手順で問題を解く概念を理解する

P対NP問題

スティーヴン・クックの1971年定理から、解の検証が速い問題を速く解けるかという難問を学ぶ

論理回路とブール代数

クロード・シャノンの1937年修士論文から、スイッチ回路をブール演算で設計する方法を学ぶ

二進法

ライプニッツの1703年二進算術論から、0と1だけで整数と演算を表現する仕組みを学ぶ

圏論

アイレンベルグとマックレーンの1945年論文から、対象より写像の合成を中心に構造を捉える

型理論

ペール・マルティン＝レーフの1972年直観主義型理論から、命題を型、証明を項として扱う方法を学ぶ