Classical Logic (Stanford Encyclopedia of Philosophy) Cite this entry Search the SEP • Advanced Search • Tools • RSS FeedTable of Contents• What's New• Archives• Projected ContentsEditorial Information• About the SEP• Editorial Board• How to Cite the SEP• Special CharactersSupport the SEPContact the SEP ©Metaphysics Research Lab,CSLI,Stanford University  Open access to the SEP is made possible by a world-wide funding initiative. Please Read How You Can Help Keep the Encyclopedia FreeClassical LogicFirst published Sat Sep 16, 2000Typically, a logic consists of a formal or informal languagetogether with a deductive system and/or a model-theoretic semantics.The language is, or corresponds to, a part of a natural language likeEnglish or Greek. The deductive system is to capture, codify, orsimply record which inferences are correct for the givenlanguage, and the semantics is to capture, codify, or record themeanings, or truth-conditions, or possible truth conditions, for atleast part of the language. The following sections provide the basics of a typical logic,sometimes called "classical elementary logic" or "classicalfirst-order logic". Section 2 develops a formal language, with arigorous syntax and grammar. The formal language is a recursivelydefined collection of strings on a fixed alphabet. As such, it hasno meaning, or perhaps better, the meaning of the formulas is givenby the deductive system and the semantics. Some of the symbols havecounterparts in ordinary language. We define an argument tobe a non-empty collection of formulas in the formal language, one ofwhich is designated to be the conclusion. The other formulas (ifany) in an argument are its premises. Section 3 sets up a deductivesystem for the language, in the spirit of natural deduction. Anargument is derivable if there is a deduction from some ofits premises to its conclusion. Section 4 provides a model-theoreticsemantics. An argument is valid if there is nointerpretation (in the semantics) in which its premises are all trueand its conclusion false. This reflects the longstanding view that avalid argument is truth-preserving. In Section 5, we turn to relationships between the deductive systemand the semantics, and in particular, the relationship betweenderivability and validity. We show that an argument is derivable onlyif it is valid. This pleasant feature, called soundness,entails that no deduction takes one from true premises to a falseconclusion. Thus, deductions preserve truth, and there aren't toomany deductions. Then we establish a converse, calledcompleteness, that an argument is valid only if it isderivable. This establishes that the deductive system is rich enoughto provide a deduction for every valid argument. There are enoughdeductions. All and only valid arguments are derivable. We brieflyindicate other features of the logic, some of which are corollaries tosoundness and completeness. 1. Introduction 2. Language 3. Deduction 4. Semantics 5. Meta-theory Bibliography Other Internet Resources Related Entries1. Introduction Today, logic is both a branch of mathematics and a branch ofphilosophy. In most large universities, both departments offersequences of courses in logic, and there is usually a lot of overlapbetween them. Formal languages, deductive systems, andmodel-theoretic semantics are mathematical objects and, as such, thelogician is interested in their mathematical properties andrelations. Soundness, completeness, and most of the other resultsreported below are typical examples. Philosophically, logic is thestudy of correct reasoning. Reasoning is an epistemic,mental activity. This raises questions concerning the philosophicalrelevance of the mathematical aspects of logic. How do deducibilityand validity, as properties of formal languages--sets of strings on afixed alphabet--relate to correct reasoning? What do themathematical results reported below have to do with the originalphilosophical issue? This is an instance of the philosophicalproblem of explaining how mathematics applies to non-mathematicalreality. Typically, ordinary reasoning takes place in a natural language, orperhaps a natural language augmented with some mathematical symbols. Soour question begins with the relationship between a natural language and aformal language. Without attempting to be comprehensive, it may help tosketch several options on this matter. One view is that the formal languages accurately exhibit actualfeatures of certain fragments of a natural language. Somephilosophers claim that declarative sentences of natural languagehave underlying logical forms and that these forms aredisplayed by formulas of a formal language. Other writers hold that(successful) declarative sentences express propositions; andformulas of formal languages somehow display the forms of thesepropositions. On views like this, the components of a logic providethe underlying deep structure of correct reasoning. A chunk ofreasoning in natural language is correct if the forms underlying thesentences constitute a valid or deducible argument. See for example,Montague [1974], Davidson [1984], Lycan [1984]. Another view, held at least in part by Gottlob Frege and WilhelmLeibniz, is that because natural languages are vague and ambiguous,they should be replaced by formal languages. A similar view,held by W. V. O. Quine (e.g., [1960], [1986]), is that a naturallanguage should be regimented, cleaned up for seriousscientific and metaphysical work. One desideratum of the enterpriseis that the logical structures in the regimented language should betransparent. It should be easy to "read off" the logical propertiesof each sentence. A regimented language is similar to a formallanguage regarding, for example, the explicitly presented rigor ofits syntax and its truth conditions. On a view like this, deducibility and validity representidealizations of correct reasoning in natural language. Achunk of reasoning is correct to the extent that it corresponds to,or can be regimented by, a valid or deducible argument in a formallanguage. When mathematicians and many philosophers reason, they occasionallyinvoke formulas in a formal language to help disambiguate, orotherwise clarify what they mean. In other words, sometimes formulasin a formal language are used in ordinary reasoning. Thissuggests that one might think of a formal language as anaddendum to a natural language. Then our present questionconcerns the relationship between this addendum and the originallanguage. What do deducibility and validity, as sharply defined onthe addendum, tell us about correct reasoning in general? Another view is that a formal language is a mathematicalmodel of a natural language in roughly the same sense as, say, acollection of point masses is a model of a system of physicalobjects, and the Bohr construction is a model of an atom. In otherwords, a formal language displays certain features of naturallanguages, or idealizations thereof, while ignoring or simplifyingother features. The purpose of mathematical models is to shed lighton what they are models of, without claiming that the model isaccurate in all respects or that the model should replace what it isa model of. On a view like this, deducibility and validity representmathematical models of (perhaps different aspects of) correctreasoning in natural languages. Correct chunks of reasoningcorrespond, more or less, to valid or deducible arguments; incorrectchunks of reasoning roughly correspond to invalid or non-deduciblearguments. See, for example, Corcoran [1973] or Shapiro [1998]. There is no need to adjudicate this matter here. Perhaps the truthlies in a combination of the above options, or maybe some otheroption is the correct, or most illuminating one. I raise the matteronly to lend some philosophical perspective to the formal treatmentthat follows.2. LanguageHere we develop the basics of a formal language, or to be precise, aclass of formal languages. Again, a formal language is a recursivelydefined set of strings on a fixed alphabet. Some aspects of theformal languages correspond to, or have counterparts in, naturallanguages like English. Technically, this "counterpart relation" isnot part of the formal development, but I will mention it from timeto time, to motivate some of the features and results.Building blocks We begin with analogues of singular terms, linguistic itemswhose function is to denote a person or object. We call theseterms. We assume a stock of individual constants.These are lower-case letters, near the beginning of the Romanalphabet, with or without numerical subscripts:a, a1, b23, c, d22, etc. We envisage a potential infinity of individual constants. In thepresent system each constant is a single character, and so individualconstants do not have an internal syntax. Thus we have an infinitealphabet. This last could be avoided by taking a constant liked22, for example, to consist of three characters,a lowercase "d" followed by a pair of subscript "2"s. We also assume a stock of individual variables. These arelower-case letters, near the end of the alphabet, with or withoutnumerical subscripts:w, x, y12, z, z4, etc. Variables serve a dual function. Sometimes a variable is used as asingular term to denote a specific, but unspecified (or arbitrary)object. For example, a mathematician might start a derivation: "Letx be a natural number". Variables are also used to expressgenerality, as in the mathematical assertion that for any naturalnumber x, there is a natural number y, such thaty>x and y is prime. Some logiciansemploy different symbols for unspecified objects (sometimes called"individual parameters") and variables used to express generality. Constants and variables are the only terms in our formal language,so all of our terms are simple, corresponding to proper names andpronouns. Some authors also introduce function letters,which allow complex terms corresponding to: "7+4" and "the wife ofBill Clinton", or complex terms containing variables, like "thefather of x" and "x/y". Logic books aimedat mathematicians are likely to contain function letters, probablydue to the centrality of functions to mathematical discourse. Booksaimed at a more general audience (or at philosophy students), mayleave out function letters, since it simplifies the syntax andtheory. We follow the latter route here. This is an instance of ageneral tradeoff between presenting a system with greater expressiveresources, at the cost of making its formal treatment more complex. For each natural number n, we introduce a stock ofn-place predicate letters. These are upper-caseletters at the beginning or middle of the alphabet. A superscriptindicates the number of places, and there may or may not be asubscript. For example, A3, B32, P3, etc. are three-place predicate letters. We often omit the superscript,when no confusion will result. We also add a special two-place symbol"=" for identity. Zero-place predicate letters are sometimes called "sentenceletters". They correspond to free-standing sentences whose internalstructure does not matter. One-place predicate letters, called"monadic predicate letters", correspond to linguistic items denotingproperties, like "being a man", "being red", or "being a primenumber". Two-place predicate letters, "binary predicate letters",correspond to linguistic items denoting binary relations, like "is aparent of" or "is greater than". Three-place predicate letterscorrespond to three-place relations, like "lies on a straight linebetween". And so on. The non-logical terminology of the language consists of itsindividual constants and predicate letters. The symbol "=", foridentity, is not a non-logical symbol. In taking identity to belogical, we provide explicit treatment for it in the deductive systemand the model-theoretic semantics. Most authors do the same, butthere is some controversy over the issue (Quine [1986, Chapter5]). If K is a set of constants and predicate letters, thenwe give the fundamentals of a language  1K= built on this set of non-logical terminology. It may be called thefirst-order language with identity on K. A similarlanguage that lacks the symbol for identity (or which takes identityto be non-logical) may be called 1K,the first-order language without identity on K.Atomic formulas If V is an n-place predicate letter in K,and t1, …, tnare terms of K (i.e., constants in K or variables),then Vt1 … tnis an atomic formula of 1K=. Notice that the terms t1, …,tn need not be distinct. Examples ofatomic formulas include: P4xaab,C1x, C1a,D0, A3abc. The last one is an analogue of a statement that a certain relation(A) holds between three objects (a, b,c). If t1 and t2 areterms, then t1=t2 is anatomic formula of 1K=. It correspondsto an assertion that t1 is identical tot2. If an atomic formula has no variables, then it is called anatomic sentence. If it does have variables, it is called anopen formula. In the above list of examples, the first andsecond are open; the rest are sentences. Compound formulas We now introduce the final items of the lexicon: ¬, &, ∨, →, ∀, ∃, (, ) We give a recursive definition of a formula of 1K=: 1. All atomic formulas of 1K= are formulas of 1K=. 2. If θ is a formula of 1K=, then so is ¬θ. Asserting a sentence corresponding to ¬θ is tantamount to denying the sentence corresponding to θ. The symbol "¬" is called "negation", and is a unary connective. 3. If θ and ψ are formulas of 1K=, then so is (θ & ψ). The ampersand "&" corresponds to the English "and" (when "and" isused to connect sentences). So (θ & ψ) can be read "θ and ψ". The formula (θ & ψ) is called the "conjunction" of θ and ψ. 4. If θ and ψ are formulas of 1K=, then so is (θ ∨ ψ). The wedge "∨" corresponds to "either … or … or both", so (θ ∨ ψ) can be read "θ or ψ". The formula (θ ∨ ψ) is called the "disjunction" of θ and ψ. 5. If θ and ψ are formulas of 1K=, then so is (θ → ψ). The arrow "→" corresponds to "if … then … ", so (θ → ψ) can be read "if θ then ψ" or "θ only if ψ". The symbols "&", "∨", and "→" are called "binaryconnectives", since they serve to "connect" two sentences into one. Someauthors introduce (θ ↔ ψ) as an abbreviation of ((θ → ψ) & (ψ → θ)). The symbol "↔" is an analogue of the locution "if and only if". 6. If θ is a formula of 1K= and v is a variable, then ∀v θ is a formula of 1K=. The symbol "∀" is called a universal quantifier, and is an analogue of "for all"; so ∀vθ can be read "for all v, θ". 7. If θ is a formula of 1K= and v is a variable, then ∃v θ is a formula of 1K=. The symbol "∃" is called anexistential quantifier, and is an analogue of "there exists" or"there is"; so ∃v θ can be read "there is a v such that θ". 8. That's all folks. That is, all formulas areconstructed in accordance with rules (1)-(7). Clause (8) allows us to do inductions on the complexity offormulas. If a certain property holds of the atomic formulas and isclosed under the operations presented in clauses (2)-(7), then theproperty holds of all formulas. We next define the notion of an occurrence of a variable beingfree or bound in a formula. All variables thatoccur in an atomic formula are free. If a variable occurs free (orbound) in θ or in ψ, then that same occurrence is free (or bound) in ¬θ, (θ & ψ), (θ ∨ ψ), and (θ → ψ). That is, the (unary and binary) connectives do not change the status of variables that occur inthem. All occurrences of the variable v in θ are bound in ∀v θ and ∃v θ. Any free occurrences of v in θ are bound by the initial quantifier. All other variables that occur in θ are free or bound in ∀v θ and ∃v θ, as they are in θ. A variable that immediately follows a quantifier (as in "∀x" and "∃y") is neitherfree nor bound. We do not think of those as occurrences of the variable. For example, in the formula (∀x(Axy ∨ Bx) & Bx), the occurrences of "x" in Axy and in the first Bx are bound by thequantifier. The occurrence of "y" and last occurrence of"x" are free. In ∀x(Ax → ∃xBx), the "x" in Ax is bound by the initial universalquantifier, while the other occurrence of x is bound by theexistential quantifier. The above syntax allows this "overlap" of boundvariables, and it does not create an ambiguity, but we will avoid suchformulas, as a matter of taste and clarity. Free variables correspond to place-holders, while bound variablesare used to express generality. If a formula has no free variables,then it is called a sentence. If a formula has freevariables, it is called open. Features of the syntax Before turning to the deductive system and semantics, I mention a fewfeatures of the language, as developed so far. This helps draw thecontrast between formal languages and natural languages like English. We assume at the outset that all of the categories are disjoint. Forexample, no connective is also a quantifier or a variable, and thenon-logical terms are not also parentheses or connectives. Also, theitems within each category are distinct. For example, the sign fordisjunction does not do double-duty as the negation symbol, andperhaps more significantly, no two-place predicate is also aone-place predicate. Theorem 1. Every formula of 1K= has the same number of left and right parentheses. Moreover, eachleft parenthesis corresponds to a unique right parenthesis, whichoccurs to the right of the left parenthesis. Similarly, each rightparenthesis corresponds to a unique left parenthesis, which occurs tothe left of the given right parenthesis. If a parenthesis occursbetween a matched pair of parentheses, then its mate also occurswithin that matched pair. In other words, parentheses that occurwithin a matched pair are themselves matched. Proof: By clause (8), every formula is built upfrom the atomic formulas using clauses (2)-(7). The atomic formulashave no parentheses (by the policy that the categories aredisjoint). Parentheses are introduced only in clauses (3)-(5), andeach time they are introduced as a matched set. So at any stage inthe construction of a formula, the parentheses are paired off. One difference between natural languages like English and formallanguages like 1K= is that the latter are notsupposed to have any ambiguities. Our policy that the differentcategories of symbols do not overlap, and that no symbol doesdouble-duty helps avoid the kind of ambiguity, sometimes called"equivocation", that occurs when a single word has two meanings:"I'll meet you at the bank." But there are other kinds ofambiguity. Consider the English sentence: John is married, and Mary is single, or Joe is crazy. It can mean that John is married and either Mary is single or Joe iscrazy, or else it can mean that either both John is married and Maryis single, or else Joe is crazy. An ambiguity like this, due todifferent ways to parse the same sentence, is sometimes called an"amphiboly". If our formal language did not have the parentheses init, it would have amphibolies. For example, there would be a"formula" A & B ∨ C. Is thissupposed to be ((A & B) ∨ C), or is it(A & (B ∨ C))? The parenthesesresolve what would be an amphiboly. Can we be sure that there are no other amphibolies in our language?That is, can we be sure that each formula of 1K= can be puttogether in only one way? Showing this is our next task. Let us temporarily use the term "unary marker" for the negationsymbol (¬) or a quantifier followed by a variable (e.g., ∀x, ∃z). Lemma 2. Each formula consists of a string of zeroor more unary markers followed by either an atomic formula or aformula produced using a binary connective, via one of clauses(3)-(5). Proof: We proceed by induction on the complexity ofthe formula or, in other words, on the number of formation rules thatare applied. The Lemma clearly holds for atomic formulas. Letn be a natural number, and suppose that the Lemma holds forany formula constructed from n or fewer instances of clauses(2)-(7). Let θ be a formula constructed from n+1 instances. The Lemma holds if the lastclause used to construct θ waseither (3), (4), or (5). If the last clause used to construct θ was (2), then θ is ¬ψ. Since ψ was constructed withn instances of the rule, the Lemma holds for ψ (by the induction hypothesis), and so it holds for θ. Similar reasoning shows the Lemma to hold for θ if the last clause was (6) or (7). By clause (8), this exhausts thecases, and so the Lemma holds for θ, by induction. Lemma 3. If a formula θ contains a left parenthesis,then it ends with a right parenthesis, which matches the leftmost leftparenthesis in θ. Proof: Here we also proceed by induction on thenumber of instances of (2)-(7) used to construct theformula. Clearly, the Lemma holds for atomic formulas, since theyhave no parentheses. Suppose, then, that the Lemma holds for formulasconstructed with n or fewer instances of (2)-(7), and let θ be constructed withn+1 instances. If the last clause applied was (3)-(5), then the Lemmaholds since θ itself begins with a leftparenthesis and ends with the matching right parenthesis. If the last clauseapplied was (2), then θ is ¬ψ, and the induction hypothesis applies to ψ. Similarly, if the last clause applied was (6) or (7), then θ consists of a quantifier, a variable, and a formula to which we canapply the induction hypothesis. It follows that the Lemma holds for θ. Lemma 4. Each formula contains at least one atomicformula. The proof proceeds by induction on the number of instances of (2)-(7)used to construct the formula, and we leave it as an exercise. Theorem 5. Let α, β be nonempty sequences of characterson our alphabet, such that αβ (i.e α followed by β) is a formula. Then α is not a formula. Proof: By Theorem 1 and Lemma 3, if α contains a left parenthesis, then the right parenthesis that matches theleftmost left parenthesis in α β comes at the end of α β, and so the matching right parenthesis is in β. So, α has more left parenthesesthan right parentheses. By Theorem 1, α is not a formula. So now suppose that α does not contain any left parentheses. By Lemma 2, α β consists of a string of zero or more unary markers followed byeither an atomic formula or a formula produced using a binaryconnective, via one of clauses (3)-(5). If the latter formula wasproduced via one of clauses (3)-(5), then it begins with a leftparenthesis. Since α does not contain any parentheses, it must be a string of unarymarkers. But then α does not contain any atomic formulas, and so by Lemma 4, α is not a formula. The only case left is where αβ consists of a string of unary markers followed by an atomicformula, either in the formt1=t2 orPt1 … tn. Again, if α just consisted of unary markers, it would not be a formula, and so α must consist of the unary markers that start α β, followed by either t1 by itself,t1= by itself, or the predicate letter P, and perhaps some (but notall) of the terms t1, … , tn. In the first two cases, α does not contain an atomic formula, by the policy that the categories do notoverlap. Since P is an n-place predicate letter, by thepolicy that the predicate letters are distinct, P is not anm-place predicate letter for any m ≠ n. So the part of α that consists of P followed by the terms is not an atomic formula. In all ofthese cases, then, α does notcontain an atomic formula. By Lemma 4, α is not a formula.We are finally in position to show that there is no amphiboly in ourlanguage. Theorem 6. Let θ be any formula of 1K=. If θ is not atomic, then there isone and only one among (2)-(7) that was the last clause applied to construct θ. That is, θ could not be produced by two different clauses. Moreover, no formula produced by clauses (3)-(7) isatomic. Proof: By Clause (8), either θ is atomic or itwas produced by one of clauses (2)-(7). Thus, the first symbol inθ must be either a predicate letter, a term, a unary marker, ora left parenthesis. If the first symbol in θ is a predicateletter or term, then θ is atomic. In this case, θ was notproduced by any of (2)-(7), since all such formulas begin withsomething other than a predicate letter or term. If the first symbolin θ is a negation sign "¬", then was θ produced byclause (2), and not by any other clause (since the other clausesproduce formulas that begin with either a quantifier or a leftparenthesis). Similarly, if θ begins with a universalquantifier, then it was produced by clause (6), and not by any otherclause, and if θ begins with an existential quantifier, then itwas produced by clause (7), and not by any other clause. The only caseleft is where θ begins with a left parenthesis. In this case, itmust have been produced by one of (3)-(5), and not by any otherclause. We only need to rule out the possibility that θ wasproduced by more than one of (3)-(5). To take an example, suppose thatθ was produced by (3) and (4). Then θ is(ψ1 & ψ2) and θ is also(ψ3 ∨ ψ4), where ψ1, ψ2,ψ3, and ψ4 are themselves formulas. Thatis, (ψ1 & ψ2) is the very sameformula as (ψ3 ∨ ψ4). By Theorem 5, ψ1 cannot be a proper part ofψ3, nor can ψ3 be a proper part of ψ1. So ψ1 must be the same formula asψ3.But then "&" must be the same symbol as "∨", and this contradicts the policy that all of the symbols aredifferent. So θ was not produced by both Clause (3) and Clause(4). Similar reasoning takes care of the other combinations. This result is sometimes called "unique readability". It shows thateach formula is produced from the atomic formulas via the variousclauses in exactly one way. If θ was produced by clause (2), then its main connective is the initial "¬". If θ was produced by clauses (3), (4), or (5), then its main connective is the introduced "&", "∨", or "→", respectively. If θ wasproduced by clauses (6) or (7), then its main connective is the initialquantifier. I apologize for the tedious details. I included them to indicate thelevel of precision and rigor for the syntax.3. DeductionWe now introduce a deductive system, D, for ourlanguages. As above, we define an argument to be a non-emptycollection of formulas in the formal language, one of which isdesignated to be the conclusion. If there are any otherformulas in the argument, they are its premises. Byconvention, we use "Γ", "Γ′", "Γ1", etc, torange over sets of formulas, and we use the letters "φ", "ψ", "θ", uppercase or lowercase, withor without subscripts, to range over single formulas. We write "Γ, Γ′" for the union of Γ and Γ′, and "Γ, φ" for the union of Γ with {φ}. We write an argument in the form <Γ, φ>, where Γ is the set of premises and φ is the conclusion. Rememberthat Γ may be empty. We write Γ  φ to indicate that φ is deducible from Γ, or, in other words, thatthe argument <Γ, φ> is deducible in D. We may write Γ D φ to emphasize the deductive system D. We write φ or D φ to indicate that φ can be deduced (in D) from the empty set of premises. The rules in D are chosen to match logical relationsconcerning the English analogues of the logical terminology in thelanguage. Again, we define the deducibility relation by recursion. Westart with a rule of assumptions: (As) If φ is a member of Γ, then Γ φ. We thus have that {φ} φ; each premise follows fromitself. We next present two clauses for each connective andquantifier. The clauses indicate how to "introduce" and "eliminate"formulas in which each symbol is the main connective. First, recall that "&" is an analogue of the English connective"and". Intuitively, one can deduce a formula in the form (θ & ψ) if one has deduced θ and one has deduced ψ. Conversely, one can deduce θ from (θ & ψ) and one can deduce ψ from (θ & ψ): (&I) If Γ1 θ and Γ2 ψ, then Γ1, Γ2 (θ & ψ). (&E) If Γ (θ & ψ) then Γ θ; and if Γ (θ & ψ) then Γ ψ.The name "&I" stands for "&-introduction"; "&E" stands for"&-elimination". Since, the symbol "∨" corresponds to the English "or", (θ ∨ ψ) should be deducible from θ, and (θ ∨ ψ) should also be deducible from ψ: (∨I) If Γ θ then Γ (θ ∨ ψ); if Γ ψ then Γ (θ ∨ ψ). The elimination rule is a bit more complicated. Suppose that "θ or ψ" is true. Suppose also that φ follows from θ and that φ follows from ψ. One can reason that if θ is true, then φis true. If instead ψ is true, we still have that φ is true. So either way, φ must be true. (∨E) If Γ1 (θ ∨ ψ), Γ2, θ φ and Γ3, ψ φ, then Γ1, Γ2, Γ3 φ. For the next clauses, recall that the symbol "→" is an analogue of the English "if … then … " construction. If one knows, or assumes (θ → ψ) and also knows, or assumes θ, then one can conclude ψ. Conversely, if one deduces ψ from an assumption θ, then one can conclude that (θ → ψ ). (→I) If Γ, θ ψ, then Γ (θ → ψ). (→E) If Γ1 (θ → ψ) and Γ2 θ , then Γ1, Γ2 ψ. Our next clauses are for the negation sign, "¬". The underlyingidea is that a formula ψ is inconsistent with itsnegation ¬ψ. They cannot both betrue. We call a pair of formulas ψ, ¬ψ contradictoryopposites. If one can deduce such a pair from an assumption θ, then one can conclude that θ is false, or, in other words,one can conclude ¬θ. (¬I) If Γ1, θ ψ and Γ2, θ ¬ψ, then Γ1, Γ2 ¬θ. There is some controversy over the other rule for the negation sign. By (As), we have that {A,¬A} A and{A,¬A} ¬A. So by¬I we have that {A} ¬¬A. However, we do not have the converse yet. Intuitively,¬¬θ corresponds to "it is notthe case that it is not the case that" . One might think that this last isequivalent to θ, and we have a rule to thateffect: (DNE) If Γ ¬¬θ, then Γ θ. The name DNE stands for "double-negation elimination". This inferenceis rejected by philosophers and mathematicians who do not hold that eachmeaningful sentence is either true or not true. Intuitionisticlogic does not sanction the inference in question (see, for exampleDummett [1977]), but, again, classical logic does. To illustrate the parts of the deductive system D presentedthus far, I show that (A ∨ ¬A): (i) {¬(A ∨ ¬A), A} ¬(A ∨ ¬A), by (As) (ii) {¬(A ∨ ¬A), A} A, by clause (As). (iii) {¬(A ∨ ¬A), A} (A ∨ ¬A), by (∨I), from (ii). (iv) {¬(A ∨ ¬A)} ¬A, by (¬I), from (i) and (iii). (v) {¬(A ∨ ¬A), ¬A} ¬(A ∨ ¬A), by (As) (vi) {¬(A ∨ ¬A), ¬A} ¬A, by (As) (vii) {¬(A ∨ ¬A), ¬A} (A ∨ ¬A), by(∨I), from (vi). (viii) {¬(A ∨ ¬A)} ¬¬A, by (¬I), from (v) and (vii). (ix) ¬¬(A ∨ ¬A), by (¬I), from (iv) and (viii). (x) (A ∨ ¬A), by (DNE), from (ix). The principle (θ ∨ ¬θ) is sometimes called thelaw of excluded middle. It is not valid in intuitionistic logic. Let θ, ¬θ be a pair of contradictory opposites, and let ψ be any formula at all. By (As) we have {θ, ¬θ, ¬ψ} θ and {θ, ¬θ, ¬ψ} ¬θ. So by (¬I), {θ, ¬θ} ¬¬ψ. So, by (DNE) wehave {θ, ¬θ} ψ . That is, anything at all follows from a pair of contradictory opposites. Some logicians introduce a ruleto codify a similar inference: If Γ1 θ and Γ2 ¬θ, then for any formula ψ, Γ1, Γ2 ψ The inference is sometimes called ex falso quodlibet. Somecall it "¬-elimination", but perhaps this stretches the notionof "elimination" a bit. We do not officially include ex falsoquodlibet as a separate rule in D, but as will be shownbelow (Theorem 10), each instance of it is derivable. Some logicians object to ex falso quodlibet, on the groundthat the formula ψ may be irrelevant toany of the premises in Γ. Suppose, for example, that one starts with some premises Γ about human nature andfacts about certain people, and then deduces both the sentence "Clintonhad extra-marital sexual relations" and "Clinton did not haveextra-marital sexual relations". One can surely conclude that there issomething wrong with premises Γ. But should we be allowedto then deduce anything at all from Γ? Should we be allowed to deduce "The economy is sound"? Deductive systems that demur from ex falso quodlibet are partof relevance logic. See Anderson and Belnap [1975],Anderson, Belnap, and Dunn [1992], and Tennant [1987]. Deepphilosophical issues concerning the nature of logical consequence areinvolved. Far be it for an article in a philosophy encyclopedia toavoid philosophical issues, but space considerations preclude afuller treatment of this issue here. Suffice it to note that theinference is sanctioned in systems of classical logic, thesubject of this article. It is essential to establishing the balancebetween the deductive system and the semantics (see §5 below). The next pieces of D are the clauses for the quantifiers. Let θ be a formula, v avariable, and t a term (i.e., a variable or a constant). Thendefine θ(v|t) to bethe result of substituting t for each free occurrence ofv in θ. So, if θ is (Qx & ∃xPxy), then θ(x|c) is(Qc & ∃xPxy). The lastoccurrence of x is not free (but recall that we avoid usingformulas like this). We have one other nicety to attend to. Suppose thatv1 and v2 are variables. It mayhappen that some of the substituted instances of v2are bound in θ(v1|v2). When this happens, we say that there is a clash of thevariables. Suppose, for example, that θ is ∃y(¬x =y), and so θ(x|y) is ∃y(¬y =y). We say that a term tis free for a variable v in θ if either t is aconstant or there is no clash of variables in θ(v|t). The idea is that nosubstituted instance of t should become a bound variable in θ(v|t). A formula in the form ∀v θ is an analogue of the English "for everyv, θ holds". So oneshould be able to infer θ(v|t) from ∀v θ: (∀E) If Γ ∀v θ, then Γ θ(v|t),provided that t is free for v in θ. The idea here is that if ∀v θ is true, then θ should hold of t, no matter what t is. We can illustrate the restriction on (∀E) as follows: The sentence ∀x ∃y(¬x=y) corresponds to an assertionthat for every object x, there is an object different fromx. This is a coherent, plausible assertion. It is true ifand only if the universe has at least two objects. It should followthat no matter what object t may be, something is differentfrom t. However, if we were allowed to substitute thevariable y for x, we would conclude ∃y(¬y=y), which saysthat there is something which is different from itself, a blatantfalsehood. The introduction clause for the universal quantifier is a bitmore complicated. Suppose that a formula θ has a variable v free, and that θ has been deduced from a set of premises Γ. If the variable v does not occurfree in any member of Γ, then θ will hold no matter which object v maydenote. That is, ∀v θ follows. (∀I) If Γ θ and the variable v does not occur freein any member of Γ, then Γ ∀vθ. This introduction rule corresponds to a common inference inmathematics. Suppose that a mathematician says "let n be anatural number" and goes on to show that n has a certainproperty P, without assuming anything about n(except that it is a natural number). She then reminds the readerthat n is "arbitrary", and concludes that P holdsfor all natural numbers. The condition that the variablev not occur in any premise is what guarantees that it isindeed "arbitrary". It could be any object, and so anything weconclude about it holds for all objects. The existential quantifier is an analogue of the English expression"there exists", or perhaps just "there is". If we have established(or assumed) that a given object t has a given property,then it follows that there is something that has thatproperty. Again, we have to be careful with the syntax, and avoidclashes of variables. (∃I) If Γ θ, then Γ ∃v θ′, where θ′ is obtained from θ by substituting the variablev for zero or more occurrences of a term t, providedthat (1) if t is a variable, then all of the replaced occurrencesof t are free in θ, and(2) all of the substituted occurrences of v are free in θ′. The provision (1) keeps us from replacing bound variables. Theprovision (2) comes up only if v is bound by another quantifierin θ. As noted above, we avoid suchformulas (since they appear to bind the same occurrence twice). The elimination rule for ∃ is not quite as simple: (∃E) If Γ1 ∃v θ and Γ2, θ φ, then Γ1, Γ2 φ, provided that vdoes not occur free in φ, nor in any member of Γ2. This elimination rule also corresponds to a common inference. Supposethat a mathematician asserts that there is a natural number with a givenproperty P. She then says "let n be such a naturalnumber, so that Pn", and goes on to establish a sentence φ, which does not mention the number n. If the derivation of φ does not invoke anything about n(other than the assumption that it has the given propertyP), then n could have been any number that has theproperty P. That is, n is an arbitrarynumber with property P. It does not matter which numbern is. Since φ does not mention n, it follows fromthe assertion that something has property P. The provisionsadded to (∃E) are to guarantee thatx is "arbitrary". As noted in the previous section, some authors introduce differentletters for bound variables and (what amounts to) free variables. Thismakes the syntax slightly more complex, but simplifies the provisions onsome of the rules of inference. Writers of logic books often facetradeoffs like this. The final items are the rules for the identity sign "=". Theintroduction rule is about a simple as can be: (=I) Γ t=t, where t is any term. This "inference" corresponds to the truism that everything isidentical to itself. The elimination rule corresponds to a principlethat if a is identical to b, then anything true ofa is also true of b, again paying attention toclashes of variables. (=E) If Γ1 t1=t2 and Γ2 θ, then Γ1, Γ2 θ′, where θ′ is obtained from θ by replacing zero or more occurrences of t1 witht2, provided that no bound variables are replaced, andif t2 is a variable, then all of its substitutedoccurrences are free. The rule (=E) indicates a certain restriction in the expressiveresources of our language. Suppose, for example, that Harry is identicalto Donald (since his mischievous parents gave him two names). It would notfollow from this and "Dick knows that Harry is wicked" that "Dick knowsthat Donald is wicked", for the reason that Dick might not know that Harryis identical to Donald. Contexts like this, in which identicals cannotsafely be substituted for each other, are called "opaque". We assume thatour language 1K= has no opaquecontexts. One final clause completes the description of the deductive systemD: (*) That's all folks. Γ θ only if θ follows from members of Γ by the above rules. Again, this clause allows proofs by induction on the rules used toestablish an inference. If a property of arguments holds of all instancesof (As) and (=I), and if the other rules preserve the property, then everyargument that is deducible in D enjoys the property inquestion. Before moving on to the model theory for 1K=, we pause tonote a few features of the deductive system. Lemma 7. Suppose that Γ D φ, and let v′ be avariable that does not occur free in φ or in any member of Γ. Assume that v′is free for v in φ and in every member of Γ. Let Γ′ be {θ(v|v′) | θ ∈ Γ}. That is, Γ′ is the result ofreplacing every free occurrence of a variable v with v′ in every member of Γ. Then Γ′ D φ(v|v′). Proof: The proof of this lemma is tedious, but wegive its essentials. We proceed by induction on the number of rules thatwere used to arrive at Γ φ. Suppose that n>0is a natural number, and that the lemma holds for any argument that wasderived using fewer than n rules, and suppose that Γ φ using exactly n rules. If n=1, then the rule appliedis either (As) or (=I). In this case, Γ′ φ(v|v′) by the same rule. If the last rule applied is (&I), then φ has the form (θ & ψ), and we have Γ1 θ and Γ2 ψ, with Γ = Γ1, Γ2. We apply theinduction hypothesis to the deductions of θ and ψ, and then apply (&I) tothe result. If the last rule applied was (&E), we have two sub-cases,but they are symmetric. We have Γ (φ & ψ). There are two slight complications here: the new variable v′ may occur free in ψ and it may not be free for v in ψ. In either case, first pick a new variable u that does not occur (free orbound) in (φ & ψ) or in any member of Γ. Now apply the induction hypothesis, substituting u for v′ in the deduction Γ (φ & ψ). Since v′ does notoccur free in φ or in any member of Γ, those formulas are left unchanged. The maneuver removes any freeoccurrences of v′ from thesubformula ψ. Now apply the inductionhypothesis to the result, substituting v′ for v,and then apply (&E). The remaining cases are similar. Theorem 8. The rule of Weakening. If Γ1 φ and Γ1 ⊆ Γ2, then Γ2 φ. Proof: Again, we proceed by induction on the number of rules that were used to arrive at Γ1 φ. Suppose that n>0 is a natural number, and that the theorem holds for any argument that was derived using fewer than n rules. Suppose that Γ1 φ using exactly n rules. If n=1, then the rule is either (As) or (=I). In these cases, Γ2 φ by the same rule. If the last rule applied was (&I), then φ has the form (θ&ψ), and we have Γ3 θand Γ4 ψ, with Γ1 = Γ3, Γ4. We apply the induction hypothesis to the deductions of θ and ψ, to get Γ2 θ and Γ2 ψ. and then apply (&I) to the result to get Γ2 φ. Most of the other cases are exactly like this. Slight complicationsarise only in the rules (∀I) and (∃E), because there we have to pay attention to theconditions for the rules. Starting with (∃E), we have Γ3 ∃vθ and Γ4, θ φ, with Γ1 being Γ3, Γ4, and v not free in φ, nor in any member of Γ4. We apply the induction hypothesis to get Γ2 ∃vθ, and then (∃E) to end up with Γ2 φ. Suppose that the last rule applied to get Γ1 φ is (∀I). So φ is a formula in the form ∀vθ, and we have Γ1 θ and the variable v does not occur free in any member of Γ1. The problem is that v may occur free in a member of Γ2, and so we cannot just invoke the induction hypothesis and apply (∀I) to the result. Let v′ be a variable that does not occur (free or bound) in θ or in any member of Γ2, and let Γ′ be the result of substituting v′ for every free occurrence of v in Γ2. Since v does not occur free in any member of Γ1, we still have Γ1⊆Γ. The induction hypothesis gives us Γ′ θ, and now we apply (∀I) to get Γ′ φ. We now apply Lemma 7, substituting v for the new variable v′. The result is Γ2 φ. Theorem 8 allows us to add on premises at will. It follows that Γ φ if and only if there is a subset Γ′⊆Γ such that Γ′ φ. By clause (*), all derivations are established in a finite number of steps. So we have Theorem 9. Γ φ if and only if there is a finite Γ′⊆Γ such that Γ′ φ. Theorem 10. The rule of ex falso quodlibet is a "derived rule" of D. That is, if Γ1 θ and Γ2 ¬θ,then Γ1,Γ2 ψ, for any formula ψ. Proof: Suppose that Γ1 θ and Γ2 ¬θ. Then by Theorem 8, Γ1,¬ψ θ, and Γ2,¬ψ θ. So by (¬I), Γ1, Γ2 ¬¬ψ. By (DNE), Γ1, Γ2 ψ. Theorem 11. The rule of Cut. If Γ1 ψ and Γ2, ψ θ, then Γ1, Γ2 θ. Proof: Suppose Γ1 ψ and Γ2, ψ θ. We proceed by induction on the number of rules used to establish Γ2, ψ θ.Suppose that n is a natural number, and that the theoremholds for any argument that was derived using fewer than nrules. Suppose that Γ2, ψ θ wasderived using exactly n rules. If the last rule used was(=I), then Γ1, Γ2 θ is also an instance of (=I). If Γ2, ψ θ is aninstance of (As), then either θ is ψ, or θ is a member of Γ2. In the former case, we have Γ1 θ by supposition, and get Γ1, Γ2 θ by Weakening (Theorem 8). In the latter case, Γ1, Γ2 θ is itself an instance of (As). Suppose that Γ2, ψ θ was obtained using (&E). Then we have Γ2, ψ (θ&φ). The induction hypothesis gives us Γ1, Γ2 (θ&φ), and (&E) produces Γ1, Γ2 θ.The remaining cases are similar. Theorem 11 allows us to chain together inferences. This fits thepractice of establishing theorems and lemmas and then using thosetheorems and lemmas later, at will. The cut principle is, I think,essential to reasoning. In some logical systems, the cut principle isa deep theorem. The system here was designed to make the proof ofTheorem 11 straightforward. If Γ D θ, then we say that the formula θis a deductive consequence of the set of formulas Γ, and that the argument <Γ,θ> is deductivelyvalid. A formula θ is a logicaltheorem, or a deductive logical truth, if D θ. That is, θ is a logical theorem if it is a deductive consequence of the empty set. A set Γ of formulas is consistent if there is no formula θ such that Γ D θ and Γ D ¬θ. That is, a set is consistent if itdoes not entail a pair of contradictory opposite formulas. Theorem 12. A set Γ is consistent if and only if there is a formula θ such that it is not the case that Γ θ. Proof: Suppose that Γ is consistent and let θ be any formula. Theneither it is not the case that Γ θ or it is not the case that Γ ¬θ. For the converse, suppose that Γ is inconsistent and let ψ be anyformula. We have that there is a formula such that both Γ θ and Γ ¬θ. By ex falso quodlibet (Theorem 10), Γ ψ. Define a set Γ of formulas of the language 1K= to be maximally consistent if Γ is consistent and for every formula θ of 1K=, if θ is not in Γ, then Γ, θ is inconsistent. In other words, Γis maximally consistent if Γ is consistent, and adding any formula in thelanguage not already in Γ renders it inconsistent. Notice that if Γ is maximally consistent then Γ θ if and only if θ is in Γ. Theorem 13. The Lindenbaum Lemma. LetΓ be any consistent set of formulas of 1K=. Then there is a set Γ′ of formulas of 1K= such that Γ⊆Γ′ and Γ′ ismaximally consistent. Proof: Although this theorem holds in general, we assume here that the set K of non-logical terminology is either finite or denumerably infinite (i.e., the size of the natural numbers, usually called  0). It follows that there is an enumeration θ0, θ1, … of the formulas of 1K=, such that every formula of 1K= eventually occurs in the list. Define a sequence of sets of formulas, by recursion, as follows: Γ0 is Γ; for each natural number n, if Γn, θn is consistent, then let Γn+1 = Γn, θn. Otherwise, let Γn+1 = Γn. Let Γ′ be the union of all of the sets Γn. Intuitively, the idea is to go through the formulas of 1K=, throwing each one into Γ′if doing so produces a consistent set. Notice that each Γn is consistent. Suppose that Γ′ is inconsistent. Thenthere is a formula θ such that Γ′ θ and Γ′ ¬θ. By Theorem 9 and Weakening (Theorem 8), there is finite subset Γ″ of Γ′ such that Γ″ θand Γ″ ¬θ. Because Γ″ is finite, there is a natural number n such that every member of Γ″ is in Γn. So, by Weakening again, Γn θ and Γn ¬θ. So Γn is inconsistent, which contradicts the construction. So Γ′ is consistent. Now suppose that a formula θ is not in Γ′. We have to show that Γ′, θ is inconsistent. The formula θ must occur in the aforementioned list of formulas; say that θ is θm. Since θm is not in Γ′, then it is not in Γm+1. This happens only if Γm, θm is inconsistent. So a pair of contradictory opposites can be deduced from Γm,θm. By Weakening, a pair of contradictory opposites can be deduced from Γ′, θm. So Γ′, θm is inconsistent. Thus, Γ′ is maximally consistent. Notice that this proof uses a principle corresponding to the law of excluded middle. In the construction of Γ′, we assumed that, at each stage, either Γn is consistent or it isnot. Intuitionists, who demur from excluded middle, do not accept theLindenbaum lemma (see Shapiro [1988]).4. SemanticsLet K be a set of non-logical terminology. Aninterpretation for the language 1K= is a structure M =<d,I>, where d is a non-empty set,called the domain-of-discourse, or simply thedomain, of the interpretation, and I is aninterpretation function. Informally, the domain is what weinterpret the language 1K= to beabout. It is what the variables range over. The interpretationfunction assigns appropriate extensions to the non-logical terms. Inparticular,If c is a constant in K, then I(c) is a member of the domain d. If P0 is a zero-place predicate letter in K, then I(P0) is a truth value, either truth or falsehood. If Q1 is a one-place predicate letter in K, then I(Q) is a subset of d. Intuitively, I(Q) is the set of members of the domain that the predicate Q holds of. If Q represents "red", then I(Q) is the set of red members of the domain. If R2 is a two-place predicate letter in K, then I(R) is a set of ordered pairs of members of d. Intuitively, I(R) is the set of pairs of members of the domain that the relation R holds between. If R represents "love", then I(R) is the set of pairs <a,b> such that a and bare the members of the domain for which a loves b. In general, if Sn is an n-place predicate letter in K, then I(S) is a set of ordered n-tuples of members of d. Define s to be a variable-assignment, or simply anassignment, on an interpretation M, if sis a function from the variables to the domain d ofM. The role of variable-assignments is to assign denotationsto the free variables of open formulas. (In a sense, thequantifiers determine the "meaning" of the bound variables.) Logicalsystems that dispense with free variables do not needvariable-assignments, but some other device is employed. We now define a relation of satisfaction betweeninterpretations, variable-assignments, and formulas of 1K=. If φ is a formula of 1K=, M is an interpretation for 1K=, and s is avariable-assignment on M, then we write M,s  φ for M satisfies φ under the assignment s. Theidea is that M,s φ is an analogue of "φ comes out true when interpreted as in M via s". Let t be a term of 1K=. We define the denotation of t in M unders, in terms of the interpretation function andvariable-assignment: If c is a constant, then DM,s(c) is I(c), and if v is a variable, then DM,s(v) is s(v). That is, the interpretation M assigns denotations to theconstants, while the variable-assignment assigns denotations to the(free) variables. If the language contained function symbols, thedenotation function would be defined by recursion. We now proceed by recursion on the complexity of the formulas of 1K=. If t1 and t2 are terms,then M,s t1=t2 if and only ifDM,s(t1)is the same asDM,s(t2). This is about as straightforward as it gets. An identityt1=t2 comes out true if andonly if the terms t1 and t2denote the same thing. If P0 is a zero-place predicateletter in K, then M,s P if and only if I(P) is truth. If Sn is an n-place predicate letter in K and t1, … , tn are terms, then M,s St1 … tn if and only if the n-tuple <DM,s(t1), … , DM,s(tn)> is in I(S).This takes care of the atomic formulas. We now proceed to thecompound formulas of the language, following the meanings of theEnglish counterparts of the logical terminology.M,s ¬θ if and only if it is not the case that M,s θ. M,s (θ&ψ) if and only if both M,s θ and M,s ψ. M,s (θ∨ψ) if and only if either M,s θ or M,s ψ. M,s (θ→ψ) if and only if either it is not the case that M,s θ, or M,s ψ. M,s ∀vθ if and only if M,s′ θ, for every assignment s′ that agrees with s except possibly at the variable v. The idea here is that ∀vθ comes out trueif and only if θ comes out true no matter what isassigned to the variable v. The final clause is similar. M,s ∃vθ if and only if M,s′ θ, for some assignment s′ that agrees with s except possibly at the variable v. So ∃vθ comes outtrue if there is an assignment to v that makes θ true. Theorem 6, unique readability, assures us that this definition iscoherent. At each stage in breaking down a formula, there is exactlyone clause to be applied, and so we never get contradictory verdictsconcerning satisfaction. As indicated, the role of variable-assignments is to givedenotations to the free variables. We now show thatvariable-assignments play no other role.Theorem 14. For any formula θ, if s1 and s2 agree on the free variables in θ, then M,s1 θ if and only if M,s2 θ. Proof: We proceed by induction on the complexityof the formula θ. The theorem clearly holds if θ is atomic, since in those cases only thevalues of the variable-assignments at the variables in θ figure in the definition. Assume, then, that thetheorem holds for all formulas less complex than θ. And suppose that s1 ands2 agree on the free variables of θ. Assume, first, that θ is anegation, ¬ψ. Then, by the induction hypothesis, M,s1 ψ if and only if M,s2 ψ. So, by the clause fornegation, M,s1 ¬ψ if and only if M,s2 ¬ψ. The cases where the main connective in θ is a binary connectives are also straightforward. Suppose that θ is ∃vψ, and that M,s1 ∃vψ. Then there is an assignment s1′ that agrees with s1 except possibly at v such that M,s1′ ψ. Let s2′ be the assignment thatagrees with s2 on the free variables not in and agrees with s1′ on the others. Then, by the induction hypothesis, M,s2′ ψ. Notice that s2′ agrees with s2 on every variable except possibly v. So M,s2 ∃vψ. The converse is the same, and the case where θ begins with a universal quantifier is similar. Recall that a sentence is a formula with no free variables. So by Theorem 14, if θ is a sentence, and s1, s2, are any two variable-assignments, then M,s1 θ if and only if M,s2 θ. So we can just write M θ if M,s θ forsome, or all, variable-assignments s. Suppose that K′⊆K are two sets of non-logical terms. If M = <d,I> is an interpretation of 1K=, then we define the restriction of M to 1K′ be the interpretation M′=<d,I′> such that I′ is the restriction ofI to K′. That is, Mand M′ have the same domain and agree onthe non-logical terminology in K′. Astraightforward induction establishes the following: Theorem 15. If M′ is the restriction of M to 1K′, then for every formula θ of 1K′, if s is any variable-assignment, M,s θ if and only if M′,s θ. Theorem 16. If two interpretations M1, M2 have the same domain and agree on the non-logical terminology of a formula θ, then if s is any variable-assignment, M1,s θ if and only if M2,s θ. In short, the satisfaction of a formula θ onlydepends on the domain of discourse, the interpretation of thenon-logical terminology in θ, and theassignments to the free variables in θ. We say that an argument <Γ,θ> is semantically valid, or just valid, written Γ θ, if for every interpretation M of the language and any variable-assignment s on M, if M,s ψ, for every member ψ of Γ, then M,s θ. If Γ θ, wealso say that θ is a logicalconsequence, or semantic consequence, ormodel-theoretic consequence of Γ. Thedefinition corresponds to the informal idea that an argument is validif it is not possible for its premises to all be true and itsconclusion false. Our definition of logical consequence alsosanctions the common thesis that a valid argument istruth-preserving--to the extent that satisfaction representstruth. Officially, an argument in 1K=is valid if its conclusion comes out true under every interpretationof the language in which the premises are true. Validity is themodel-theoretic counterpart to deducibility. A formula θ is logically true, or valid, if M,s θ, for every interpretation M and assignment s. Aformula is logically true if and only if it is a consequence of theempty set. If θ is logically true, then for any set Γ of formulas, Γ θ. Logical truth is the model-theoretic counterpart of theoremhood. A formula θ is satisfiable if there isan interpretation M and a variable-assignment s onM such that M,s θ. That is, θ is satisfiable ifthere is an interpretation and assignment that satisfies it. A set Γ of formulas is satisfiable if there is aninterpretation M and a variable-assignment s onM such that M,s θ, for every formula θ in Γ. If Γ is a set of sentences andif M θ for eachsentence θ in Γ, then we saythat M is a model of Γ. So aset of sentences is satisfiable if it has a model. Satisfiability isthe model-theoretic counterpart to consistency. Notice that Γ θ if and only if the set Γ,¬θ is not satisfiable. Itfollows that if a set Γ is not satisfiable, thenif θ is any formula, Γ θ.This is a model-theoretic counterpart to ex falso quodlibet (seeTheorem 10). We have the following, as an analogue to Theorem 12: Theorem 17. Let Γ be a set of formulas. The following are equivalent: (a) Γ is satisfiable; (b) there is no formula θ such that both Γ θ and Γ ¬θ; (c) there is some formula ψ such that it is not the case that Γ ψ. Proof: (a)⇒(b): Suppose that Γ is satisfiable and let θ be any formula. There is an interpretationM and assignment s such thatM,s ψ for every member ψ of Γ. By the clause for negations, we cannot haveboth M,s θ and M,s ¬θ. So either <Γ,θ> is not valid or else <Γ,¬θ> is not valid. (b)⇒(c): This is immediate. (c)⇒(a): Suppose that it is not the case that Γ ψ. Then there is an interpretation M and an assignment s such that M,s θ, for every formula θ in Γ and it is not the case that M,s ψ.A fortiori, M,s satisfies every member of Γ, and so Γ is satisfiable. 5. Meta-theoryWe now present some results that relate the deductive notions totheir model-theoretic counterparts. The first one is probably themost straightforward. We motivated both the various rules of thedeductive system D and the various clauses in the definitionof satisfaction in terms of the meaning of the English counterpartsto the logical terminology. So one would expect that an argument isdeducible, or deductively valid, only if it is semantically valid. Theorem 18. Soundness. For any formula θ and set Γ of formulas, if Γ D θ, then Γ θ. Proof: We proceed by induction on the number ofclauses used to establish Γ θ. So let n be a natural number, and assume that the theoremholds for any argument established as deductively valid with fewerthan n steps. And suppose that Γ θ was established using exactly n steps. If the last ruleapplied was (=I) then θ is a formula in the form t=t, and so θ is logically true. A fortiori, Γ θ. If the last rule applied was (As), then θ is a member of Γ, and so of course any interpretation andassignment that satisfies every member of Γ also satisfies θ. Suppose the last rule applied is (&I). So θ has the form (φ&ψ), and we have Γ1 φand Γ2 ψ, with Γ = Γ1, Γ2. The induction hypothesis gives us Γ1 φ and Γ2 ψ. Suppose that M,s satisfies every member of Γ. Then M,s satisfies every member of Γ1, and so M,s satisfies φ. Similarly, M,s satisfies every member of Γ2, and so M,s satisfies ψ. Thus, by the clause for "&" in thedefinition of satisfaction, M,s satisfies θ. So Γ θ. Suppose the last clause applied was (∃E). So we have Γ1 ∃vψ and Γ2, ψ θ, where Γ = Γ1, Γ2, and v does not occur free in ψ, nor in any member of Γ2. By the induction hypothesis, we have Γ1 ∃vψ and Γ2, ψ θ. Let M be an interpretation and s an assignmentsuch that M,s satisfies every member of Γ. Then M,s satisfies every memberof Γ1, and so M,s ∃vψ. So there is an assignment s′ that agrees with s on every variable except possibly v such that M,s′ ψ. We have that M,s satisfies every member of Γ2. Since v does not occur freein any member of Γ2, and s agrees with s′ on everything else, wehave that M,s′ satisfies everymember of Γ2, by Theorem 14. So M,s′ θ. Since v does not occur free in θ, and s agrees with s on everythingelse, we have that M,s θ, also by Theorem 14. So, in this case, Γ θ. Noticethe role of the restrictions on (∃E) here. Theother cases are about as straightforward. Corollary 19. Let Γ be a set of formulas. If Γ is satisfiable, then Γ is consistent. Proof: Suppose that Γ is satisfiable. So let M be an interpretation and san assignment such that M,s satisfies everymember of Γ. Assume that Γ is inconsistent. Then there is a formula θ such that Γ θ and Γ ¬θ. By soundness (Theorem 18), Γ θ and Γ ¬θ. So we have that M,s θ and M,s ¬θ. But this isimpossible, given the clause for negation in the definition ofsatisfaction. Even though the deductive system D and the model-theoreticsemantics were developed with the meanings of the logical terminologyin mind, one should not automatically expect the converse tosoundness (or Corollary 19) to hold. For all we know so far, we maynot have included enough rules of inference to deduce every validargument. The converses to soundness and Corollary 19 are among themost interesting results in contemporary mathematical logic. We beginwith the latter. Theorem 20. Completeness. Gödel [1930]. Let Γ be a set of formulas. If Γ is consistent, then Γ issatisfiable. Proof: The proof of completeness is rathercomplex. We only sketch it here. Let Γ be a consistent set of formulas of 1K=. Again, we assume for simplicity that the set K of non-logical terminology iseither finite or countably infinite (although the theorem holds evenif K is uncountable). The task at hand is to find aninterpretation M and a variable-assignment s onM, such that M,s satisfies every member of Γ. Consider the language obtained from 1K= by adding a denumerably infinitestock of new individual constants c0,c1, … We stipulate that the constants,c0, c1, … , are alldifferent from each other and none of them occur in K. Webuild an interpretation of the language from the language itself,using some of the constants as members of the domain ofdiscourse. Let θ0, θ1, … be an enumeration of theformulas of the expanded language, so that each formula occurs in thelist eventually. Let x be any variable, and define asequence Γ0, Γ1, … of sets of formulas (of theexpanded language) by recursion as follows: Γ0 = Γ; and Γn+1 = Γn,(∃xθn → θn(x|ci)), where ci is the first constant in the above listthat does not occur in θn or in any member of Γn. The underlying ideahere is that if ∃xθnis true, then ci is to be one such x. Let Γ be the union of the sets Γn. I sketch a proof that Γ′ is consistent. Suppose that Γ′ is inconsistent. ByTheorem 9, there is a finite subset of Γ that is inconsistent, and so one of the sets Γm is inconsistent. By hypothesis, Γ0 = Γ is consistent. Let n be the smallestnumber such that Γn is consistent, but Γn+1 = Γn,(∃xθn → θn(x|ci))is inconsistent. By (¬I), we have that(1) Γn ¬(∃xθn → θn(x|ci)). By ex falso quodlibet (Theorem 10), Γn, ¬∃xθn, ∃xθn θn(x|ci).So by (→I), Γn, ¬∃xθn (∃xθn → θn(x|ci)). From this and (1), we have Γn ¬¬∃xθn, by (¬I), and by (DNE) we have (2) Γn ∃xθn. By (As), Γn, θn(x|ci), ∃xθn θn(x|ci).So by (→I), Γn, θn(x|ci) (∃xθn → θn(x|ci)).From this and (1), we have Γn ¬θn(x|ci), by (¬I). Let v be a variable that does not occur(free or bound) in θn or inany member of Γn. By uniformsubstitution of v for ci, we can turnthe derivation of Γn ¬θn(x|ci)into Γn ¬θn(x|v). By (∀I), we have (3) Γn ∀v¬θn(x|v). By (As) we have {∀v¬θn(x|v),θn} θn and by (∀E) we have {∀v¬θn(x|v), θn} ¬θn. So {∀v¬θn(x|v), θn} is inconsistent. Let φ be any sentence of the language (so that φ has no free variables). By ex falso quodlibet(Theorem 10), we have that {∀v¬θn(x|v),θn} φ and {∀v¬θn(x|v), θn} ¬φ. So with (2), we have that Γn, ∀v¬θn(x|v) φ and Γn, ∀v¬θn(x|v) ¬φ, by (∃E). By Cut (Theorem 11), Γn φ and Γn ¬φ. So Γn is inconsistent, contradicting the assumption. So Γ′ is consistent. Applying the Lindenbaum Lemma (Theorem 13), let Γ″ be a maximally consistentset of sentences (of the expanded language) that contains Γ′. So, of course, Γ″ contains Γ. We define an interpretation M, and avariable-assignment s on M, such thatM,s satisfies every member of Γ″. If we did not have a sign for identity in the language, we would letthe domain of M be the collection of new constants{c0, c1, … }. But as itis, there may be a sentence in the formci=cj, with i≠j, in Γ″. If so, we cannot haveboth ci andcj in the domain of theinterpretation. So we define the domain d of M tobe the set {ci | there is noj<i such thatci=cj is in Γ″}. In other words, aconstant ci is in the domain ofM if Γ″ does not declare it to be identical to an earlier constant in thelist. Notice that for each new constantci, there is exactly one j≤i such thatcj is in d and the sentenceci=cj is in Γ″. We now define the interpretation function I. Leta be any constant in the expanded language. By (=I) and(∃I), Γ″ ∃x x=a, and so ∃x x=a ∈ Γ″. By the construction of Γ′, there is a sentence in the form (∃x x=a → ci=a) in Γ″. We havethat ci=a is in Γ″. As above, there is exactly onecj in d such thatci=cj is in Γ″. LetI(a)=cj. Notice thatif ci is a constant in the domaind, thenI(ci)=ci.That is each ci in d denotesitself. Let P be a one-place predicate letter in K. LetI(P) be the set of constants{ci | ci isin d and the formula Pc is in Γ″}. Let R be abinary predicate letter in K. Let I(R) bethe set of pairs of constants{<ci,cj>| ci is in d,cj is in d, and the formulaRcicj is inΓ″}. Three-placepredicates, etc. are interpreted similarly. In effect, Iinterprets the non-logical terminology as they are in Γ″. The variable-assignment is similar. If v is a variable,then s(v)=ci, whereci is the first constant in d suchthat ci=v is in Γ″. The final item in this proof is a tedious lemma that for everyformula θ in the expanded language, M,s θ if and only if θ is in Γ″. This proceeds byinduction on the complexity of θ. The case where θ is atomic follows from the definitions ofM (i.e., the domain d and the interpretationfunction I) and the variable-assignment s. Theother cases follow from the various clauses in the definition ofsatisfaction. Since Γ⊆Γ″, we have that M,s satisfies every member of Γ. By Theorem 15, the restriction of M to theoriginal language 1K= and salso satisfies every member of Γ. Thus Γ is satisfiable. A converse to Soundness (Theorem 18) is a straightforwardcorollary: Theorem 21. For any formula θ and set Γ of formulas, if Γ θ, then Γ D θ. Proof: Suppose that Γ θ. Then there is no interpretation M and assignment ssuch that M,s satisfies every member of Γ but does not satisfy θ. So the set Γ,¬θ is notsatisfiable. By Completeness (Theorem 20), Γ,¬θ is inconsistent. Sothere is a formula φ such that Γ,¬θ φ and Γ,¬θ ¬φ. By (¬I), Γ ¬¬θ, and by (DNE) Γ θ.Our next item is a corollary of Theorem 9, Soundness (Theorem 18),and Completeness: Corollary 22. Compactness. A set Γ of formulas is satisfiable if and only if everyfinite subset of Γ is satisfiable. Proof: If M,s satisfies everymember of Γ, then M,ssatisfies every member of each finite subset of Γ. For the converse, suppose that Γ is notsatisfiable. Then we show that some finite subset of Γ is not satisfiable. By Completeness (Theorem 20), Γ is inconsistent. By Theorem 9 (andWeakening), there is a finite subset Γ′⊆Γ such that Γ′ is inconsistent.By Corollary 19, Γ′ isnot satisfiable. Soundness and completeness together entail that an argument isdeducible if and only if it is valid, and a set of formulas isconsistent if and only if it is satisfiable. So we can go back andforth between model-theoretic and proof-theoretic notions,transferring properties of one to the other. Compactness holds in themodel theory because all derivations use only a finite number ofpremises. Recall that in the proof of Completeness (Theorem 20), we made thesimplifying assumption that the set K of non-logicalconstants is either finite or denumerably infinite. Theinterpretation we produced was itself either finite or denumerablyinfinite. Thus, we have the following: Corollary 23. Löwenheim-Skolem Theorem. Let Γ be a satisfiable set of sentences of thelanguage 1K=. If Γ is either finite ordenumerably | |
