数理論理学
{\displaystyle (x=0)\lor (x=1)\lor (x=2)\lor \cdots .}
高階述語論理は議論領域の要素だけではなく議論領域の部分集合(述語)、議論領域の冪集合の部分集合(述語の述語)、さらに高階の対象に対する量化を許した論理である。その意味論は、それぞれの高階型の量化子に対して独立した議論領域を割り当てるよりは、量化子は適切な型の全ての対象に及ぶように定義される。現在の形の一階述語論理が開発される以前に研究されていた論理、例えばフレーゲの論理など、は集合論的な側面を持っていた。高階述語論理はより表現力が高く、自然数の構造の完全な公理化すら可能であるけれども、一階述語論理における完全性やコンパクト性定理に対応する性質を高階述語論理は持たない。また一階述語論理の持つ証明論的なよい性質の多くは高階述語論理では失われている。
他のタイプの論理としては不動点論理があり、これは原始帰納的関数の記述に使われるような帰納的定義を許す。
数学が正確な基礎の上に築かれていなかったことへの不安が、算術、解析、幾何のような数学の基礎的な領域に対する公理系の開発をもたらした。
論理学において、算術とは自然数の理論を意味する。ジュゼッペ・ペアノ(1889)は後に彼の名前が付けられた算術の公理系(ペアノの公理)を発表した。これはブールとシュレーダーの論理体系の変種を用いているが、量化記号が追加されている点で異なる。ペアノはこのときフレーゲの仕事を知らなかった。同時期にリヒャルト・デデキントは、自然数の全体はそれらの帰納法の性質によって一意的に特徴づけられることを示した。デデキント(1888)は別の特徴付けを提案した。その特徴付けは、ペアノの公理にあったような形式論理的な性格を欠いていたが、ペアノの公理においては到達できない定理を証明するものであった。それには自然数の集合の(同型を除いた)一意性と、加法と乗法の後者関数と数学的帰納法に基づく再帰的定義が含まれる。
再帰理論の重要な部分領域ではアルゴリズム的に非可解な問題が研究される;決定問題または関数問題がアルゴリズム的に非可解(英: algorithmically unsolvable)あるいは決定不可能(英: undecidable)とは、任意の合法な入力に対して正しい解を返すような計算可能なアルゴリズムが存在しないことをいう。決定不可能性に関する最初の結果は、1936年にチャーチとチューリングによって独立に得られたもので、一階述語論理の決定問題がアルゴリズム的に非可解であるというものである。チュ―リングはこれを停止性問題の決定不可能性を示すことによって証明した。この結果は再帰理論と計算機科学の双方に広範な示唆を与えるものである。
通常の数学においても多くの決定不可能問題の例が知られている。群の語の問題は1955年のピョートル・ノビコフと1959年のW.ボーンによって独立に証明せられた。ビジービーバー問題は1962年にTibor Radóによって与えられた別のよく知られた例である。
ヒルベルトの第10問題は多変数整数係数代数方程式(ディオファントス方程式)が整数解を持つか否かを決定するアルゴリズムの存在を問うものである。部分的な解答はジュリア・ロビンソン、マーティン・デイビス、ヒラリー・パトナムらによって与えられた。この問題のアルゴリズム的非可解性はユーリ・マチャセヴィッチによって1970年に証明された(Davis 1973)。
20世紀の最初の10年における研究の主領域は集合論と形式論理であった。非形式的な集合論におけるパラドックスの発見は、数学それ自身が無矛盾であるのかを疑わせるものであり、無矛盾性の証明の必要に迫られた。
1900年、ダフィット・ヒルベルトはヒルベルトの23の問題の幾つかを次の世紀へと提出した。その最初の2つは連続体仮説の解決と初等算術(実数論)の無矛盾性の証明であった。第10番は整数上の多変数多項式からなる方程式(ディオファントス方程式)が解を持つかを決定する手続きを求めるものであった。これらの問題を解くための次なる仕事によって、数理論理学の方向性が決定づけられ、1928年に提出されたヒルベルトのEntscheidungsproblem(英語版)(決定問題)を解決する努力へと向かうことになった。この問題は与えられた形式化された数学的言明について、それが真か偽かを決定する手続きを問うものである。