Typically, alogic consists of a formal or informal languagetogether with a deductive system and/or a model-theoretic semantics.The language has components that correspond to a part of a naturallanguage like English or Greek. The deductive system is to capture,codify, or simply recordarguments that arevalidfor the given language, and the semantics is to capture, codify, orrecord the meanings, or truth-conditions for at least part of thelanguage.

The following sections provide the basics of a typical logic,sometimes called “classical elementary logic” or“classical first-order logic”. Section 2 develops a formallanguage, with a rigorous syntax and grammar. The formal language is arecursively defined collection of strings on a fixed alphabet. Assuch, it has no meaning, or perhaps better, the meaning of itsformulas is given by the deductive system and the semantics. Some ofthe symbols have counterparts in ordinary language. We define anargument to be a non-empty collection of sentences in theformal language, one of which is designated to be the conclusion. Theother sentences (if any) in an argument are its premises. Section 3sets up a deductive system for the language, in the spirit of naturaldeduction. An argument isderivable if there is a deductionfrom some or all of its premises to its conclusion. Section 4 providesa model-theoretic semantics. An argument isvalid if there isno interpretation (in the semantics) in which its premises are alltrue and its conclusion false. This reflects the longstanding viewthat a valid 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, calledsoundness,entails that no deduction takes one from true premises to a falseconclusion. Thus, deductions preserve truth. Then we establish aconverse, calledcompleteness, that an argument is valid onlyif it is derivable. This shows that the deductive system is richenough to provide a deduction for every valid argument. So there areenough deductions: all and only valid arguments are derivable. Webriefly indicate other features of the logic, some of which arecorollaries to soundness and completeness.

The final section, Section 6, is devoted to the a brief examination ofthe philosophical position that classical logic is “the oneright logic”.

• 1. Introduction
• 2. Language
  • 2.1 Building blocks
  • 2.2 Atomic formulas
  • 2.3 Compound formulas
  • 2.4 Features of the syntax
• 3. Deduction
• 4. Semantics
• 5. Meta-theory
• 6. The One Right Logic?
  • 6.1 Rivals to classical, first-order logic
  • 6.2 Sublogics of classical, first-order logic
• Bibliography
  • Further Reading
• Academic Tools
• Other Internet Resources
• Related Entries

1. Introduction

Today, logic is a branch of mathematics and a branch of philosophy. Inmost large universities, both departments offer courses in logic, andthere is usually a lot of overlap between them. Formal languages,deductive systems, and model-theoretic semantics are mathematicalobjects and, as such, the logician is interested in their mathematicalproperties and relations. Soundness, completeness, and most of theother results reported below are typical examples. Philosophically,logic is at least closely related to the study ofcorrectreasoning. Reasoning is an epistemic, mental activity. So logicis at least closely allied with epistemology. Logic is also a centralbranch of computer science, due, in part, to interesting computationalrelations in logical systems, and, in part, to the close connectionbetween formal deductive argumentation and reasoning (see the entriesonrecursive functions,computability and complexity, andphilosophy of computer science).

This raises questions concerning the philosophical relevance of thevarious mathematical aspects of logic. How do deducibility andvalidity, as properties of formal languages – sets of strings ona fixed alphabet – relate to correct reasoning? What do themathematical results reported below have to do with the originalphilosophical issues concerning valid reasoning? This is an instanceof the philosophical problem of explaining how mathematics applies tonon-mathematical reality.

Typically, ordinary deductive reasoning takes place in a naturallanguage, or perhaps a natural language augmented with somemathematical symbols. So our question begins with the relationshipbetween a natural language and a formal language. Without attemptingto be comprehensive, it may help to sketch several options on thismatter.

One view is that the formal languages accurately exhibit actualfeatures of certain fragments of a natural language. Some philosophersclaim that declarative sentences of natural language have underlyinglogical forms and that these forms are displayed by formulasof a formal language. Other writers hold that (successful) declarativesentences expresspropositions; and formulas of formallanguages somehow display the forms of these propositions. On viewslike this, the components of a logic provide the underlying deepstructure of correct reasoning. A chunk of reasoning in naturallanguage is correct if the forms underlying the sentences constitute avalid or deducible argument. See for example, Montague [1974],Davidson [1984], Lycan [1984] (and the entry onlogical form).

Another view, held at least in part by Gottlob Frege and WilhelmLeibniz, is that because natural languages are fraught with vaguenessand ambiguity, they should bereplaced by formal languages. Asimilar view, held by W. V. O. Quine (e.g., [1960], [1986]), is that anatural language should beregimented, cleaned up for seriousscientific and metaphysical work. One desideratum of the enterprise isthat the logical structures in the regimented language should betransparent. It should be easy to “read off” the logicalproperties of each sentence. A regimented language is similar to aformal language regarding, for example, the explicitly presented rigorof its 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, orcan be regimented by, a valid or deducible argument in a formallanguage.

When mathematicians and many philosophers engage in deductivereasoning, they occasionally invoke formulas in a formal language tohelp disambiguate, or otherwise clarify what they mean. In otherwords, sometimes formulas in a formal language areused inordinary reasoning. This suggests that one might think of a formallanguage as anaddendum to a natural language. Then ourpresent question concerns the relationship between this addendum andthe original language. What do deducibility and validity, as sharplydefined on the addendum, tell us about correct deductive reasoning ingeneral?

Another view is that a formal language is amathematicalmodel of a natural language in roughly the same sense as, say, acollection of point masses is a model of a system of physical objects,and the Bohr construction is a model of an atom. In other words, aformal language displays certain features of natural languages, oridealizations thereof, while ignoring or simplifying other features.The purpose of mathematical models is to shed light on what they aremodels of, without claiming that the model is accurate in all respectsor that the model should replace what it is a model of. On a view likethis, deducibility and validity represent mathematical models of(perhaps different aspects of) correct reasoning in natural languages.Correct chunks of deductive reasoning correspond, more or less, tovalid or deducible arguments; incorrect chunks of reasoning roughlycorrespond to invalid or non-deducible arguments. See, for example,Corcoran [1973], Shapiro [1998], and Cook [2002].

There is no need to adjudicate this matter here. Perhaps the truthlies in a combination of the above options, or maybe some other optionis the correct, or most illuminating one. We raise the matter only tolend some philosophical perspective to the formal treatment thatfollows.

2. Language

Here 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 the formallanguages correspond to, or have counterparts in, natural languageslike English. Technically, this “counterpart relation” isnot part of the formal development, but we will mention it from timeto time, to motivate some of the features and results.

2.1 Building blocks

We begin with analogues ofsingular terms, linguistic itemswhose function is to denote a person or object. We call theseterms. We assume a stock ofindividual constants.These are lower-case letters, near the beginning of the Romanalphabet, with or without numerical subscripts:

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 could be avoided by taking a constant like \(d_{22}\),for example, to consist of three characters, a lowercase“\(d\)” followed by a pair of subscript“2”s.

We also assume a stock ofindividual variables. These arelower-case letters, near the end of the alphabet, with or withoutnumerical subscripts:

In ordinary mathematical reasoning, there are two functions terms needto fulfill. We need to be able to denote specific, but unspecified (orarbitrary) objects, and sometimes we need to express generality. Inour system, we use some constants in the role of unspecified referenceand variables to express generality. Both uses are recapitulated inthe formal treatment below. Some logicians employ different symbolsfor unspecified objects (sometimes called “individualparameters”) and variables used to express generality.

Constants and variables are the only terms in our formal language, soall of our terms are simple, corresponding to proper names and someuses of pronouns. We call a term closed if it is not a variable. Ingeneral, we use \(v\) to represent variables, and \(t\) to represent aclosed term, an individual constant. Some authors also introducefunction letters, which allow complex terms corresponding to:“\(7+4\)” and “the wife of Bill Clinton”, orcomplex terms containing variables, like “the father of\(x\)” and “\(x/y\)”. Logic books aimed atmathematicians are likely to contain function letters, probably due tothe centrality of functions in mathematical discourse. Books aimed ata more general audience (or at philosophy students), may leave outfunction letters, since it simplifies the syntax and theory. We followthe latter route here. This is an instance of a general tradeoffbetween presenting a system with greater expressive resources, at thecost of making its formal treatment more complex.

