レーヴェンハイム–スコーレムの定理
レーヴェンハイム-スコーレムの定理はこの希望への最初の打撃となった。なぜなら、その定理によれば無限のモデルを持つ一階の理論は範疇的にはなり得ないからである。さらに1931年、ゲーデルの不完全性定理によって希望は完全に打ち砕かれた。
レーヴェンハイム-スコーレムの定理から導かれる結論の多くは、一階とそうでないものの違いがはっきりしていなかった20世紀初頭の論理学者にとっては直観に反していた。例えば、真の算術 (true arithmetic) には非可算なモデルがあり、それらは一階のペアノ算術を満足するが、同時に帰納的でない部分集合を持つ。さらに悩ましかったのは、集合論の可算なモデルの存在である。それにもかかわらず、集合論は実数が非可算であるという文を満たさなければならない。この直観に反するような状況はスコーレムのパラドックスと呼ばれ、可算性 (countability) は絶対的 (absolute) ではないことを示している。