数理論理学
論理に関する理論は多くの文化と歴史の中で発展してきた。その中には中国、インド、ギリシャ、イスラーム世界が含まれる。18世紀のヨーロッパでは、形式論理の演算子を記号的または代数的な方法の中で取り扱おうという試みが、哲学的数学者によってなされた。その中にはゴットフリート・ライプニッツとランベルトが含まれる。しかしライプニッツらの仕事は孤立して残っているばかりでよく知られていない。
モデル理論は様々な形式理論のモデルを研究する。ここで理論(英語版)とは特定の形式論理に於ける論理式とシグネチャ(英語版)からなる集まりで、モデル(英語版)とはその理論の具体的な解釈を与える構造である。モデル理論は普遍代数と代数幾何学に密接に関係しているが、モデル理論の手法は他の分野よりも論理的な考察に重きを置いている。
特定の理論の全てのモデルからなる集合は初等クラスと呼ばれる;古典モデル理論は特定の初等クラスの性質を決定しようとしたり、あるいは構造からなる或るクラスが初等クラスとなるか否かを決定しようとする。
量化記号消去の手法は特定の理論における定義可能集合がそこまで複雑ではないことを示すことに使える。タルスキ(1948)は実閉体の量化記号消去(これは実数体の理論が決定可能であることをも示す結果である)を確立した。(彼はまた自身の手法が任意の標数の代数閉体にもそのまま適用可能であることを指摘した。)ここから発展した現代的な副分野は順序極小構造(英語版)に関わる。
マイケル・D・モーレイ(英語版)(1965)によって証明されたモーレイの範疇性定理(英語版)は、もし可算言語上の一階理論が或る非可算濃度について範疇的(つまりその濃度を持つ全てのモデルが同型)ならば、全ての非可算濃度で範疇的となることを述べる。
連続体仮説からの自明な帰結として、連続体濃度個未満の互いに非同型な可算モデルを持つような完全理論はそれ(非同型モデル)をちょうど可算個だけ持つこと、がある。ロバート・ローソン・ヴォート(英語版)に因むヴォート予想(英語版)はこれが連続体仮説とは無関係に真であることを主張する。この予想は多くの特別なケースについて確立されている。
再帰理論(計算可能性理論とも呼ばれる)は計算可能関数とチューリング次数(これは計算不可能関数を同じレベルの計算不可能性を持つ集合に分ける)の性質を研究する。再帰理論はまた一般計算可能性と定義可能性の研究を含む。再帰理論はアロンゾ・チャーチとアラン・チューリングによる1930年代の仕事(これはクリーネとポストによって1940年代に大きく拡張された)から生まれた。
古典再帰理論は自然数から自然数への関数の計算可能性に着目する。基本的な結果は、チューリング機械やラムダ計算やその他のシステムなど、多数の独立だが同値な特徴づけを持つ、ロバストかつカノニカルな計算可能関数のクラスを確立したことである。より高度な結果はチューリング次数の構造や帰納的可算集合の成す束に関するものである。
一般再帰理論は再帰理論の諸概念をもはや有限ではないような計算へと拡張する。そこには高階の型の計算可能性の研究や超算術的理論(英語版)やアルファ再帰理論(英語版)などの分野を同様に含む。
再帰理論の現代的研究には、純粋な再帰理論の新しい結果と同様に、その応用研究(例えばアルゴリズム的ランダム性、計算可能モデル理論(英語版)、逆数学など)が含まれる。