Completeness in the Shadow of Decidability

This dissertation investigates the origins of the completeness theorem for first-order predicate logic in the algebraic logic work of L\"{o}wenheim and Skolem. When G\"{o}del proved the completeness theorem in 1929, he was unaware that all the components of a completeness proof were already contained in earlier papers by L\"{o}wenheim and Skolem in which they prove the model-theoretic result known as the L\"{o}wenheim-Skolem theorem. This is not, however, a question of G\"{o}del’s completeness proof having been preempted. For neither were L\"{o}wenheim or Skolem show recognition of the result that G\"{o}del would later make explicit. When the similarity between the proofs was noticed in the 1950s, the fact that Skolem in particular had not put the pieces together to prove completeness before G\"{o}del seemed a puzzling oversight. G\"{o}del offered his own answer to the puzzle, appealing to alleged prejudices Skolem had against transfinite methods of reasoning. Chapter One shows how the puzzle emerged and how G\"{o}del purported to explain it. Chapters Two and Three give reconstructions of the original proofs of L\"{o}wenheim and G\"{o}del. I analyze the meaning of G\"{o}del’s claim that ``finitary prejudices’’ were at the heart of the failure to recognize completeness, and assess the evidence for this claim in L\"{o}wenheim and Skolem. Chapter Four reconstructs Skolem’s proof of L\"{o}wenheim’s theorem and establishes the technical background to understand the relation it bears to the completeness theorem. In Chapter 5, I argue that G\"{o}del’s own answer to the puzzle rests on a false premise. When certain contextual features are accounted for, Skolem’s failure to recognize a completeness theorem in his own work is not the oversight it now seems. I investigate Skolem’s search for a decidability proof for first-order logic and the role this played in leading Skolem away from the discovery of completeness