For each natural number \(n\), we introduce a stock of \(n\)-placepredicate letters. These are upper-case letters at thebeginning or middle of the alphabet. A superscript indicates thenumber of places, and there may or may not be a subscript. Forexample,

are three-place predicate letters. We often omit the superscript, whenno confusion will result. We also add a special two-place predicatesymbol “\(=\)” for identity.

Zero-place predicate letters are sometimes called “sentenceletters”. They correspond to free-standing sentences whoseinternal structure does not matter. One-place predicate letters,called “monadic predicate letters”, correspond tolinguistic items denoting properties, like “being a man”,“being red”, or “being a prime number”.Two-place predicate letters, called “binary predicateletters”, correspond to linguistic items denoting binaryrelations, like “is a parent of” or “is greaterthan”. Three-place predicate letters correspond to three-placerelations, like “lies on a straight line between”. And soon.

Thenon-logical terminology of the language consists of itsindividual constants and predicate letters. The symbol“\(=\)”, for identity, is not a non-logical symbol. Intaking identity to be logical, we provide explicit treatment for it inthe deductive system and in the model-theoretic semantics. Mostauthors do the same, but there is some controversy over the issue(Quine [1986, Chapter 5]). If \(K\) is a set of constants andpredicate letters, then we give the fundamentals of a language\(\LKe\) built on this set of non-logical terminology. It may becalled thefirst-order language with identity on \(K\). Asimilar language that lacks the symbol for identity (or which takesidentity to be non-logical) may be called \(\mathcal{L}1K\), thefirst-order language without identity on \(K\).

2.2 Atomic formulas

If \(V\) is an \(n\)-place predicate letter in \(K\), and \(t_1,\ldots,t_n\) are terms of \(K\), then \(Vt_1 \ldots t_n\) is anatomic formula of \(\LKe\). Notice that the terms \(t_1,\ldots,t_n\) need not be distinct. Examples of atomic formulasinclude:

The last one is an analogue of a statement that a certain relation\((A)\) holds between three objects \((a, b, c)\). If \(t_1\) and\(t_2\) are terms, then \(t_1 =t_2\) is also an atomic formula of\(\LKe\). It corresponds to an assertion that \(t_1\) is identical to\(t_2\).

If an atomic formula has no variables, then it is called anatomicsentence. If it does have variables, it is calledopen.In the above list of examples, the first and second are open; the restare sentences.

2.3 Compound formulas

We now introduce the final items of the lexicon:

We give a recursive definition of aformula of \(\LKe\):

1. All atomic formulas of \(\LKe\) are formulas of \(\LKe\).
2. If \(\theta\) is a formula of \(\LKe\), then so is \(\neg\theta\).

A formula corresponding to \(\neg \theta\) thus says that it is notthe case that \(\theta\). The symbol “\(\neg\)” is called“negation”, and is a unary connective.

3. If \(\theta\) and \(\psi\) are formulas of \(\LKe\), then so is\((\theta \amp \psi)\).

The ampersand “\(\amp\)” corresponds to the English“and” (when “and” is used to connectsentences). So \((\theta \amp \psi)\) can be read “\(\theta\)and \(\psi\)”. The formula \((\theta \amp \psi)\) is called the“conjunction” of \(\theta\) and \(\psi\).

4. If \(\theta\) and \(\psi\) are formulas of \(\LKe\), then so is\((\theta \vee \psi)\).

The symbol “\(\vee\)” corresponds to “either… or … or both”, so \((\theta \vee \psi)\) can beread “\(\theta\) or \(\psi\)”. The formula \((\theta \vee\psi)\) is called the “disjunction” of \(\theta\) and\(\psi\).

5. If \(\theta\) and \(\psi\) are formulas of \(\LKe\), then so is\((\theta \rightarrow \psi)\).

The arrow “\(\rightarrow\)” roughly corresponds to“if … then … ”, so \((\theta \rightarrow\psi)\) can be read “if \(\theta\) then \(\psi\)” or“\(\theta\) only if \(\psi\)”.

The symbols “\(\amp\)”, “\(\vee\)”, and“\(\rightarrow\)” are called “binaryconnectives”, since they serve to “connect” twoformulas into one. Some authors introduce \((\theta \leftrightarrow\psi)\) as an abbreviation of \(((\theta \rightarrow \psi) \amp(\psi\rightarrow \theta))\). The symbol “\(\leftrightarrow\)”is an analogue of the locution “if and only if”.

6. If \(\theta\) is a formula of \(\LKe\) and \(v\) is a variable,then \(\forall v \theta\) is a formula of \(\LKe\).

The symbol “\(\forall\)” is called auniversalquantifier, and is an analogue of “for all”; so\(\forall v\theta\) can be read “for all \(v,\theta\)”.

7. If \(\theta\) is a formula of \(\LKe\) and \(v\) is a variable,then \(\exists v \theta\) is a formula of \(\LKe\).

The symbol “\(\exists\)” is called anexistentialquantifier, and is an analogue of “there exists” or“there is”; so \(\exists v \theta\) can be read“there is a \(v\) such that \(\theta\)”.

8. That’s all folks. That is, all formulas are constructed inaccordance with rules (1)–(7).

Clause (8) allows us to do inductions on the complexity of formulas.If a certain property holds of the atomic formulas and is closed underthe operations presented in clauses (2)–(7), then the propertyholds of all formulas. Here is a simple example:

We next define the notion of an occurrence of a variable beingfree orbound in a formula. A variable thatimmediately follows a quantifier (as in “\(\forall x\)”and “\(\exists y\)”) is neither free nor bound. We do noteven think of those as occurrences of the variable. All variables thatoccur in an atomic formula are free. If a variable occurs free (orbound) in \(\theta\) or in \(\psi\), then that same occurrence is free(or bound) in \(\neg \theta, (\theta \amp \psi), (\theta \vee \psi)\),and \((\theta \rightarrow \psi)\). That is, the (unary and binary)connectives do not change the status of variables that occur in them.All occurrences of the variable \(v\) in \(\theta\) are bound in\(\forall v \theta\) and \(\exists v \theta\). Anyfreeoccurrences of \(v\) in \(\theta\) are bound by the initialquantifier. All other variables that occur in \(\theta\) are free orbound in \(\forall v \theta\) and \(\exists v \theta\), as they are in\(\theta\).

