記号論理
Leopold LöwenheimとThoralf Skolemは、Löwenheim-Skolem定理を得ました。Skolemは、この定理が集合論の一階形式化にも適用され、そのような形式化が可算モデルを持つことを意味することに気付きました。この直感に反する事実は、「スコレムのパラドックス」として知られるようになりました。
クルト・ゲーデルは博士論文の中で、一階論理の構文と意味の対応を示す「完全性定理」を証明しました。ゲーデルは、この完全性定理を用いてコンパクトネス定理を証明し、一階論理の帰結が有限であることを示しました。これらの結果により、一階論理は数学者の間で主流の論理として定着しました。
1931年、ゲーデルは『Mathematica と関連する体系の形式的に決定不可能な命題について』を発表し、十分に強い有効な一階理論がすべて不完全であることを証明しました。この結果は「ゲーデルの不完全性定理」として知られ、数学の公理的基礎に厳しい制限を設け、ヒルベルトの計画に強い打撃を与えました。ゲーデルの不完全性定理は、形式的な算術理論では算術の一貫性を証明することができないことを示しています。しかし、ヒルベルトはしばらくの間、不完全性定理の重要性を認識していませんでした。
ゲーデルの定理は、十分に強い有効な公理系の無矛盾性証明は、その公理系が無矛盾であれば、その公理系自体にも、それよりも弱い公理系にも得られないことを示しています。このことから、検討している体系の中で形式化できない無矛盾性証明の可能性が残されています。ゲンツェンは、有限主義的な体系と超限帰納法の原理を用いて、算術の無矛盾性を証明しました。ゲンツェンの結果は、カット・エリミネーションや証明論的序列の考え方を導入し、証明論の重要なツールとなりました。ゲーデルは、古典的な算術の無矛盾性を、より高い型における直観主義的算術の無矛盾性に還元するという、異なる無矛盾性の証明を行いました。
1896年、『不思議の国のアリス』の作者ルイス・キャロルが、一般向けの記号論理学の教科書を初めて書きました。

他の分野のはじまり
アルフレッド・タルスキーがモデル理論の基礎を開発した。
1935年以降、著名な数学者たちがニコラ・ブルバキというペンネームで、数学の百科事典「Éléments de mathématique」を出版した。厳格で公理的な文体で書かれたこれらのテキストは、厳密な表現と集合論的な基礎を重視していた。双射、注入、超射などの造語や、集合論的な考え方は、数学の世界に広く浸透していった。
計算可能性の研究は、再帰理論または計算可能性理論と呼ばれるようになりました。これは、ゲーデルやクレーネによる初期の形式化が、関数の再帰的な定義に基づいていたためです。これらの定義が、チューリングマシンを用いたチューリングの形式化と等価であることが示されたとき、新しい概念である計算可能な関数が発見されたことが明らかになりました。ゲーデルは、1931年の不完全性定理の研究において、有効な形式システムの厳密な概念を持っていませんでしたが、計算可能性の新しい定義がこの目的のために使用できることにすぐに気づき、元の論文では暗示されていただけの一般性を持って不完全性定理を述べることができるようになりました。
1940年代には、スティーブン・コール・クレーネとエミール・レオン・ポストが再帰理論で多くの結果を出した。Kleeneは、チューリングが予言した相対的な計算可能性や、算術的な階層の概念を導入した。Kleeneは後に再帰理論を高階の関数に一般化した。KleeneとGeorg Kreiselは、直観主義数学の形式的バージョンを、特に証明論の文脈で研究した。