1900年、ダフィット・ヒルベルトはヒルベルトの23の問題の幾つかを次の世紀へと提出した。その最初の2つは連続体仮説の解決と初等算術（実数論）の無矛盾性の証明であった。第10番は整数上の多変数多項式からなる方程式（ディオファントス方程式）が解を持つかを決定する手続きを求めるものであった。これらの問題を解くための次なる仕事によって、数理論理学の方向性が決定づけられ、1928年に提出されたヒルベルトのEntscheidungsproblem（英語版）（決定問題）を解決する努力へと向かうことになった。この問題は与えられた形式化された数学的言明について、それが真か偽かを決定する手続きを問うものである。
集合論とパラドックス

エルンスト・ツェルメロ（1904）は任意の集合が整列可能であることの証明を与えた。この結果はゲオルク・カントールには得ることができなかったものである。ツェルメロはその証明を完成させるために選択公理を導入した。これは数学者と集合論の先駆者達の間の激しい論戦と研究を引き起こすことになる。即座に浴びた批判から、ツェルメロは自身の結果の第2の解説を出版した（Zermelo 1908a）。この論文はツェルメロの証明に対する批判に直接対処するものであり、これによって数学界において選択公理が広く受け入れられることになった。

選択公理に関する疑念は最近の素朴集合論におけるパラドックスの発見により強化された。集合論のパラドックスについて初めて述べたのはチェザーレ・ブラリ・フォルティ（1897）である：ブラリ＝フォルティのパラドックスは全ての順序数からなる集まりが集合を成さないことを示す。その直後に、バートランド・ラッセルは1901年にラッセルのパラドックスを、ジュール・リシャール（1905）はリシャールのパラドックスを発見した。

ツェルメロ（1908b）は集合論に対する最初の公理化を与えた。ツェルメロの公理にアドルフ・フレンケルによる置換公理を加えたものは今日ではツェルメロ＝フレンケル集合論（ZF）の名で知られる。ツェルメロの公理にはラッセルのパラドックスを回避するためのサイズの制限の原理が組み込まれた。

1910年にアルフレッド・ノース・ホワイトヘッドとバートランド・ラッセルによる プリンキピア・マテマティカ の第一巻が出版された。この重要な著作は、関数と基数に関する理論を型理論の完全に形式的な枠組みの中で展開した。型理論はパラドックスを回避するラッセルとホワイトヘッドの努力のもとに開発されたものである。型理論の枠組みは数学の基礎理論として普及しなかったが(Ferreiros 2001, p. 445)、プリンキピア・マテマティカ は20世紀の最も影響力のある研究のひとつと見做されている。

フレンケル(1922)は、選択公理が原子（英語版）付きツェルメロ集合論の残りの公理からは証明できないことを証明した。後のポール・コーエン(1966)による仕事は、（その証明には）原子の追加が不要であって、選択公理はZFにおいて証明不可能であることを示した。コーエンの証明は強制法の手法を生み、今日では集合論における独立性結果（英語版）を確立するための重要なツールとなっている[注 5]。
記号論理

レオポルト・レーヴェンハイム（英語版）（1915）とトアルフ・スコーレム（1920）はレーヴェンハイム-スコーレムの定理を得た。これは一階述語論理は無限構造の濃度を制御できないことを述べる。スコーレムは、この定理を一階で形式化された集合論へ適用でき、そのいかなる形式化も可算モデルを持つことが導かれる、ということに気付いた。この直観に反する結果はスコーレムのパラドックスとして知られることになった。

ゲーデルは自身の博士論文（1929）において完全性定理を示した。これは一階論理における構文論と意味論の間の対応を確立する。ゲーデルは完全性定理をコンパクト性定理の証明に用いた。これは一階の論理的帰結の有限性を立証する。これらの結果は一階論理を数学者にとって支配的な論理として確立することを助けた。

1931年、ゲーデルはプリンキピア・マテマティカとそれに関連する体系において形式的に決定不可能な命題について（英語版）を出版した。ここでは、十分に強く、実効的な一階理論が不完全（完全性定理のそれとは異なる意味である）であることを示されている。この結果はゲーデルの不完全性定理として知られ、数学の公理的基礎の厳密な限界を示すものであり、ヒルベルト・プログラムに大きな打撃を与えた。これは算術の無矛盾性をいかなる算術の形式理論においても証明できないことを示している。しかしながら、ヒルベルトは、不完全性定理の重要性を、あるときまで認めなかった。

ゲーデルの定理は十分に強く、実効的な公理系の無矛盾性の証明はそれが無矛盾である限り、それ自身からもそれよりも弱い体系からも得られないことを示す。これはいま考えている体系で形式化できないような無矛盾性証明の可能性については未解決のまま残す。ゲンツェン（1936）は算術の無矛盾性を超限帰納法の原理を持つ有限的な体系を用いて証明した。ゲンツェンの結果はカット除去と証明論的順序数の概念を生み出し、これらは証明論における主要な道具となった。ゲーデル（1958）は別の無矛盾性証明を与えた。これは古典算術の無矛盾性を高階直観主義算術の無矛盾性に還元することで為された。
他の分科の始まり

アルフレッド・タルスキはモデル理論の基礎を発展させた。

1935年初頭、著名な数学者らは網羅的な数学の教科書のシリーズを出版するためにニコラ・ブルバキというペンネームで集結した。これらの教科書は禁欲的かつ公理的に記述されており、厳格な記述と集合論的な基礎を強調した。これらの教科書から生まれた用語、例えば全単射、単射、全射や、教科書で採用された集合論的な基礎は、広く数学に採用された。

計算可能性の研究は再帰理論として知られるようになった。これはゲーデルとクリーネによる計算可能性の初期の定式化が関数の再帰的定義に基づいていたことによる[注 6]。それらの定義がチューリングによるチューリング機械を用いた定式化と同値であることが示されたことで、計算可能関数という新しい概念が見出され、またこの定義が多数の独立な特徴付けを許すようなロバスト性を持つことが明らかになった。1931年の不完全性定理に関するゲーデルの仕事では、実効的な形式的体系の厳格な概念（規定）を欠いていた。ゲーデルは計算可能性の新しい定義が不完全性定理の設定の一般化に使えることに気付いた。

再帰理論における多くの結果は1940年代にスティーヴン・コール・クリーネとエミール・ポストによって得られた。クリーネ（1943）は相対的計算可能性と算術的階層の概念を導入した。前者はチューリング（1939）で暗示されていたものである。クリーネは後に再帰理論を高階汎関数へ一般化した。クリーネとクライゼルは形式的な直観主義数学、とくに再帰理論の文脈でのそれを研究した。
形式論理体系

数理論理学の中心では形式論理体系を用いて表現された数学の概念を取り扱う。それらの体系は、多くの細部の差異はあるが、固定した形式言語で記述されるという共通の性質がある。命題論理と一階述語論理の体系は今日では最も広く研究されている。それは数学基礎論への応用可能性とそれらの望ましい証明論的な性質の故である[注 7]。より強い古典論理、例えば二階述語論理や無限論理もまた直観主義論理とともに研究されている。
一階述語論理詳細は「一階述語論理」を参照

一階論理は特定の形式的体系である。その構文論（証明論）は有限個の表現―構文的に正しい（well-formed）式だけからなるが、その意味論は量化子を固定された議論領域への制限として特徴付けられる。