The concepts of formal provability and logical consequence in first order logic are introduced, and their equivalence is proved in the soundness and completeness theorems. Goedel’s incompleteness theorem is discussed, making use of the halting problem of computability theory. Relative computability and the Turing degrees are further studied. Prereq: PMATH 345 or 346; Not open to General Mathematics students