For example, in the formula \((\forall\)x(Axy \(\vee Bx) \ampBx)\), the occurrences of “\(x\)” inAxy and inthe first \(Bx\) are bound by the quantifier. The occurrence of“\(y\)” and last occurrence of “\(x\)” arefree. In \(\forall x(Ax \rightarrow \exists\)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“double-binding”. Although it does not create anyambiguities (see below), we will avoid such formulas, as a matter oftaste and clarity.

The syntax also allows so-called vacuous binding, as in\(\forall\)x\(Bc\). These, too, will be avoided in what follows. Sometreatments of logic rule out vacuous binding and double binding as amatter of syntax. That simplifies some of the treatments below, andcomplicates others.

Free variables correspond to place-holders, while bound variables areused to express generality. If a formula has no free variables, thenit is called asentence. If a formula has free variables, itis calledopen.

2.4 Features of the syntax

Before turning to the deductive system and semantics, we mention a fewfeatures of the language, as developed so far. This helps draw thecontrast between formal languages and natural languages likeEnglish.

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 a one-placepredicate.

One difference between natural languages like English and formallanguages like \(\LKe\) is that the latter are not supposed to haveany ambiguities. The policy that the different categories of symbolsdo not overlap, and that no symbol does double-duty, avoids the kindof ambiguity, sometimes called “equivocation”, that occurswhen a single word has two meanings: “I’ll meet you at thebank.” But there are other kinds of ambiguity. Consider theEnglish 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 theparentheses in it, it would have amphibolies. For example, there wouldbe a “formula” \(A \amp B \vee\) C. Is thissupposed to be \(((A \amp B) \vee C)\), or is it \((A \amp(B \veeC))\)? The parentheses resolve 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 \(\LKe\) can be puttogether in only one way? Our next task is to answer thisquestion.

Let us temporarily use the term “unary marker” for thenegation symbol \((\neg)\) or a quantifier followed by a variable(e.g., \(\forall x, \exists z)\).

The proof proceeds by induction on the number of instances of(2)–(7) used to construct the formula, and we leave it as anexercise.

We are finally in position to show that there is no amphiboly in ourlanguage.

This result is sometimes called “unique readability”. Itshows that each formula is produced from the atomic formulas via thevarious clauses in exactly one way. If \(\theta\) was produced byclause (2), then itsmain connective is the initial“\(\neg\)”. If \(\theta\) was produced by clauses (3),(4), or (5), then itsmain connective is the introduced“\(\amp\)”, “\(\vee\)”, or“\(\rightarrow\)”, respectively. If \(\theta\) wasproduced by clauses (6) or (7), then itsmain connective isthe initial quantifier. We apologize for the tedious details. Weincluded them to indicate the level of precision and rigor for thesyntax.

3. Deduction

We now introduce adeductive system, \(D\), for ourlanguages. As above, we define anargument to be a non-emptycollection of sentences in the formal language, one of which isdesignated to be theconclusion. If there are any othersentences in the argument, they are itspremises.^[1] By convention, we use “\(\Gamma\)”,“\(\Gamma'\)”, “\(\Gamma_1\)”, etc, to rangeover sets of sentences, and we use the letters “\(\phi\)”,“\(\psi\)”, “\(\theta\)”, uppercase orlowercase, with or without subscripts, to range over single sentences.We write “\(\Gamma, \Gamma'\)” for the union of \(\Gamma\)and \(\Gamma'\), and “\(\Gamma, \phi\)” for the union of\(\Gamma\) with \(\{\phi\}\).

We write an argument in the form \(\langle \Gamma, \phi \rangle\),where \(\Gamma\) is a set of sentences, the premises, and \(\phi\) isa single sentence, the conclusion. Remember that \(\Gamma\) may beempty. We write \(\Gamma \vdash \phi\) to indicate that \(\phi\) isdeducible from \(\Gamma\), or, in other words, that the argument\(\langle \Gamma, \phi \rangle\) is deducible in \(D\). We may write\(\Gamma \vdash_D \phi\) to emphasize the deductive system \(D\). Wewrite \(\vdash \phi\) or \(\vdash_D \phi\) to indicate that \(\phi\)can be deduced (in \(D)\) from the empty set of premises.

The rules in \(D\) are chosen to match logical relations concerningthe English analogues of the logical terminology in the language.Again, we define the deducibility relation by recursion. We start witha rule of assumptions:

(As)

If \(\phi\) is a member of \(\Gamma\), then \(\Gamma \vdash\phi\).

We thus have that \(\{\phi \}\vdash \phi\); each premise follows fromitself. We next present two clauses for each connective andquantifier. The clauses indicate how to “introduce” and“eliminate” sentences in which each symbol is the mainconnective.

First, recall that “\(\amp\)” is an analogue of theEnglish connective “and”. Intuitively, one can deduce asentence in the form \((\theta \amp \psi)\) if one has deduced\(\theta\) and one has deduced \(\psi\). Conversely, one can deduce\(\theta\) from \((\theta \amp \psi)\) and one can deduce \(\psi\)from \((\theta \amp \psi)\):

\((\amp \mathrm{I})\)

If \(\Gamma_1 \vdash \theta\) and \(\Gamma_2 \vdash \psi\), then\(\Gamma_1, \Gamma_2 \vdash(\theta \amp \psi)\).

\((\amp \mathrm{E})\)

If \(\Gamma \vdash(\theta \amp \psi)\) then \(\Gamma \vdash\theta\); and if \(\Gamma \vdash(\theta \amp \psi)\) then \(\Gamma\vdash \psi\).

The name “&I” stands for“&-introduction”; “&E” stands for“&-elimination”.

Since, the symbol “\(\vee\)” corresponds to the English“or”, \((\theta \vee \psi)\) should be deducible from\(\theta\), and \((\theta \vee \psi)\) should also be deducible from\(\psi\):

\((\vee \mathrm{I})\)

If \(\Gamma \vdash \theta\) then \(\Gamma \vdash(\theta \vee\psi)\); if \(\Gamma \vdash \psi\) then \(\Gamma \vdash(\theta \vee\psi)\).

The elimination rule is a bit more complicated. Suppose that“\(\theta\) or \(\psi\)” is true. Suppose also that\(\phi\) follows from \(\theta\) and that \(\phi\) follows from\(\psi\). One can reason that if \(\theta\) is true, then \(\phi\) istrue. If instead \(\psi\) is true, we still have that \(\phi\) istrue. So either way, \(\phi\) must be true.

\((\vee \mathrm{E})\)

If \(\Gamma_1 \vdash(\theta \vee \psi), \Gamma_2, \theta \vdash\phi\) and \(\Gamma_3, \psi \vdash \phi\), then \(\Gamma_1, \Gamma_2,\Gamma_3 \vdash \phi\).

For the next clauses, recall that the symbol,“\(\rightarrow\)”, is an analogue of the English “if… then … ” construction. If one knows, or assumes\((\theta \rightarrow \psi)\) and also knows, or assumes \(\theta\),then one can conclude \(\psi\). Conversely, if one deduces \(\psi\)from an assumption \(\theta\), then one can conclude that \((\theta\rightarrow \psi)\).

\(({\rightarrow}\mathrm{I})\)

If \(\Gamma, \theta \vdash \psi\), then \(\Gamma \vdash(\theta\rightarrow \psi)\).

\(({\rightarrow}\mathrm{E})\)

If \(\Gamma_1 \vdash(\theta \rightarrow \psi)\) and \(\Gamma_2\vdash \theta\), then \(\Gamma_1, \Gamma_2 \vdash \psi\).

This elimination rule is sometimes called “modus ponens”.In some logic texts, the introduction rule is proved as a“deduction theorem”.

Our next clauses are for the negation sign, “\(\neg\)”.The underlying idea is that a sentence \(\psi\) is inconsistent withits negation \(\neg \psi\). They cannot both be true. We call a pairof sentences \(\psi, \neg \psi\)contradictory opposites. Ifone can deduce such a pair from an assumption \(\theta\), then one canconclude that \(\theta\) is false, or, in other words, one canconclude \(\neg \theta\).

\((\neg \mathrm{I})\)

If \(\Gamma_1, \theta \vdash \psi\) and \(\Gamma_2, \theta \vdash\neg \psi\), then \(\Gamma_1, \Gamma_2 \vdash \neg \theta\).

By (As), we have that \(\{A,\neg A\}\vdash A\) and\(\{\)A,\(\neg\)A\(\}\vdash \neg A\). So by \(\neg\)I we havethat \(\{A\}\vdash \neg \neg A\). However, we do not have the converseyet. Intuitively, \(\neg \neg \theta\) corresponds to “it is notthe case that it is not the case that” . One might think thatthis last is equivalent to \(\theta\), and we have a rule to thateffect:

(DNE)

If \(\Gamma \vdash \neg \neg \theta\), then \(\Gamma \vdash\theta\).

The name DNE stands for “double-negation elimination”.There is some controversy over this inference. It is rejected byphilosophers and mathematicians who do not hold that each meaningfulsentence is either true or not true.Intuitionistic logicdoes not sanction the inference in question (see, for example Dummett[2000], or the entry onintuitionistic logic, orhistory of intuitionistic logic), but, again, classical logic does.

To illustrate the parts of the deductive system \(D\) presented thusfar, we show that \(\vdash(A \vee \neg A)\):

1. \(\{\neg(A \vee \neg A), A\}\vdash \neg(A \vee \neg A)\), by(As)
2. \(\{\neg(A \vee \neg A), A\}\vdash A\), by (As).
3. \(\{\neg(A \vee \neg A), A\}\vdash(A \vee \neg A)\), by\((\vee\)I), from (ii).
4. \(\{\neg(A \vee \neg A)\}\vdash \neg A\), by \((\neg\)I), from (i)and (iii).
5. \(\{\neg(A \vee \neg A), \neg A\}\vdash \neg(A \vee \neg A)\), by(As)
6. \(\{\neg(A \vee \neg A), \neg A\}\vdash \neg A\), by (As)
7. \(\{\neg(A \vee \neg A), \neg A\}\vdash(A \vee \neg A)\), by\((\vee\)I), from (vi).
8. \(\{\neg(A \vee \neg A)\}\vdash \neg \neg A\), by \((\neg\)I),from (v) and (vii).
9. \(\vdash \neg \neg(A \vee \neg A)\), by \((\neg\)I), from (iv) and(viii).
10. \(\vdash(A \vee \neg A)\), by (DNE), from (ix).

The principle \((\theta \vee \neg \theta)\) is sometimes called thelaw of excluded middle. It is not valid in intuitionisticlogic.

Let \(\theta, \neg \theta\) be a pair of contradictory opposites, andlet \(\psi\) be any sentence at all. By (As) we have \(\{\theta, \neg\theta, \neg \psi \}\vdash \theta\) and \(\{\theta, \neg \theta, \neg\psi \}\vdash \neg \theta\). So by \((\neg\)I), \(\{\theta, \neg\theta \}\vdash \neg \neg \psi\). So, by (DNE) we have \(\{\theta ,\neg \theta \}\vdash \psi\) . That is, anything at all follows from apair of contradictory opposites. Some logicians introduce a rule tocodify a similar inference:

If \(\Gamma_1 \vdash \theta\) and \(\Gamma_2 \vdash \neg \theta\),then for any sentence \(\psi, \Gamma_1, \Gamma_2 \vdash \psi\)

The inference is sometimes calledex falso quodlibet or, morecolorfully,explosion. Some call it“\(\neg\)-elimination”, but perhaps this stretches thenotion of “elimination” a bit. We do not officiallyincludeex falso quodlibet as a separate rule in \(D\), butas will be shown below (Theorem 10), each instance of it is derivablein our system \(D\).

Some logicians object toex falso quodlibet, on the groundthat the sentence \(\psi\) may beirrelevant to any of thepremises in \(\Gamma\). Suppose, for example, that one starts withsome premises \(\Gamma\) about human nature and facts about certainpeople, and then deduces both the sentence “Clinton hadextra-marital sexual relations” and “Clinton did not haveextra-marital sexual relations”. One can perhaps conclude thatthere is something wrong with the premises \(\Gamma\). But should webe allowed to then deduceanything at all from \(\Gamma\)?Should we be allowed to deduce “The economy is sound”?

A small minority of logicians, calleddialetheists, hold thatsome contradictions are actually true. For them,ex falsoquodlibet is not truth-preserving.

Deductive systems that demur fromex falso quodlibet arecalledparaconsistent. Most relevant logics areparaconsistent. See the entries onrelevance logic,paraconsistent logic, anddialetheism. Or see Anderson and Belnap [1975], Anderson, Belnap, and Dunn [1992],and Tennant [1997] for fuller overviews of relevant logic; and Priest[2006a,b], for dialetheism. Deep philosophical issues concerning thenature oflogical consequence are involved. Far be it for an article in a philosophy encyclopediato avoid philosophical issues, but space considerations preclude afuller treatment of this issue here. Suffice it to note that theinferenceex falso quodlibet is sanctioned in systems ofclassical logic, the subject of this article. It is essentialto establishing the balance between the deductive system and thesemantics (see §5 below).

The next pieces of \(D\) are the clauses for the quantifiers. Let\(\theta\) be a formula, \(v\) a variable, and \(t\) a term (i.e., avariable or a constant). Then define \(\theta(v|t)\) to be the resultof substituting \(t\) for eachfree occurrence of \(v\) in\(\theta\). So, if \(\theta\) is \((Qx \amp \exists\)xPxy),then \(\theta(x|c)\) is \((Qc \amp \exists\)xPxy). The lastoccurrence of \(x\) is not free.

A sentence in the form \(\forall v \theta\) is an analogue of theEnglish “for every \(v, \theta\) holds”. So one should beable to infer \(\theta(v|t)\) from \(\forall v \theta\) for any closedterm \(t\). Recall that the only closed terms in our system areconstants.

\((\forall \mathrm{E})\)

If \(\Gamma \vdash \forall v \theta\), then \(\Gamma \vdash\theta(v|t)\), for any closed term \(t\).

The idea here is that if \(\forall v \theta\) is true, then \(\theta\)should hold of \(t\), no matter what \(t\) is.

The introduction clause for the universal quantifier is a bit morecomplicated. Suppose that a sentence \(\theta\) contains a closed term\(t\), and that \(\theta\) has been deduced from a set of premises\(\Gamma\). If the closed term \(t\) does not occur in any member of\(\Gamma\), then \(\theta\) will hold no matter which object \(t\) maydenote. That is, \(\forall v \theta\) follows.

\((\forall \mathrm{I})\)

For any closed term \(t\), if \(\Gamma\vdash\theta (v|t)\), then\(\Gamma\vdash\forall v\theta\) provided that \(t\) is not in\(\Gamma\) or \(\theta\).

This rule \((\forall \mathbf{I})\) corresponds to a common inferencein mathematics. Suppose that a mathematician says “let \(n\) bea natural number” and goes on to show that \(n\) has a certainproperty \(P\), without assuming anything about \(n\) (except that itis a natural number). She then reminds the reader that \(n\) is“arbitrary”, and concludes that \(P\) holds forall natural numbers. The condition that the term \(t\) notoccur in any premise is what guarantees that it is indeed“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”. Ifwe have established (or assumed) that a given object \(t\) has a givenproperty, then it follows that there is something that has thatproperty.

\((\exists \mathrm{I})\)

For any closed term \(t\), if \(\Gamma\vdash\theta (v|t)\) then\(\Gamma\vdash\exists v\theta\).

The elimination rule for \(\exists\) is not quite as simple:

\((\exists \mathrm{E})\)

For any closed term \(t\), if \(\Gamma_1\vdash\exists v\theta\)and \(\Gamma_2, \theta(v|t)\vdash\phi\), then \(\Gamma_1,\Gamma_2\vdash\phi\), provided that \(t\) does not occur in \(\phi\),\(\Gamma_2\) or \(\theta\).

This elimination rule also corresponds to a common inference. Supposethat a mathematician assumes or somehow concludes that there is anatural number with a given property \(P\). She then says “let\(n\) be such a natural number, so that \(Pn\)”, and goes on toestablish a sentence \(\phi\), which does not mention the number\(n\). If the derivation of \(\phi\) does not invoke anything about\(n\) (other than the assumption that it has the given property\(P)\), then \(n\) could have been any number that has the property\(P\). That is, \(n\) is anarbitrary number with property\(P\). It does not matter which number \(n\) is. Since \(\phi\) doesnot mention \(n\), it follows from the assertion that something hasproperty \(P\). The provisions added to \((\exists\)E) are toguarantee that \(t\) is “arbitrary”.

The final items are the rules for the identity sign “=”.The introduction rule is about a simple as can be:

\(({=}\mathrm{I})\)

\(\Gamma \vdash t=t\), where \(t\) is any closed term.

This “inference” corresponds to the truism that everythingis identical to itself. The elimination rule corresponds to aprinciple that if \(a\) is identical to \(b\), then anything true of\(a\) is also true of \(b\).

\(({=}\mathrm{E})\)

For any closed terms \(t_1\) and \(t_2\), if \(\Gamma_1 \vdash t_1=t_2\) and \(\Gamma_2 \vdash \theta\), then \(\Gamma_1, \Gamma_2\vdash \theta'\), where \(\theta'\) is obtained from \(\theta\) byreplacing one or more occurances of \(t_1\) with \(t_2\).

The rule \(({=}\mathrm{E})\) indicates a certain restriction in theexpressive resources of our language. Suppose, for example, that Harryis identical to Donald (since his mischievous parents gave him twonames). According to most people’s intuitions, it would notfollow from this and “Dick knows that Harry is wicked”that “Dick knows that Donald is wicked”, for the reasonthat Dick might not know that Harry is identical to Donald. Contextslike this, in which identicals cannot safely be substituted for eachother, are called “opaque”. We assume that our language\(\LKe\) has no opaque contexts.

One final clause completes the description of the deductive system\(D\):

(*)

That’s all folks. \(\Gamma \vdash \theta\) only if\(\theta\) follows from members of \(\Gamma\) by the above rules.

Again, this clause allows proofs by induction on the rules used toestablish an argument. If a property of arguments holds of allinstances of (As) and \(({=}\mathrm{I})\), and if the other rulespreserve the property, then every argument that is deducible in \(D\)enjoys the property in question.

Before moving on to the model theory for \(\LKe\), we pause to note afew features of the deductive system. To illustrate the level ofrigor, we begin with a lemma that if a sentence does not contain aparticular closed term, we can make small changes to the set ofsentences we prove it from without problems. We allow ourselves theliberty here of extending some previous notation: for any terms \(t\)and \(t'\), and any formula \(\theta\), we say that \(\theta(t|t')\)is the result of replacing all free occurrences of \(t\) in \(\theta\)with \(t'\).

Theorem 8 allows us to add on premises at will. It follows that\(\Gamma \vdash \phi\) if and only if there is a subset\(\Gamma'\subseteq \Gamma\) such that \(\Gamma'\vdash \phi\). Somesystems of relevant logic do not have weakening, nor doessubstructural logic (See the entries onrelevance logic,substructural logics, andlinear logic).

By clause (*), all derivations are established in a finite number ofsteps. So we have

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, some think,essential to reasoning. In some logical systems, the cut principle isa deep theorem; in others it is invalid. The system here was designed,in part, to make the proof of Theorem 11 straightforward.

If \(\Gamma \vdash_D \theta\), then we say that the sentence\(\theta\) is adeductive consequence of the set of sentences\(\Gamma\), and that the argument \(\langle \Gamma,\theta \rangle\) isdeductively valid. A sentence \(\theta\) is alogicaltheorem, or adeductive logical truth, if \(\vdash_D\theta\). That is, \(\theta\) is a logical theorem if it is adeductive consequence of the empty set. A set \(\Gamma\) of sentencesisconsistent if there is no sentence \(\theta\) such that\(\Gamma \vdash_D \theta\) and \(\Gamma \vdash_D \neg \theta\). Thatis, a set is consistent if it does not entail a pair of contradictoryopposite sentencess.

Define a set \(\Gamma\) of sentences of the language \(\LKe\) to bemaximally consistent if \(\Gamma\) is consistent and forevery sentence \(\theta\) of \(\LKe\), if \(\theta\) is not in\(\Gamma\), then \(\Gamma,\theta\) is inconsistent. In other words,\(\Gamma\) is maximally consistent if \(\Gamma\) is consistent, andadding any sentence in the language not already in \(\Gamma\) rendersit inconsistent. Notice that if \(\Gamma\) is maximally consistentthen \(\Gamma \vdash \theta\) if and only if \(\theta\) is in\(\Gamma\).

Notice that this proof uses a principle corresponding to the law ofexcluded middle. In the construction of \(\Gamma'\), we assumed that,at each stage, either \(\Gamma_n\) is consistent or it is not.Intuitionists, who demur from excluded middle, do not accept theLindenbaum lemma.

4. Semantics

Let \(K\) be a set of non-logical terminology. Aninterpretation for the language \(\LKe\) is a structure \(M =\langle d,I\rangle\), where \(d\) is a non-empty set, called thedomain-of-discourse, or simply thedomain, of theinterpretation, and \(I\) is aninterpretation function.Informally, the domain is what we interpret the language \(\LKe\) tobe about. 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 thedomain \(d\).

Thus we assume that every constant denotes something. Systems wherethis is not assumed are calledfree logics (see the entry onfree logic). Continuing,

Define \(s\) to be avariable-assignment, or simply anassignment, on an interpretation \(M\), if \(s\) is afunction from the variables to the domain \(d\) of \(M\). The role ofvariable-assignments is to assign denotations to thefreevariables of open formulas. (In a sense, the quantifiers determine the“meaning” of the bound variables.)

Let \(t\) be a term of \(\LKe\). We define thedenotation of\(t\) in \(M\) under \(s\), in terms of the interpretation functionand variable-assignment:

If \(t\) is a constant, then \(D_{M,s}(t)\) is \(I(t)\), and if \(t\)is a variable, then \(D_{M,s}(t)\) is \(s(t)\).

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 define a relation ofsatisfaction betweeninterpretations, variable-assignments, and formulas of \(\LKe\). If\(\phi\) is a formula of \(\LKe, M\) is an interpretation for\(\LKe\), and \(s\) is a variable-assignment on \(M\), then we write\(M,s\vDash \phi\) for \(M\)satisfies \(\phi\)under theassignment \(s\). The idea is that \(M,s\vDash \phi\) is ananalogue of “\(\phi\) comes out true when interpreted as in\(M\) via \(s\)”.

We proceed by recursion on the complexity of the formulas of\(\LKe\).

If \(t_1\) and \(t_2\) are terms, then \(M,s\vDash t_1 =t_2\) if andonly if \(D_{M,s}(t_1)\) is the same as \(D_{M,s}(t_2)\).

This is about as straightforward as it gets. An identity \(t_1 =t_2\)comes out true if and only if the terms \(t_1\) and \(t_2\) denote thesame thing.

If \(P^0\) is a zero-place predicate letter in \(K\), then \(M,s\vDashP\) if and only if \(I(P)\) is truth.

IfS\(^n\) is an \(n\)-place predicate letter in \(K\) and\(t_1, \ldots,t_n\) are terms, then \(M,s\vDash St_1 \ldots t_n\) ifand only if the \(n\)-tuple \(\langle D_{M,s}(t_1),\ldots,D_{M,s}(t_n)\rangle\) is in \(I(S)\).

This takes care of the atomic formulas. We now proceed to the compoundformulas of the language, more or less following the meanings of theEnglish counterparts of the logical terminology.

The idea here is that \(\forall v\theta\) comes out true if and onlyif \(\theta\) comes out true no matter what is assigned to thevariable \(v\). The final clause is similar.

\(M,s\vDash \exists v\theta\) if and only if \(M,s'\vDash \theta\),for some assignment \(s'\) that agrees with \(s\) except possibly atthe variable \(v\).

So \(\exists v\theta\) comes out true if there is an assignment to\(v\) that makes \(\theta\) 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 give denotationsto the free variables. We now show that variable-assignments play noother role.

By Theorem 14, if \(\theta\) is a sentence, and \(s_1, s_2\), are anytwo variable-assignments, then \(M,s_1 \vDash \theta\) if and only if\(M,s_2 \vDash \theta\). So we can just write \(M\vDash \theta\) if\(M,s\vDash \theta\) for some, or all, variable-assignments \(s\). Sowe define

\(M\vDash \theta\) where \(\theta\) is a sentence just in case\(M,s\vDash\theta\) for all variable assignments \(s\).

In this case, we call \(M\) amodel of \(\theta\).

Suppose that \(K'\subseteq K\) are two sets of non-logical terms. If\(M = \langle d,I\rangle\) is an interpretation of \(\LKe\), then wedefine therestriction of \(M\) to \(\mathcal{L}1K'{=}\) tobe the interpretation \(M'=\langle d,I'\rangle\) such that \(I'\) isthe restriction of \(I\) to \(K'\). That is, \(M\) and \(M'\) have thesame domain and agree on the non-logical terminology in \(K'\). Astraightforward induction establishes the following:

In short, the satisfaction of a sentence \(\theta\) only depends onthe domain of discourse and the interpretation of the non-logicalterminology in \(\theta\).

We say that an argument \(\langle \Gamma,\theta \rangle\) issemantically valid, or justvalid, written \(\Gamma\vDash \theta\), if for every interpretation \(M\) of the language, if\(M\vDash\psi\), for every member \(\psi\) of \(\Gamma\), then\(M\vDash\theta\). If \(\Gamma \vDash \theta\), we also say that\(\theta\) is alogical consequence, orsemanticconsequence, ormodel-theoretic consequence of\(\Gamma\). The definition corresponds to the informal idea that anargument is valid if it is not possible for its premises to all betrue and its conclusion false. Our definition of logical consequencealso sanctions the common thesis that a valid argument istruth-preserving – to the extent that satisfaction representstruth. Officially, an argument in \(\LKe\) is valid if its conclusioncomes out true under every interpretation of the language in which thepremises are true. Validity is the model-theoretic counterpart todeducibility.

A sentence \(\theta\) islogically true, orvalid,if \(M\vDash \theta\), for every interpretation \(M\). A sentence islogically true if and only if it is a consequence of the empty set. If\(\theta\) is logically true, then for any set \(\Gamma\) ofsentences, \(\Gamma \vDash \theta\). Logical truth is themodel-theoretic counterpart of theoremhood.

A sentence \(\theta\) issatisfiable if there is aninterpretation \(M\) such that \(M\vDash \theta\). That is, \(\theta\)is satisfiable if there is an interpretation that satisfies it. A set\(\Gamma\) of sentences is satisfiable if there is an interpretation\(M\) such that \(M\vDash\theta\), for every sentence \(\theta\) in\(\Gamma\). If \(\Gamma\) is a set of sentences and if \(M\vDash\theta\) for each sentence \(\theta\) in \(\Gamma\), then we say that\(M\) is amodel of \(\Gamma\). So a set of sentences issatisfiable if it has a model. Satisfiability is the model-theoreticcounterpart to consistency.

Notice that \(\Gamma \vDash \theta\) if and only if the set\(\Gamma,\neg \theta\) is not satisfiable. It follows that if a set\(\Gamma\) is not satisfiable, then if \(\theta\) is any sentence,\(\Gamma \vDash \theta\). This is a model-theoretic counterpart toex falso quodlibet (see Theorem 10). We have the following,as an analogue to Theorem 12:

5. Meta-theory

We now present some results that relate the deductive notions to theirmodel-theoretic counterparts. The first one is probably the moststraightforward. We motivated both the various rules of the deductivesystem \(D\) and the various clauses in the definition of satisfactionin terms of the meaning of the English counterparts to the logicalterminology (more or less, with the same simplifications in bothcases). So one would expect that an argument is deducible, ordeductively valid, only if it is semantically valid.

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 to soundness(or Corollary 19) to hold. For all we know so far, we may not haveincluded enough rules of inference to deduce every valid argument. Theconverses to soundness and Corollary 19 are among the most importantand influential results in mathematical logic. We begin with thelatter.

A converse to Soundness (Theorem 18) is a straightforwardcorollary:

Our next item is a corollary of Theorem 9, Soundness (Theorem 18), andCompleteness:

Soundness and completeness together entail that an argument isdeducible if and only if it is valid, and a set of sentences 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-logical constants iseither finite or denumerably infinite. The interpretation we producedwas itself either finite or denumerably infinite. Thus, we have thefollowing:

Corollary 23. Löwenheim-Skolem Theorem. Let\(\Gamma\) be a satisfiable set of sentences of the language \(\LKe\).If \(\Gamma\) is either finite or denumerably infinite, then\(\Gamma\) has a model whose domain is either finite or denumerablyinfinite.

In general, let \(\Gamma\) be a satisfiable set of sentences of\(\LKe\), and let \(\kappa\) be the larger of the size of \(\Gamma\)and denumerably infinite. Then \(\Gamma\) has a model whose domain isat most size \(\kappa\).

There is a stronger version of Corollary 23. Let \(M_1 =\langled_1,I_1\rangle\) and \(M_2 =\langle d_2,I_2\rangle\) beinterpretations of the language \(\LKe\). Define \(M_1\) to be asubmodel of \(M_2\) if \(d_1 \subseteq d_2, I_1 (c) = I_2(c)\) for each constant \(c\), and \(I_1\) is the restriction of\(I_2\) to \(d_1\). For example, if \(R\) is a binary relation letterin \(K\), then for all \(a,b\) in \(d_1\), the pair \(\langlea,b\rangle\) is in \(I_1 (R)\) if and only if \(\langle a,b\rangle\)is in \(I_2 (R)\). If we had included function letters among thenon-logical terminology, we would also require that \(d_1\) be closedunder their interpretations in \(M_2\). Notice that if \(M_1\) is asubmodel of \(M_2\), then any variable-assignment on \(M_1\) is also avariable-assignment on \(M_2\).

Say that two interpretations \(M_1 =\langle d_1,I_1\rangle, M_2=\langle d_2,I_2\rangle\) areequivalent if one of them is asubmodel of the other, and for any formula of the language and anyvariable-assignment \(s\) on the submodel, \(M_1,s\vDash \theta\) ifand only if \(M_2,s\vDash \theta\). Notice that if two interpretationsare equivalent, then they satisfy the same sentences.

Another corollary to Compactness (Corollary 22) is the opposite of theLöwenheim-Skolem theorem:

Combined, the proofs of the downward and upward Löwenheim-Skolemtheorems show that for any satisfiable set \(\Gamma\) of sentences, ifthere is no finite bound on the models of \(\Gamma\), then for anyinfinite cardinal \(\kappa\), there is a model of \(\Gamma\) whosedomain has sizeexactly \(\kappa\). Moreover, if \(M\) is anyinterpretation whose domain is infinite, then for any infinitecardinal \(\kappa\), there is an interpretation \(M'\) whose domainhas size exactly \(\kappa\) such that \(M\) and \(M'\) areequivalent.

These results indicate a weakness in the expressive resources offirst-order languages like \(\LKe\). No satisfiable set of sentencescan guarantee that its models are all denumerably infinite, nor canany satisfiable set of sentences guarantee that its models areuncountable. So in a sense, first-order languages cannot express thenotion of “denumerably infinite”, at least not in themodel theory. (See the entry onsecond-order and higher-order logic.)

Let \(A\) be any set of sentences in a first-order language \(\LKe\),where \(K\) includes terminology for arithmetic, and assume that everymember of \(A\) is true of the natural numbers. We can even let \(A\)be the set of all sentences in \(\LKe\) that are true of the naturalnumbers. Then \(A\) has uncountable models, indeed models of anyinfinite cardinality. Such interpretations are among those that aresometimes calledunintended, ornon-standard modelsof arithmetic. Let \(B\) be any set of first-order sentences that aretrue of the real numbers, and let \(C\) be any first-orderaxiomatization of set theory. Then if \(B\) and \(C\) are satisfiable(in infinite interpretations), then each of them has denumerablyinfinite models. That is, any first-order, satisfiable set theory ortheory of the real numbers, has (unintended) models the size of thenatural numbers. This is despite the fact that a sentence (seemingly)stating that the universe is uncountable is provable in mostset-theories. This situation, known as theSkolem paradox,has generated much discussion, but we must refer the reader elsewherefor a sample of it (see the entry onSkolem’s paradox and Shapiro 1996).

6. The One Right Logic?

Surely, logic has something to do with correct reasoning, or at leastcorrect deductive reasoning. The details of the connection are subtle,and controversial – see Harman [1984] for an influential study.It is common to say that someone has reasoned poorly if they have notreasoned logically, or that a given (deductive) argument is bad, andmust be retracted, if it is shown to be invalid.

Some philosophers and logicians have maintained that there is a singlelogical system that is uniquely correct, in its role of characterizingvalidity. Among those, some, perhaps most, favor classical,first-order logic as uniquely correct, as the One True Logic. See, forexample, Quine [1986], Resnik [1996], Rumfitt [2015], Williamson[2017], and a host of others.

That classical, first-order logic should be given this role is perhapsnot surprising. It has rules which are more or less intuitive, and issimple for how strong it is. As we have seen in section 5, classical,first-order logic has interesting and important meta-theoreticproperties, such as soundness and completeness, that have lead to manyimportant mathematical and logical studies.

However, as noted, the main meta-theoretic properties of classical,first-order logic lead to expressivelimitations of theformal languages and model-theoretic semantics. Key notions, likefinitude, countability, minimal closure, natural number, and the likecannot be expressed.

Barwise [1985, 5] once remarked:

As logicians, we do our subject a disservice by convincing others thatlogic is first-order and then convincing them that almost none of theconcepts of modern mathematics can really be captured in first-orderlogic.

And Wang [1974, 154]:

When we are interested in set theory or classical analysis, theLöwenheim-Skolem theorem is usually taken as a sort of defect...of the first-order logic... [W]hat is established [by these theorems]is not that first-order logic is the only possible logic but ratherthat it is the only possible logic when we in a sense deny reality tothe concept of [the] uncountable...

Other criticisms of classical, first-order logic have also beenlodged. There are issues with its ability to deal with certainparadoxes (see, for example, the entry onRussel’s paradox), its apparent overgeneration of beliefs (see the entry on (the normative status of logic), and some argue that it has some arguments that do not match with theway we normally think we think (see for example, the entry onrelevance logic).

There are two main options available to those who are critical ofclassical, first-order logic, as the One True Logic. One is to proposesome other logic as the One True Logic. Priest [2006a] describes themethodology one might use to settle in the One True Logic.

The other main option is to simply deny that there is a single logicthat qualifies as the One True Logic. One instance of this is a kindoflogical nihilism, a thesis that there is no correct logic.Another is alogical pluralism, the thesis that a variety ofdifferent logical all qualify as correct, or best, or even the truelogic, at least in various contexts.

Of course, this is not the place to pursue this matter in detail. SeeBeall and Restall [2006] and Shapiro [2014] for examples of pluralism,and the entry onlogical pluralism for an overview of the terrain for both logical pluralism and logicalnihilism.

We close with brief sketches of some of the main alternatives toclassical, first-order logic, providing references to other work andentries to this Encyclopedia. See also the second half of Shapiro andKouri Kissel [2022].

6.1 Rivals to classical, first-order logic

Approximations

In recent years, some work has been done to "approximate" classicallogic. The idea is to get as close to classical logic as possible, inorder to preserve some of the benefits, while at the same timeremoving some limitations of classical logic, like being closer tointuitive inference or applying to things like vagueness andparadoxes.

For example, Barrio, Pailos and Szmuc [2020] show that we canapproximate classical logic in something called the ST-hierarchy (STfor strict-tolerant, from Cobreros, Egre, Ripley and van Rooij[2012a,b]). This allows them to avoid certain classical problems ateach level of the hierarchy, like some of the paradoxes, while at thesame time maintaining many of the benefits of the strength ofclassical logic when considering the full hierarchy.

Dave Ripley [2013] provides a multi-sequent calculus version of“classical logic” that he argues solves some of theparadoxes. Notably, he claims it solves at least the Sorites and LiarParadoxes (see the entries on thesorites paradox andliar Paradox). The system conservatively extends classical logic. Ripley claims thatthis is what makes it classical. However, the system is nottransitive, and does not have a Cut rule.

There are, of course, some questions about whether these new logicsarereally classical, but it is informative worknonetheless.

Expansions

One way to extend classical, first-order logic is to add additionaloperators to the underlying formal language.Modal logic addsoperators which designate necessity and possibility. So, we can saythat a proposition is possibly true, or necessarily true, rather thanjust true.

W. V. O Quine [1953] once argued that it is not coherent forquantifiers to bind variables inside modal operators, but opinion onthis matter has since changed considerably (see, for example, Barcan[1990]). There is now a thriving industry of developing modal logicsto capture various kinds of modality and temporal operators. See theentry onmodal logic.

All of the formal languages sketched above have only one sort ofvariable. These are sometimes calledfirst-order variables.Each interpretation of the language has a domain, which is the rangeof these first-order variables. It is what the language is about,according to the given interpretation.Second-order variablesrange over properties, sets, classes, relations, or functions of theitems in that domain.Third-order variables range overproperties, classes, relations of whatever is in the range of thesecond-order variables. And it goes on from there.

A formal language is calledsecond-order if it hassecond-order variables and first-order variables, and no others;Third-order if it has third-order, second-order, andfirst-order variables and no others, etc. A formal language ishigher-order if it is at least second-order.

As noted, it is not an exaggeration to say that classical, first-orderlogic is the paradigm of contemporary logical theory. Most textbooksdo not mention higher-order languages at all, and most of the restgive it scant treatment.

A number of different deductive systems and model-theoretic semanticshave been proposed for second- and higher-order languages. For thesemantics, the main additional feature of the model-theory is tospecify a range of the higher-order variables.

InHenkin semantics, each interpretation specifies a specificrange of the higher-order variables. For monadic second-ordervariables, each interpretation specifies a non-empty subset of thepowerset of the domain, for two-place second-order variables, anon-empty set of ordered pairs of members of the domain, etc. Thesystem has all of the above limitative meta-theoretic results. Thereis a deductive system that is sound and complete for Henkin semantics;the logic is compact; and the downward and upwardLöwenheim-Skolem theorems all hold.

In so-calledstandard semantics, sometimes calledfullsemantics, monadic second-order variables range over the entirepowerset of the domain; two-place second-order variables range overthe entire class of ordered pairs of members of the domain, etc. Itcan be shown that second-order languages, with standard semantics, cancharacterize many mathematical notions and structures, up toisomorphism. Examples include the notions of finitude, countability,well-foundedness, minimal closure, and structures like the naturalnumbers, the real numbers, and the complex numbers. As a result, noneof the limitative theorems of classical, first-order logic hold: thereis no effective deductive system is both sound and complete, the logicis not compact, and both Löwenheim-Skolem theorems fail. Some,such as Quine [1986], argue that second-order logic, with standardsemantics is not really logic, but is a form of mathematics, settheory in particular. For more on this, see Shapiro [1991] and theentry onhigher-order logic, along with the many references cited there.

One might also consider generalized quantifiers as an expansion ofclassical first-order logic (see the entry ongeneralized quantifiers). These quantifiers allow from an expansion between the classical“all” and “some” , and can accommodatequantifiers like “most” , “less than half” ,“usually” , etc. They are useful from both a logical andlinguistic perspective. For example, Kennedy andVäänänen [2021] use generalized quantifiers to arguethat “ uncountable” is a logical notion.

6.2 Sublogics of classical, first-order logic

Some philosophers and logicians argue that classical, first-orderlogic is too strong: it declares that some argument-forms are validwhich are not. Here we sketch two kinds of proposals.

Intuitionistic logic

Advocates ofintuitionistic logic reject the validity of the(so-called) Law of Excluded Middle:

and other inferences related to this, such as Double NegationElimination (DNE):

Roughly speaking, there are two main motivations for theserestrictions. The traditional intuitionists L. E. J. Brouwer (e.g.,[1964a], [1964b]) and Arend Heyting (e.g. [1956]) held that theessence of mathematics is idealized mental construction. Consider, forexample, the proposition that for every natural number \(n\), there isa prime number \(m \gt n\) such that \(m \lt n!+2\). For Brouwer, thisproposition invokes aprocedure that, given any naturalnumber \(n\), produces a prime number \(m\) that is greater than \(n\)but less than \(n!+2\). The proposition expresses the existence ofsuch a procedure. Given this orientation, we have no reason to holdthat for any mathematical proposition \(\Phi\), we can establisheither the procedure associated with \(\Phi\) or the procedureassociated with \(\neg \Phi\).

Michael Dummett (e.g., [1978]) provides general arguments concerninghow language functions, as a vehicle of communication, to argue thatintuitionistic logic is uniquely correct, the One True Logic, not justfor mathematics.

For an overview of intuitionistic logic, and its philosophicalmotivation, see the entry onintuitionistic logic.

Relevance and paraconsistency

This time the target inference, to be declared invalid, is the one weabove callex falso quodlibet, abbreviated (EFQ):\[{\rm If} \ \Gamma_1 \vdash \Theta \ {\rm and} \ \Gamma_2 \vdash \neg\Theta \ {\rm then} \ \Gamma_1, \Gamma_2 \vdash \Psi\] We can focus attention one kind of instance of this:\[\Phi, \neg\Phi \vdash \Psi,\] sometimes colorfully called “explosion”. Itsays that anything at all follows from a contradiction.

Logics that regard (EFQ) as invalid are calledparaconsistent. Broadly speaking, there are two camps oflogicians advocating for paraconsistent systems, either as candidatesfor the One True Logic or as instances of pluralism. One camp consistsof logicians who insist that in a valid argument, the premises must berelevant to the conclusion. Typically, relevance logiciansalso demur from certain classical logical truths calledparadoxesof material implication, such as \((\Phi \rightarrow (\Psi\rightarrow \Phi))\) and \((\Phi \rightarrow (\Psi \rightarrow\Psi))\).

For more, see the entry onrelevance logic, or Kerr [2019]. Classic works include Anderson and Belnap [1975],Anderson Belnap and Dunn [1992], and Read [1988]. Neil Tennant’s[2017] core logic is both relevant and intuitionistic.

The other main camp of logicians who prefer a paraconsistent logic (orparaconsistent logics) are advocates ofdialetheism, the viewthat some contradictions, some sentences in the form \[(\Phi \wedge \neg \Phi),\] aretrue. One supposed example is when \(\Phi\) is a statement of asemantic paradoxes, such as the Liar. Consider, for example, asentence \(\Phi\) that says that \(\Phi\) is not true.

In a system in which (EFQ) holds, any true contradiction would entailevery sentence of the formal language, thus rendering the language andtheory trivial. So, clearly, any logic for dialetheism would have tobe paraconsistent. See the entry ondialetheism. The classic work here is Priest [2006a].

Of course, the small sample presented here does not include everylogical system proposed as a rival to classical, first-order logic,again either as a candidate for the One True Logic, or as a furtherinstance of logical pluralism. See, for example, the entries onsubstructural logics,fuzzy logic, and many others.

Bibliography

• Anderson, Alan and Nuel Belnap, 1975,Entailment: The logic ofrelevance and necessity I, Princeton: Princeton UniversityPress.
• Anderson, Alan, Nuel Belnap, and J. Michael Dunn, 1992,Entailment: The logic of relevance and necessity II,Princeton: Princeton University Press.
• Barcan Marcus, Ruth. 1990, “A Backwards Look atQuine’s Animadversions on Modalities,” in R. Bartrett andR. Gibson (eds.),Perspectives on Quine, Cambridge:Blackwell.
• Barrio, Eduardo Alejandro., Federico Pailos, and Damian Szmuc,2020, “A Hierarchy of Classical and ParaconsistentLogics”,J Philos Logic, 49: 93–120.doi:10.1007/s10992-019-09513-z
• Barwise, Jon, 1985, “Model-theoretic logics: background andaims”, inModel-theoretic logics, edtied by Jon Barwiseand Soloman Feferman (eds.), New York, Springer-Verlag, pp.3–23.
• Beall, Jc and Greg Restall, 2006,Logical Pluralism,Oxford: Oxford University Press.
• Brouwer, L.E.J., 1949, “Consciousness, Philosophy andMathematics”,Journal of Symbolic Logic, 14(2):132–133.
• –––, 1964b, “Intuitionism andFormalism”, inPhilosophy of mathematics: selectedreadings edited by P. Benacerraf and H. Putnam, Englewood Cliffs,NJ, Cambridge University Press, (eds.), 77–89.
• Cobreros, Pablo, Paul Egré, David Ripley, and Robert vanRooij, 2012, “Tolerance and Mixed Consequence in theS’valuationist Setting”,Studia logica, 100(4),855–877.
• –––, 2012, “Tolerant, classical,strict”,Journal of Philosophical Logic, 41(2),347–385.
• Cook, Roy, 2002, “Vagueness and mathematicalprecision”,Mind, 111: 227–247.
• Corcoran, John, 1973, “Gaps between logical theory andmathematical practice”,The methodological unity ofscience, ed. by M. Bunge, Dordrecht: D. Reidel, 23–50.
• Davidson, Donald, 1984,Inquiries into truth andinterpretation, Oxford: Clarendon Press.
• Dummett, Michael, 2000,Elements of intuitionism, secondedition, Oxford: Oxford University Press.
• –––, 1978, “The philosophical basis ofintuitionistic logic”, inTruth and other enigmas,Cambridge, MA, Harvard University Press, 215–247.
• Gödel, Kurt, 1930, “Die Vollständigkeit der Axiomedes logischen Funktionenkalkuls”,Montatshefte fürMathematik und Physik 37, 349–360; translated as “Thecompleteness of the axioms of the functional calculus of logic”,in van Heijenoort 1967, 582–591.
• Harman, Gilbert, 1984, “Logic and reasoning”,Synthese, 60, 107–127.
• Heyting, A., 1956,Intuitionism, Amsterdam: North-HollandPublishing.
• Kerr, Alison Duncan, 2019, “A plea for KR”,Synthese, 198(4): 3047–3071.
• Lycan, William, 1984,Logical form in natural language,Cambridge, MA: The MIT Press.
• Montague, Richard, 1974,Formal philosophy, ed. by R.Thomason, New Haven: Yale University Press.
• Kennedy, Juliette, and Jouko Väänänen, 2021,Logicality and modelclasses.Bulletin of Symbolic Logic,27(4): 385–414.
• Priest, Graham, 2006a,In contradiction, a study of thetransconsistent, second, revised edition, Oxford: ClarendonPress.
• –––, 2006b,Doubt truth to be a liar,Oxford: Clarendon Press.
• Quine, W. V. O., 1960,Word and object, Cambridge, MA:The MIT Press.
• –––, 1953, “Three grades of modalinvolvement”,Proceedings of the XI^thInternational Congress of Philosophy, 14, Amsterdam, NorthHolland Publishing Company, 65–81.
• –––, 1986,Philosophy of logic, secondedition, Cambridge, Massachusetts: Harvard University Press.
• –––, 1986,Philosophy of logic, secondedition, Englewood Cliffs: Prentice-Hall.
• Read, Stephen, 1988,Relevant logic, Oxford: OxfordUniversity Press.
• Resnik, Michael, 1996, “Ought there to be but one truelogic”, inLogic and Reality: Essays on the Legacy of ArthurPrior, J. Copeland (ed.), Oxford: Oxford University Press,489–517.
• Ripley, David, 2013, “Paradoxes and Failures of Cut”,Australasian Journal of Philosophy, 91(1):139–164.
• Rumfitt, Ian, 2015,The Boundary Stones of Thought: An Essayin the Philosophy of Logic, Oxford: Oxford University Press.
• Shapiro, Stewart, 1991,Foundations withoutFoundationalism, Oxford: Clarendon Press.
• –––, 1996,The limits of logic: Second-orderlogic and the Skolem paradox,The international researchlibrary of philosophy, Dartmouth Publishing Company, 1996. (Ananthology containing many of the significant later papers on theSkolem paradox.)
• –––, 1998, “Logical consequence: modelsand modality”, inThe philosophy of mathematics today,edited by M. Schirn, Oxford: Oxford University Press,131–156.
• –––, 2014,Varieties of Logic, Oxford:Oxford University Press.
• Shapiro, Stewart and Teresa Kouri Kissel,Classical, firstorder logic, Cambridge Elements, Cambridge, Cambridge UniversityPress.
• Tennant, Neil, 1997,The taming of the true, Oxford:Clarendon Press.
• Van Heijenoort, Jean, 1967,From Frege to Gödel,Cambridge, Massachusetts: Harvard University Press. An anthologycontaining many of the major historical papers on mathematical logicin the early decades of the twentieth century.
• Wang, Hao, 1974,From Mathematics to Philosophy, London,Routledge and Kegan Paul.
• Williamson, Timothy, 2017, “Semantic paradoxes and abductivemethodology”, inReflections on the liar edited byBradley Armour-Garb, Oxford, Oxford University Press,325–346.

Further Reading

There are many fine textbooks on mathematical logic. A samplefollows.

• Boolos, George S., John P. Burgess, and Richard C. Jeffrey, 2007,Computability and logic, fifth edition, Cambridge, England:Cambridge University Press. Elementary and intermediate level.
• Bergmann, Merrie, James Moor, and Jack Nelson, 2013,The logicbook, sixth edition, New York: McGraw-Hill. Elementary andintermediate level.
• Church, Alonzo, 1956,Introduction to mathematical logic,Princeton: Princeton University Press. Classic textbook.
• Enderton, Herbert, 1972,A mathematical introduction tologic, New York: Academic Press. Textbook in mathematical logic,aimed at a mathematical audience.
• Forbes, Graeme, 1994,Modern Logic, Oxford: OxfordUniversity Press. Elementary textbook.
• Mendelson, Elliott, 1987,Introduction to mathematicallogic, third edition, Princeton: van Nostrand. Intermediate.

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

[Please contact the author with suggestions.]

Related Entries

logic: free |logic: infinitary |logic: intuitionistic |logic: linear |logic: modal |logic: paraconsistent |logic: relevance |logic: second-order and higher-order |logic: substructural |logic: temporal |logical consequence |logical form |logical truth |model theory |model theory: first-order |paradox: Skolem’s |proof theory: development of