What are the soundness and completeness theorems in logic all about?

academics logic

If you’re interested in logic, you’ve probably heard of the soundness and completeness theorems. They’re the first major results proved in a logic class. Their proofs can get messy and technical, especially the proof of completeness. What the theorems are really supposed to tell us and why it’s interesting often gets lost in all that technicality. So let’s take a step back and see what these theorems are all about.

What is logic about?

Logic can be thought of as the study of some very special words: not, and, or, if-then, all, and some. The logical form of a sentence is its structure with respect to these unique words. Consider, for example, the sentences “If Kumi went to the park and didn’t bring an umbrella, then she got stuck in the rain” and “If Phil was at the house and awake, then he saw it happen.” Though different in important ways, they both have the logical form: If A and B, then C.

A sentence is valid if it is true solely in virtue of its logical form. “Irene is hungry or Irene is not hungry” is valid, because we don’t need to know anything about Irene, or about hunger, to know whether it is true. All we need to know is that it has the logical form A or not A. All sentences with this form are true, no matter what A is. “Batman is Bruce Wayne and Spiderman is Peter Parker”, while certainly true, is not valid. Not every sentence with its form, A and B, is true.

Validity

How do we check if a sentence is valid? Let’s look at the sentence about Irene again. For the purposes of logic, it doesn’t matter what “Irene” and “hungry” mean. For all we care, “Irene” could be the name of Wilson the volleyball; and “hungry” could actually mean elated. If we substituted these changes, we would get: “Wilson is elated or not elated.” What logicians do is consider every possible way of changing the meaning of every word in the sentence except the logical words. Each of these possible ways is called a model. So there’s a model where “Irene” is the name of a particular rock in Iceland and “hungry” means 12.3 meters long; another where “Irene” is the name of my cat and “hungry” actually means hungry. But in all these models, “not” still means not and “or” still means or.

To find out if a sentence is valid, we check if it is true in every single model. If it is, then it’s valid.

Provability

Another important logical concept is provability. A proof system is a kind of procedure for writing down sentences, one after the other. A proof system is sort of like chess: there are clear rules for what moves are allowed and what moves are not allowed. So long as a move is allowed, you can play it.

Proof systems are defined by two things: their axioms and their rules of inference. The axioms are the sentences that the proof system gives you for free. For example, a proof system might have every sentence of the form If A, then A as axioms. In that case, I am always allowed to write down, say, “If I am a judge, then I am judge”, or “If the ball is red, then the ball is red” at any point in my sequence of sentences.

A rule of inference is a rule that tells you that if you’ve already written down sentences of certain forms, then you’re allowed to write down certain other sentences. For example, a typical inference rule is one that says: If you’ve already written down a sentence A and a sentence B, you’re allowed to write down the sentence A and B. For example, if I’ve written down the two example axioms I listed above, then this rule says I can now write down the (very weird) sentence “If the ball is red, then the ball is red AND if I am a judge, then I am judge.”

A sentence is called provable in a proof system if, following the rules of the system, the system ever allows you to write it down.

Soundness and completeness

Given a certain proof system, the soundness theorem says that only valid sentences are provable in it. The completeness theorem says that every valid sentence is provable in it. Together, they tell us that provability in that proof system exactly coincides with validity. The provable sentences and the valid ones are exactly the same sentences.

Why do logicians care about this? Well, in a nutshell, validity and provability represent the two main ways logicians have for thinking about logic. The concept of validity is designed to capture the meaning of the special logical words, and how those meanings contribute to the truth or falsity of sentences. The concept of provability, on the other hand, captures how we reason with these special words. What soundness shows is that ideal logical reasoning does not lead us astray. When we prove something logically, the actual meaning of the logical words agrees with what we’ve proved. Meanwhile, completeness shows that ideal logical reasoning allows us to prove everything that really is true by the meaning of logical words alone. In other words, there’s nothing reasoning misses out on. Together, they tell us that, as far as logic goes, proof and meaning are two paths to the same destination—the purely logical truths.

William is a PhD candidate at NYU, writing a dissertation on the philosophy of logic. He previously majored in political science and film production at the Macaulay Honors Program at Brooklyn College, he. His thesis film, “Sugar Packet”, was selected to screen at the Brooklyn Academy of Music and won two awards.

Comments

topicTopics
academics study skills medical school admissions MCAT SAT college admissions expository writing strategy English MD/PhD admissions writing LSAT physics GMAT GRE chemistry academic advice biology graduate admissions math law school admissions ACT interview prep language learning test anxiety personal statements premed career advice MBA admissions AP exams homework help test prep creative writing MD computer science mathematics study schedules Common Application summer activities history secondary applications philosophy research organic chemistry economics supplements 1L grammar statistics & probability PSAT admissions coaching dental admissions psychology law legal studies ESL reading comprehension CARS PhD admissions SSAT covid-19 logic games calculus engineering USMLE medical school mentorship Latin Spanish parents AMCAS admissions advice biochemistry case coaching verbal reasoning DAT English literature STEM excel genetics political science skills French Linguistics MBA coursework Tutoring Approaches academic integrity astrophysics chinese classics dental school gap year letters of recommendation mechanical engineering technical interviews units Anki DO Social Advocacy algebra art history artificial intelligence business careers cell biology data science diversity statement first generation student freewriting geometry graphing kinematics linear algebra mental health presentations quantitative reasoning software engineering study abroad tech industry time management work and activities 2L AAMC DMD IB exams ISEE MD/PhD programs MMI Sentence Correction adjusting to college algorithms amino acids analysis essay argumentative writing athletics business skills cold emails executive function fellowships finance functions genomics information sessions international students internships logic networking office hours poetry pre-dental proofs resume revising scholarships science social sciences trigonometry writer's block 3L Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian JD/MBA admissions Japanese Lagrange multipliers London MD vs PhD Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser burnout campus visits cantonese capacitors capital markets central limit theorem centrifugal force chem/phys chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism embryology entropy escape velocity evolution extracurriculars fundraising harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports letter of continued interest linear maps mandarin chinese