This is a file in the archives of the Stanford Encyclopedia of Philosophy. |

The following sections provide the basics of a typical logic,
sometimes called "classical elementary logic" or "classical
first-order logic". Section 2 develops a formal language, with a
rigorous syntax and grammar. The formal language is a recursively
defined collection of strings on a fixed alphabet. As such, it has
no meaning, or perhaps better, the meaning of the formulas is given
by the deductive system and the semantics. Some of the symbols have
counterparts in ordinary language. We define an *argument* to
be a non-empty collection of formulas in the formal language, one of
which is designated to be the conclusion. The other formulas (if
any) in an argument are its premises. Section 3 sets up a deductive
system for the language, in the spirit of natural deduction. An
argument is *derivable* is there is a deduction from some of
its premises to its conclusion. Section 4 provides a model-theoretic
semantics. An argument is *valid* if there is no
interpretation (in the semantics) in which its premises are all true
and its conclusion false. This reflects the longstanding view that a
valid argument is truth-preserving.

In Section 5, we turn to relationships between the deductive system
and the semantics, and in particular, the relationship between
derivability and validity. We show that an argument is derivable only
if it is valid. This pleasant feature, called *soundness*,
entails that no deduction takes one from true premises to a false
conclusion. Thus, deductions preserve truth, and there aren't too
many deductions. Then we establish a converse, called
*completeness*, that an argument is valid only if it is
derivable. This establishes that the deductive system is rich enough
to provide a deduction for every valid argument. There are enough
deductions. All and only valid arguments are derivable. We briefly
indicate other features of the logic, some of which are corollaries to
soundness and completeness.

- 1. Introduction
- 2. Language
- 3. Deduction
- 4. Semantics
- 5. Meta-theory
- Bibliography
- Other Internet Resources
- Related Entries

Typically, ordinary reasoning takes place in a natural language, or perhaps a natural language augmented with some mathematical symbols. So our question begins with the relationship between a natural language and a formal language. Without attempting to be comprehensive, it may help to sketch several options on this matter.

One view is that the formal languages accurately exhibit actual
features of certain fragments of a natural language. Some
philosophers claim that declarative sentences of natural language
have underlying *logical forms* and that these forms are
displayed by formulas of a formal language. Other writers hold that
(successful) declarative sentences express *propositions*; and
formulas of formal languages somehow display the forms of these
propositions. On views like this, the components of a logic provide
the underlying deep structure of correct reasoning. A chunk of
reasoning in natural language is correct if the forms underlying the
sentences 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 Wilhelm
Leibniz, 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 natural
language should be *regimented*, cleaned up for serious
scientific and metaphysical work. One desideratum of the enterprise
is that the logical structures in the regimented language should be
transparent. It should be easy to "read off" the logical properties
of each sentence. A regimented language is similar to a formal
language regarding, for example, the explicitly presented rigor of
its syntax and its truth conditions.

On a view like this, deducibility and validity represent
*idealizations* of correct reasoning in natural language. A
chunk of reasoning is correct to the extent that it corresponds to,
or can be regimented by, a valid or deducible argument in a formal
language.

When mathematicians and many philosophers reason, they occasionally
invoke formulas in a formal language to help disambiguate, or
otherwise clarify what they mean. In other words, sometimes formulas
in a formal language are *used* in ordinary reasoning. This
suggests that one might think of a formal language as an
*addendum* to a natural language. Then our present question
concerns the relationship between this addendum and the original
language. What do deducibility and validity, as sharply defined on
the addendum, tell us about correct reasoning in general?

Another view is that a formal language is a *mathematical
model* of a natural language in roughly the same sense as, say, a
collection 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, a formal language displays certain features of natural
languages, or idealizations thereof, while ignoring or simplifying
other features. The purpose of mathematical models is to shed light
on what they are models of, without claiming that the model is
accurate in all respects or that the model should replace what it is
a model of. On a view like this, deducibility and validity represent
mathematical models of (perhaps different aspects of) correct
reasoning in natural languages. Correct chunks of reasoning
correspond, more or less, to valid or deducible arguments; incorrect
chunks of reasoning roughly correspond to invalid or non-deducible
arguments. See, for example, Corcoran [1973] or Shapiro [1998].

There is no need to adjudicate this matter here. Perhaps the truth lies in a combination of the above options, or maybe some other option is the correct, or most illuminating one. I raise the matter only to lend some philosophical perspective to the formal treatment that follows.

We envisage a potential infinity of individual constants. In the present system each constant is a single character, and so individual constants do not have an internal syntax. Thus we have an infinite alphabet. This last could be avoided by taking a constant likea,a_{1},b_{23},c,d_{22}, etc.

We also assume a stock of *individual variables*. These are
lower-case letters, near the end of the alphabet, with out without
numerical subscripts:

Variables serve a dual function. Sometimes a variable is used as a singular term to denote a specific, but unspecified (or arbitrary) object. For example, a mathematician might start a derivation: "Letw,x,y_{12},z,z_{4}, etc.

Constants and variables are the only terms in our formal language,
so all of our terms are simple, corresponding to proper names and
pronouns. Some authors also introduce *function letters*,
which allow complex terms corresponding to: "7+4" and "the wife of
Bill Clinton", or complex terms containing variables, like "the
father of *x*" and "*x*/*y*". Logic books aimed
at mathematicians are likely to contain function letters, probably
due to the centrality of functions to mathematical discourse. Books
aimed at a more general audience (or at philosophy students), may
leave out function letters, since it simplifies the syntax and
theory. We follow the latter route here. This is an instance of a
general tradeoff between presenting a system with greater expressive
resources, at the cost of making its formal treatment more complex.

For each natural number *n*, we introduce a stock of
*n*-place *predicate letters*. These are upper-case
letters at the beginning or middle of the alphabet. A superscript
indicates the number of places, and there may or may not be a
subscript. For example,

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.A^{3},B^{3}_{2},P^{3}, etc.

Zero-place predicate letters are sometimes called "sentence letters". They correspond to free-standing sentences whose internal structure does not matter. One-place predicate letters, called "monadic predicate letters", correspond to linguistic items denoting properties, like "being a man", "being red", or "being a prime number". Two-place predicate letters, "binary predicate letters", correspond to linguistic items denoting binary relations, like "is a parent of" or "is greater than". Three-place predicate letters correspond to three-place relations, like "lies on a straight line between". And so on.

The *non-logical terminology* of the language consists of its
individual constants and predicate letters. The symbol "=", for
identity, is not a non-logical symbol. In taking identity to be
logical, we provide explicit treatment for it in the deductive system
and the model-theoretic semantics. Most authors do the same, but
there is some controversy over the issue (Quine [1986, Chapter
5]). If *K* is a set of constants and predicate letters, then
we give the fundamentals of a language
1*K*=
built on this set of non-logical terminology. It may be called the
*first-order language with identity* on *K*. A similar
language that lacks the symbol for identity (or which takes identity
to be non-logical) may be called
1*K*,
first-order logic without identity.

The last one is an analogue of a statement that a certain relation (P^{4}xaab,C^{1}x,C^{1}a,D^{0},A^{3}abc.

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

¬, &, , , , , (, )We give a recursive definition of a

1. All atomic formulas of 1Asserting a sentence corresponding to ¬ is tantamount to denying the sentence corresponding to . The symbol "¬" is called "negation", and is a unary connective.K= are formulas of 1K=.2. If is a formula of 1

K=, then so is ¬.

3. If and are formulas of 1The ampersand "&" corresponds to the English "and" (when "and" is used to connect sentences). So ( & ) can be read " and ". The formula ( & ) is called the "conjunction"of and .K=, then so is ( & ).

4. If and are formulas of 1The wedge "" corresponds to "either . . . or . . . or both", so ( ) can be read " or ". The formula ( & ) is called the "disjunction"of and .K=, then so is ( ).

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 "binary connectives", since they serve to "connect" two sentences into one. Some authors introduce ( ) as an abbreviation of (( ) & ( )). The symbol "" is an analogue of the locution "if and only if".

6. If is a formula of 1The symbol "" is called aK= andvis a variable, thenvis a formula of 1K=.

7. If is a formula of 1The symbol "" is called anK= andvis a variable, thenvis a formula of 1K=.

8. That's all folks. That is, all formulas are constructed in accordance 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 under the operations presented in clauses (2)-(7), then the property holds of all formulas.

We next define the notion of an occurrence of a variable being
*free* or *bound* in a formula. All variables that
occur in an atomic formula are free. If a variable occurs free (or
bound) 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 in
them. 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 neither
free 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 the
quantifier. The occurrence of "*y*" and last occurrence of
"*x*" are free. In
*x*(*Ax*
*xBx*),
the "*x*" in *Ax* is bound by the initial universal
quantifier, while the other occurrence of *x* is bound by the
existential quantifier. The above syntax allows this "overlap" of bound
variables, and it does not create an ambiguity, but we will avoid such
formulas, as a matter of taste and clarity

Free variables correspond to place-holders, while bound variables
are used to express generality. If a formula has no free variables,
then it is called a *sentence*. If a formula has free
variables, it is called *open*.

We assume at the outset that all of the categories are disjoint. For example, no connective is also a quantifier or a variable, and the non-logical terms are not also parentheses or connectives. Also, the items within each category are distinct. For example, the sign for disjunction does not do double-duty as the negation symbol, and perhaps more significantly, no two-place predicate is also a one-place predicate.

One difference between natural languages like English and formal languages like 1Theorem 1. Every formula of 1K= has the same number of left and right parentheses. Moreover, each left parenthesis corresponds to a unique right parenthesis, which occurs to the right of the left parenthesis. Similarly, each right parenthesis corresponds to a unique left parenthesis, which occurs to the left of the given right parenthesis. If a parenthesis occurs between a matched pair of parentheses, then its mate also occurs within that matched pair. In other words, parentheses that occur within a matched pair are themselves matched.

Proof: By clause (8), every formula is built up from the atomic formulas using clauses (2)-(7). The atomic formulas have no parentheses (by the policy that the categories are disjoint). Parentheses are introduced only in clauses (3)-(5), and each time they are introduced as a matched set. So at any stage in the construction of a formula, the parentheses are paired off.

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 is crazy, or else it can mean that either both John is married and Mary is single, or else Joe is crazy. An ambiguity like this, due to different ways to parse the same sentence, is sometimes called an "amphiboly". If our formal language did not have the parentheses in it, it would have amphibolies. For example, there would be a "formula"

Can we be sure that there are no other amphibolies in our language?
That is, can we be sure that each formula of
1*K*= can be put
together in only one way? Showing this is our next task.

Let us temporarily use the term "unary marker" for the negation
symbol (¬) or a quantifier followed by a variable (e.g.,
*x*,
*z*).

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.Lemma 2. Each formula consists of a string of zero or more unary markers followed by either an atomic formula or a formula produced using a binary connective, via one of clauses (3)-(5).

Proof: We proceed by induction on the complexity of the formula or, in other words, on the number of formation rules that are applied. The Lemma clearly holds for atomic formulas. Letnbe a natural number, and suppose that the Lemma holds for any formula constructed fromnor fewer instances of clauses (2)-(7). Let be a formula constructed fromn+1 instances. The Lemma holds if the last clause used to construct was either (3), (4), or (5). If the last clause used to construct was (2), then is ¬. Since was constructed withninstances 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 the cases, 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 left parenthesis in .

Proof: Here we also proceed by induction on the number of instances of (2)-(7) used to construct the formula. Clearly, the Lemma holds for atomic formulas, since they have no parentheses. Suppose, then, that the Lemma holds for formulas constructed withnor fewer instances of (2)-(7), and let be constructed withn+1 instances. If the last clause applied was (3)-(5), then the Lemma holds since itself begins with a left parenthesis and ends with the matching right parenthesis. If the last clause applied 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 can apply the induction hypothesis. It follows that the Lemma holds for .

Lemma 4. Each formula contains at least one atomic formula.

We are finally in position to show that there is no amphiboly in our language.Theorem 5. Let , be nonempty sequences of characters on our alphabet, such that (i.e followed by ) is a formula. Then isnota formula.

Proof: By Theorem 1 and Lemma 3, if contains a left parenthesis, then the right parenthesis that matches the leftmost left parenthesis in comes at the end of , and so the matching right parenthesis is in . So, has more left parentheses than 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 by either an atomic formula or a formula produced using a binary connective, via one of clauses (3)-(5). If the latter formula was produced via one of clauses (3)-(5), then it begins with a left parenthesis. Since does not contain any parentheses, it must be a string of unary markers. 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 atomic formula, either in the formt_{1}=t_{2}orPt_{1}. . .t_{n}. 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 eithert_{1}by itself,t_{1}= by itself, or the predicate letterP, and perhaps some (but not all) of the termst_{1}, . . . ,t_{n}. In the first two cases, does not contain an atomic formula, by the policy that the categories do not overlap. SincePis ann-place predicate letter, by the policy that the predicate letters are distinct,Pis not anm-place predicate letter for anymn. So the part of that consists ofPfollowed by the terms is not an atomic formula. In all of these cases, then, does not contain an atomic formula. By Lemma 4, is not a formula.

This result is sometimes called "unique readability". It shows that each formula is produced from the atomic formulas via the various clauses in exactly one way. If was produced by clause (2), then itsTheorem 6. Let be any formula of 1K=. If is not atomic, then there is one 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) is atomic.

Proof: By Clause (8), either is atomic or it was produced by one of clauses (2)-(7). Thus, the first symbol in must be either a predicate letter, a term, a unary marker, or a left parenthesis. If the first symbol in is a predicate letter or term, then is atomic. In this case, was not produced by any of (2)-(7), since all such formulas begin with something other than a predicate letter or term. If the first symbol in is a negation sign "¬", then was produced by clause (2), and not by any other clause (since the other clauses produce formulas that begin with either a quantifier or a left parenthesis). Similarly, if begins with a universal quantifier, then it was produced by clause (6), and not by any other clause, and if begins with an existential quantifier, then it was produced by clause (7), and not by any other clause. The only case left is where begins with a left parenthesis. In this case, it must have been produced by one of (3)-(5), and not by any other clause. We only need to rule out the possibility that was produced 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. That is, (_{1}&_{2}) is the very same formula 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 are different. So was not produced by both Clause (3) and Clause (4). Similar reasoning takes care of the other combinations.

We write an argument in the form
<,
>,
where
is the set of premises and
is the conclusion. Remember
that
may be empty. We write
to indicate that
is deducible from
, or, in other words, that
the 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 relations
concerning the English analogues of the logical terminology in the
language. Again, we define the deducibility relation by recursion. We
start with a rule of assumptions:

We thus have that {} ; each premise follows from itself. We next present two clauses for each connective and quantifier. The clauses indicate how to "introduce" and "eliminate" formulas in which each symbol is the main connective.(As)If is a member of , then .

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 ( & ):

The name "&I" stands for "&-introduction"; "&E" stands for "&-elimination".(&I)If_{1}and_{2}, then_{1},_{2}( & ).

(&E)If ( & ) then ; and if ( & ) then .

Since, the symbol "" corresponds to the English "or", ( ) should be deducible from , and ( ) should also be deducible from :

(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.I) If then ( ); if then ( ).

(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 ( ).E) If_{1}( ),_{2}, and_{3}, , then_{1},_{2},_{3}.

(Our next clauses are for the negation sign, "¬". The underlying idea is that a formula is inconsistent with its negation ¬. They cannot both be true. We call a pair of formulas , ¬I) If , , then ( ).(

E) If_{1}( ) and_{2}, then_{1},_{2}.

There is some controversy over the other rule for the negation sign.(¬I)If_{1}, and_{2}, ¬, then_{1},_{2}¬.

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 not
the case that it is not the case that" . One might think that this last is
equivalent to
, and we have a rule to that
effect:

The name DNE stands for "double-negation elimination". This inference is rejected by philosophers and mathematicians who do not hold that each meaningful sentence is either true or not true.(DNE)If ¬¬, then .

To illustrate the parts of the deductive system *D* presented
thus far, I show that
(*A*
¬*A*):

(i) {¬(The principle ( ¬) is sometimes called theA¬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).

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) we have {, ¬} . That is, anything at all follows from a pair of contradictory opposites. Some logicians introduce a rule to codify a similar inference:

IfThe inference is sometimes called_{1}and_{2}¬, then for any formula ,_{1},_{2}

Some logicians object to *ex falso quodlibet*, on the ground
that the formula
may be *irrelevant* to
any of the premises in
. Suppose,
for example, that one starts with some premises
about human nature and
facts about certain people, and then deduces both the sentence "Clinton
had extra-marital sexual relations" and "Clinton did not have
extra-marital sexual relations". One can surely conclude that there is
something wrong with premises
. But should we be allowed
to 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 part
of *relevance logic*. See Anderson and Belnap [1975],
Anderson, Belnap, and Dunn [1992], and Tennant [1987]. Deep
philosophical issues concerning the nature of logical consequence are
involved. Far be it for an article in a philosophy encyclopedia to
avoid philosophical issues, but space considerations preclude a
fuller treatment of this issue here. Suffice it to note that the
inference is sanctioned in systems of *classical logic*, the
subject of this article. It is essential to establishing the balance
between 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* a
variable, and *t* a term (i.e., a variable or a constant). The
define
(*v*|*t*) to be
the result of substituting *t* for each *free* occurrence of
*v* in
. So, if
is (*Qx* &
*xPxy*), then
(*x*|*c*) is
(*Qc* &
*xPxy*). The last
occurrence of *x* is not free (but recall that we avoid using
formulas like this).

We have one other nicety to attend to. Suppose that
*v*_{1} and *v*_{2} are variables. It may
happen that some of the substituted instances of *v*_{2}
are bound in
(*v*_{1}|*v*_{2}).
When this happens, we say that there is a *clash* of the
variables. Suppose, for example, that
is
*y*(¬*x* =
*y*), and so
(*x*|*y*) is
*y*(¬*y* =
*y*). We say that a term *t*
is *free for* a variable *v* in
if either *t* is a
constant or there is no clash of variables in
(*v*|*t*). The idea is that no
substituted instance of *t* should become a bound variable in
(*v*|*t*).

A formula in the form
*v*
is an analogue of the English "for every
*v*,
holds". So one
should be able to infer
(*v*|*t*) from
*v*
:

(The idea here is that ifE) Ifv, then (v|t), provided thattis free forvin .

The introduction clause for the universal quantifier is a bit
more 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 occur
free in any member of
, then
will hold no matter which object *v* may
denote. That is,
*v* follows.

(This introduction rule corresponds to a common inference in mathematics. Suppose that a mathematician says "letI) If and the variablevdoes not occur free in any member of , thenv.

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 that
property. Again, we have to be careful with the syntax, and avoid
clashes of variables.

(The provision (1) keeps us from replacing bound variables. The provision (2) comes up only ifI) If , thenv, where is obtained from by substituting the variablevfor zero or more occurrences of a termt, provided that (1) iftis a variable, then all of the replaced occurrences oftare free in , and (2) all of the substituted occurrences ofvare free in .

The elimination rule for is not quite as simple:

(This elimination rule also corresponds to a common inference. Suppose that a mathematician asserts that there is a natural number with a given propertyE) If_{1}vand_{2}, , then_{1},_{2}, provided thatvdoes not occur free in , nor in any member of_{2}.

As noted in the previous section, some authors introduce different letters for bound variables and (what amounts to) free variables. This makes the syntax slightly more complex, but simplifies the provisions on some of the rules of inference. Writers of logic books often face tradeoffs like this.

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

This "inference" corresponds to the truism that everything is identical to itself. The elimination rule corresponds to a principle that if(=I)t=t, wheretis any term.

The rule (=E) indicates a certain restriction in the expressive resources of our language. Suppose, for example, that Harry is identical to Donald (since his mischievous parents gave him two names). It would not follow from this and "Dick knows that Harry is wicked" that "Dick knows that Donald is wicked", for the reason that Dick might not know that Harry is identical to Donald. Contexts like this, in which identicals cannot safely be substituted for each other, are called "opaque". We assume that our language 1(=E)If_{1}t_{1}=t_{2}and_{2}, then_{1},_{2}, where is obtained from by replacing zero or more occurrences oft_{1}witht_{2}, provided that no bound variables are replaced, and ift_{2}is a variable, then all of its substituted occurrences are free.

One final clause completes the description of the deductive system
*D*:

Again, this clause allows proofs by induction on the rules used to establish an inference. If a property of arguments holds of all instances of (As) and (=I), and if the other rules preserve the property, then every argument that is deducible in(*)That's all folks. only if follows from members of by the above rules.

Before moving on to the model theory for
1*K*=, we pause to
note a few features of the deductive system.

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 haveLemma 7.Suppose that_{D}, and letvbe a variable that does not occur free in or in any member of . Assume thatvis free forvin and in every member of . Let be {(v|v) | }. That is, is the result of replacing every free occurrence of a variablevwithvin every member of . Then_{D}(v|v).

Proof:The proof of this lemma is tedious, but we give its essentials. We proceed by induction on the number of rules that were used to arrive at . Suppose thatn>0 is a natural number, and that the lemma holds for any argument that was derived using fewer thannrules, and suppose that using exactlynrules. Ifn=1, then the rule applied is 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 the induction hypothesis to the deductions of and , and then apply (&I) to the 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 variablevmay occur free in and it may not be free forvin . In either case, first pick a new variableuthat does not occur (free or bound) in ( & ) or in any member of . Now apply the induction hypothesis, substitutinguforvin the deduction ( & ). Sincevdoes not occur free in or in any member of , those formulas are left unchanged. The maneuver removes any free occurrences ofvfrom the subformula . Now apply the induction hypothesis to the result, substitutingvforv, 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 thatn>0 is a natural number, and that the theorem holds for any argument that was derived using fewer thannrules. Suppose that_{1}using exactlynrules. Ifn=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 complications arise only in the rules (I) and (E), because there we have to pay attention to the conditions for the rules. Starting with (E), we have_{3}vand_{4}, , with_{1}being_{3},_{4}, andvnot 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 formv, and we have_{1}and the variablevdoes not occur free in any member of_{1}. The problem is thatvmay occur free in a member of_{2}, and so we cannot just invoke the induction hypothesis and apply (I) to the result. Letvbe a variable that does not occur (free or bound) in or in any member of_{2}, and let be the result of substitutingvfor every free occurrence ofvin_{2}. Sincevdoes 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, substitutingvfor the new variablev. The result is_{2}.

Theorem 11 allows us to chain together inferences. This fits the practice of establishing theorems and lemmas and then using those theorems and lemmas later, at will. The cut principle is, I think, essential to reasoning. In some logical systems, the cut principle is a deep theorem. The system here was designed to make the proof of Theorem 11 straightforward.Theorem 9. if and only if there is a finite such that .

Theorem 10. The rule of ex falso quodlibet is a "derived rule" ofD. 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 thatnis a natural number, and that the theorem holds for any argument that was derived using fewer thannrules. Suppose that_{2}, was derived using exactlynrules. If the last rule used was (=I), then_{1},_{2}is also an instance of (=I). If_{2}, is an instance 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.

If
_{D},
then we say that the formula
is a *deductive consequence* of the set of formulas
, and that the argument
<,> is *deductively
valid*. A formula is a *logical
theorem*, 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 it
does not entail a pair of contradictory opposite formulas.

Define a set of formulas of the language 1Theorem 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. Then either it is not the case that or it is not the case that ¬. For the converse, suppose that is inconsistent and let be any formula. We have that there is a formula such that both and ¬. By ex falso quodlibet (Theorem 10), .

Notice that this proof uses a principle corresponding to the law of excluded middle. In the construction of , we assumed that, at each stage, eitherTheorem 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 is maximally consistent.

Proof:Although this theorem holds in general, we assume here that the setKof 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 numbern, 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. Then there 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 numbernsuch 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.

IfDefinecis a constant inK, thenI(c) is a member of the domaind.If

P^{0}is a zero-place predicate letter inK, thenI(P^{0}) is a truth value, either truth or falsehood.If

Q^{1}is a one-place predicate letter inK, thenI(Q) is a subset ofd. Intuitively,I(Q) is the set of members of the domain that the predicateQholds of. IfQrepresents "red", thenI(Q) might be the red members of the domain.If

R^{2}is a two-place predicate letter inK, thenI(R) is a set of ordered pairs of members ofd. Intuitively,I(R) is the set of pairs of members of the domain that the relationRholds between. IfRrepresents "love", thenI(R) might consist of the pairs <a,b>, such thatalovesb.In general, if

Sis an^{n}n-place predicate letter inK, thenI(S) is a set of orderedn-tuples of members ofd.

We now define a relation of *satisfaction* between
interpretations, variable-assignments, and formulas of
1*K*=. If is a formula of
1*K*=, *M* is an interpretation for
1*K*=, and *s* is a
variable-assignment on *M*, then we write
*M*,*s* for
*M* *satisfies*
*under the assignment* *s*. The
idea is that
*M*,*s* is
an analogue of " comes out true when interpreted as in
*M* via *s*".

Let *t* be a term of
1*K*=.
We define the *denotation* of *t* in *M* under
*s*, in terms of the interpretation function and
variable-assignment:

Ifcis a constant, thenD_{M,s}(c) isI(c), and ifvis a variable, thenD_{M,s}(v) iss(v).

That is, the interpretation *M* assigns denotations to the
constants, while the variable-assignment assigns denotations to the
(free) variables. If the language contained function symbols, the
denotation function would be defined by recursion.

We now proceed by recursion on the complexity of the formulas of
1*K*=.

IfThis is about as straightforward as it gets. An identityt_{1}andt_{2}are terms, thenM,st_{1}=t_{2}if and only ifD_{M,s}(t_{1}) is the same asD_{M,s}(t_{2}).

IfP^{0}is a zero-place predicate letter inK, thenM,sPif and only ifI(P) is truth.If

Sis an^{n}n-place predicate letter inKandt_{1}, . . . ,t_{n}are terms, thenM,sSt_{1}. . .t_{n}if and only if then-tuple <D_{M,s}(t_{1}), . . . ,D_{M,s}(t_{n})> is inI(S).

This takes care of the atomic formulas. We now proceed to the compound formulas of the language, following the meanings of the English counterparts of the logical terminology.

The idea here is thatM,s¬ if and only if it is not the case thatM,s.

M,s(&) if and only if bothM,sandM,s.

M,s() if and only if eitherM,sorM,s.

M,s() if and only if either it is not the case thatM,s, orM,s.

M,svif and only ifM,s, for every assignmentsthat agrees withsexcept possibly at the variablev.

SoM,svif and only ifM,s, for some assignmentsthat agrees withsexcept possibly at the variablev.

Theorem 6, unique readability, assures us that this definition is coherent. At each stage in breaking down a formula, there is exactly one clause to be applied, and so we never get contradictory verdicts concerning satisfaction.

As indicated, the role of variable-assignments is to give denotations to the free variables. We now show that variable-assignments play no other role.

Recall that a sentence is a formula with no free variables. So by Theorem 14, if is a sentence, andTheorem 14.For any formula , ifs_{1}ands_{2}agree on the free variables in , thenM,s_{1}if and only ifM,s_{2}.

Proof:We proceed by induction on the complexity of the formula . The theorem clearly holds if is atomic, since in those cases only the values of the variable-assignments at the variables in figure in the definition. Assume, then, that the theorem holds for all formulas less complex than . And suppose thats_{1}ands_{2}agree on the free variables of . Assume, first, that is a negation, ¬. Then, by the induction hypothesis,M,s_{1}if and only ifM,s_{2}. So, by the clause for negation,M,s_{1}¬ if and only ifM,s_{2}¬. The cases where the main connective in is a binary connectives are also straightforward. Suppose that isv, and thatM,s_{1}v. Then there is an assignments_{1}that agrees withs_{1}except possibly atvsuch thatM,s_{1}. Lets_{2}be the assignment that agrees withs_{2}on the free variables not in and agrees withs_{1}on the others. Then, by the induction hypothesis,M,s_{2}. Notice thats_{2}agrees withs_{2}on every variable except possiblyv. SoM,s_{2}v. The converse is the same, and the case where begins with a universal quantifier is similar.

Suppose that
*K**K*
are two sets of non-logical terms. If
*M* = <*d*,*I*> is an interpretation of
1*K*=, then we define the
*restriction* of *M* to
1*K* be the
interpretation
*M*=<*d*,*I*>
such that *I* is the restriction of
*I* to
*K*. That is, *M*
and
*M* have the same domain and agree on
the non-logical terminology in
*K*. A
straightforward induction establishes the following:

In short, the satisfaction of a formula only depends on the domain of discourse, the interpretation of the non-logical terminology in , and the assignments to the free variables in .Theorem 15. IfMis the restriction ofMto 1K, then for every formula of 1K, ifsis any variable-assignment,M,sif and only ifM,s.

Theorem 16.If two interpretationsM_{1},M_{2}have the same domain and agree on the non-logical terminology of a formula , then ifsis any variable-assignment,M_{1},sif and only ifM_{2},s.

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
, we
also say that
is a *logical
consequence*, or *semantic consequence*, or
*model-theoretic consequence* of
. The
definition corresponds to the informal idea that an argument is valid
if it is not possible for its premises to all be true and its
conclusion false. Our definition of logical consequence also
sanctions the common thesis that a valid argument is
truth-preserving--to the extent that satisfaction represents
truth. Officially, an argument in 1*K*=
is valid if its conclusion comes out true under every interpretation
of the language in which the premises are true. Validity is the
model-theoretic counterpart to deducibility.

A formula
is *logically true*, or
*valid*, if
*M*,*s*,
for every interpretation *M* and assignment *s*. A
formula is logically true if and only if it is a consequence of the
empty 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 is
an interpretation *M* and a variable-assignment *s* on
*M* such that
*M*,*s* .
That is, is satisfiable if
there is an interpretation and assignment that satisfies it. A set
of formulas is satisfiable if there is an
interpretation *M* and a variable-assignment *s* on
*M* such that
*M*,*s* ,
for every formula
in
. If
is a set of sentences and
if *M* for each
sentence
in , then we say
that *M* is a *model of*
. So a
set of sentences is satisfiable if it has a model. Satisfiability is
the model-theoretic counterpart to consistency.

Notice that if and only if the set ,¬ is not satisfiable. It follows that if a set is not satisfiable, then if is any formula, . This is a model-theoretic counterpart to ex falso quodlibet (see Theorem 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 interpretationMand assignmentssuch thatM,sfor every member of . By the clause for negations, we cannot have bothM,sandM,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 interpretationMand an assignmentssuch thatM,s, for every formula in and it is not the case thatM,s. A fortiori,M,ssatisfies every member of , and so is satisfiable.

Even though the deductive systemTheorem 18. Soundness.For any formula and set of formulas, if_{D}, then .

Proof:We proceed by induction on the number of clauses used to establish . So letnbe a natural number, and assume that the theorem holds for any argument established as deductively valid with fewer thannsteps. And suppose that was established using exactlynsteps. If the last rule applied was (=I) then is a formula in the formt=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 and assignment 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 thatM,ssatisfies every member of . ThenM,ssatisfies every member of_{1}, and soM,ssatisfies . Similarly,M,ssatisfies every member of_{2}, and soM,ssatisfies . Thus, by the clause for "&" in the definition of satisfaction,M,ssatisfies . So . Suppose the last clause applied was (E). So we have_{1}vand_{2}, , where =_{1},_{2}, andvdoes not occur free in , nor in any member of_{2}. By the induction hypothesis, we have_{1}vand_{2}, . LetMbe an interpretation andsan assignment such thatM,ssatisfies every member of . ThenM,ssatisfies every member of_{1}, and soM,sv. So there is an assignmentsthat agrees withson every variable except possiblyvsuch thatM,s. We have thatM,ssatisfies every member of_{2}. Sincevdoes not occur free in any member of_{2}, andsagrees withson everything else, we have thatM,ssatisfies every member of_{2}, by Theorem 14. SoM,s. Sincevdoes not occur free in , andsagrees withson everything else, we have thatM,s, also by Theorem 14. So, in this case, . Notice the role of the restrictions on (E) here. The other 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 letMbe an interpretation andsan assignment such thatM,ssatisfies every member of . Assume that is inconsistent. Then there is a formula such that and ¬. By soundness (Theorem 18), and ¬. So we have thatM,sandM,s¬. But this is impossible, given the clause for negation in the definition of satisfaction.

A converse to Soundness (Theorem 18) is a straightforward corollary:Theorem 20. Completeness. Gödel [1930].Let be a set of formulas. If is consistent, then is satisfiable.

Proof:The proof of completeness is rather complex. We only sketch it here. Let be a consistent set of formulas of 1K=. Again, we assume for simplicity that the setKof non-logical terminology is either finite or countably infinite (although the theorem holds even ifKis uncountable). The task at hand is to find an interpretationMand a variable-assignmentsonM, such thatM,ssatisfies every member of . Consider the language obtained from 1K= by adding a denumerably infinite stock of new individual constantsc_{0},c_{1}, . . . We stipulate that the constants,c_{0},c_{1}, . . . , are all different from each other and none of them occur inK. We build an interpretation of the language from the language itself, using some of the constants as members of the domain of discourse. Let_{0},_{1}, . . . be an enumeration of the formulas of the expanded language, so that each formula occurs in the list eventually. Letxbe any variable, and define a sequence_{0},_{1}, . . . of sets of formulas (of the expanded language) by recursion as follows:_{0}= ; and_{n}_{+1}=_{n},(x_{n}_{n}(x|c_{i})), wherec_{i}is the first constant in the above list that does not occur in_{n}or in any member of_{n}. The underlying idea here is that ifx_{n}is true, thenc_{i}is to be one suchx. Let be the union of the sets_{n}.I sketch a proof that is consistent. Suppose that is inconsistent. By Theorem 9, there is a finite subset of that is inconsistent, and so one of the sets

_{m}is inconsistent. By hypothesis,_{0}= is consistent. Letnbe the smallest number such that_{n}is consistent, but_{n}_{+1}=_{n},(x_{n}_{n}(x|c_{i})) is inconsistent. By (¬I), we have that(1)_{n}¬(x_{n}_{n}(x|c_{i})).By

ex falso quodlibet(Theorem 10),_{n}, ¬x_{n},x_{n}_{n}(x|c_{i}). So by (I),_{n}, ¬x_{n}(x_{n}_{n}(x|c_{i})). From this and (1), we have_{n}¬¬x_{n}, by (¬I), and by (DNE) we have(2)By (As),_{n}x_{n}._{n},_{n}(x|c_{i}),x_{n}_{n}(x|c_{i}). So by (I),_{n},_{n}(x|c_{i}) (x_{n}_{n}(x|c_{i})). From this and (1), we have_{n}¬_{n}(x|c_{i}), by (¬I). Letvbe a variable that does not occur (free or bound) in_{n}or in any member of_{n}. By uniform substitution ofvforc_{i}, we can turn the derivation of_{n}¬_{n}(x|c_{i}) into_{n}¬_{n}(x|v). By (I), we have(3)By (As) we have {_{n}v¬_{n}(x|v).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 consistent set of sentences (of the expanded language) that contains . So, of course, contains . We define an interpretation

M, and a variable-assignmentsonM, such thatM,ssatisfies every member of .If we did not have a sign for identity in the language, we would let the domain of

Mbe the collection of new constants {c_{0},c_{1}, . . . }. But as it is, there may be a sentence in the formc_{i}=c_{j}, withij, in . If so, we cannot have bothc_{i}andc_{j}in the domain of the interpretation. So we define the domaindofMto be the set {c_{i}| there is noj<isuch thatc_{i}=c_{j}is in }. In other words, a constantc_{i}is in the domain ofMif does not declare it to be identical to an earlier constant in the list. Notice that for each new constantc_{i}, there is exactly onejisuch thatc_{j}is indand the sentencec_{i}=c_{j}is in .We now define the interpretation function

I. Letabe any constant in the expanded language. By (=I) and (I),xx=a, and soxx=a. By the construction of , there is a sentence in the form (xx=ac_{i}=a) in . We have thatc_{i}=ais in . As above, there is exactly onec_{j}indsuch thatc_{i}=c_{j}is in . LetI(a)=c_{j}. Notice that ifc_{i}is a constant in the domaind, thenI(c_{i})=c_{i}. That is eachc_{i}inddenotes itself.Let

Pbe a one-place predicate letter inK. LetI(P) be the set of constants {c_{i}|c_{i}is indand the formulaPcis in }. LetRbe a binary predicate letter inK. LetI(R) be the set of pairs of constants {<c_{i},c_{j}> |c_{i}is ind,c_{j}is ind, and the formulaRc_{i}c_{j}is in }. Three-place predicates, etc. are interpreted similarly. In effect,Iinterprets the non-logical terminology as they are in .The variable-assignment is similar. If

vis a variable, thens(v)=c_{i}, wherec_{i}is the first constant indsuch thatc_{i}=vis in .The final item in this proof is a tedious lemma that for every formula in the expanded language,

M,sif and only if is in . This proceeds by induction on the complexity of . The case where is atomic follows from the definitions ofM(i.e., the domaindand the interpretation functionI) and the variable-assignments. The other cases follow from the various clauses in the definition of satisfaction.Since , we have that

M,ssatisfies every member of . By Theorem 15, the restriction ofMto the original language 1K= andsalso satisfies every member of . Thus is satisfiable.

Theorem 21.For any formula and set of formulas, if , then_{D}.

Proof:Suppose that . Then there is no interpretationMand assignmentssuch thatM,ssatisfies every member of but does not satisfy . So the set ,¬ is not satisfiable. By Completeness (Theorem 20), ,¬ is inconsistent. So there 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:

Soundness and completeness together entail that an argument is deducible if and only if it is valid, and a set of formulas is consistent if and only if it is satisfiable. So we can go back and forth between model-theoretic and proof-theoretic notions, transferring properties of one to the other. Compactness holds in the model theory because all derivations use only a finite number of premises.Corollary 22. Compactness.A set of formulas is satisfiable if and only if every finite subset of is satisfiable.

Proof:IfM,ssatisfies every member of , thenM,ssatisfies every member of each finite subset of . For the converse, suppose that is not satisfiable. Then we show that some finite subset of is not satisfiable. By Completeness (Theorem 20), is inconsistent. By Theorem 9 (and Weakening), there is a finite subset such that is inconsistent. By Corollary 19, is not satisfiable.

Recall that in the proof of Completeness (Theorem 20), we made the
simplifying assumption that the set *K* of non-logical
constants is either finite or denumerably infinite. The
interpretation we produced was itself either finite or denumerably
infinite. Thus, we have the following:

In general, let be a satisfiable set of sentences of 1Corollary 23. Löwenheim-Skolem Theorem.Let be a satisfiable set of sentences of the language 1K=. If is either finite or denumerably infinite, then has a model whose domain is either finite or denumerably infinite.

There is a stronger version of Corollary 23. Let
*M*_{1}=<*d*_{1},*I*_{1}>
and
*M*_{2}=<*d*_{2},*I*_{2}>
be interpretations of the language
1*K*=. Define *M*_{1} to be
a *submodel* of *M*_{2} if
*d*_{1}
*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 letter in *K*, then for all *a*,*b*
in *d*_{1}, the pair <*a*,*b*>
is in *I*_{1}(*R*) if and only if
<*a*,*b*> is in
*I*_{2}(*R*). If we had included function
letters among the non-logical terminology, we would also require
that *d*_{1} be closed under their interpretations
in *M*_{2}. Notice that if *M*_{1} is
a submodel of *M*_{2}, then any variable-assignment
on *M*_{1} is also a variable-assignment on
*M*_{2}.

Say that two interpretations
*M*_{1}=<*d*_{1},*I*_{1}>,
*M*_{2}=<*d*_{2},*I*_{2}>
are *elementarily equivalent* if one of them is a submodel
of the other, and for any formula of the language and any
variable-assignment *s* on the submodel,
*M*_{1},*s*
if and only if
*M*_{2},*s*.
Notice that if two interpretations are elementarily equivalent, then
they satisfy the same sentences.

Theorem 25. Downward Löwenheim-Skolem Theorem.LetM= <d,I> be an interpretation of the language 1K=. Letd_{1}be any subset ofd, and let be the maximum of the size ofK, the size ofd_{1}, and denumerably infinite. Then there is a submodelM= <d,I> ofMsuch that (1)dis not larger than , and (2)MandMare elementarily equivalent. In particular, if the setKof non-logical terminology is either finite or denumerably infinite, then any interpretation has an elementarily equivalent submodel whose domain is either finite or denumerably infinite.

Proof:Like completeness, this proof is complex, and we rest content with a sketch. The downward Löwenheim-Skolem theorem invokes the axiom of choice, and indeed, is equivalent to the axiom of choice. So letCbe a choice function on the powerset ofd, so that for each non-empty subseted,C(e) is a member ofe. We stipulate that ifeis the empty set, thenC(e) isC(d).Let

sbe a variable-assignment onM, let be a formula of 1K=, and letvbe a variable. Define thev-witness ofover s, writtenw_{v}(,s), as follows: Letqbe the set of all elementscdsuch that there is a variable-assignmentsonMthat agrees withson every variable except possiblyv, such thatM,s, ands(v)=c. Thenw_{v}(,s) =C(q). Notice that ifM,sv, thenqis the set of elements of the domain that can go forvin . Indeed,M,svif and only ifqis non-empty. So ifM,sv, thenw_{v}(,s) (i.e.,C(q)) is a chosen element of the domain that can go forvin . In a sense, it is a "witness" that verifiesM,sv.If

eis a non-empty subset of the domaind, then define a variable-assignmentsto be ane-assignmentif for all variablesu,s(u) is ine. That is,sis ane-assignment ifsassigns an element ofeto each variable. Definesk(e), theSkolem-hullofe, to be the set:That is, the Skolem-Hull ofe{w_{v}(,s) | is a formula in 1K=,vis a variable, andsis ane-assignment}.eis the setetogether with everyv-witness of every formula over everye-assignment. Roughly, the idea is to start witheand then throw in enough elements to make each existentially quantified formula true. But we cannot rest content with the Skolem-hull, however. Once we throw the "witnesses" into the domain, we need to deal withsk(e) assignments. In effect, we need a set which is its own Skolem-hull, and also contains the given subsetd_{1}.We define a sequence of non-empty sets

e_{0},e_{1}, . . . as follows: if the given subsetd_{1}ofdis empty and there are no constants inK, then lete_{0}beC(d), the choice function applied to the entire domain; otherwise lete_{0}be the union ofd_{1}and the denotations underIof the constants inK. For each natural numbern,e_{n}_{+1}issk(e_{n}). Finally, letdbe the union of the setse_{n}, and letIbe the restriction ofItod. Our interpretation isM= <d,I>.Clearly,

d_{1}is a subset ofd, and soMis a submodel ofM. Let be the maximum of the size ofK, the size ofd_{1}, and denumerably infinite. A calculation reveals that the size ofdis at most , based on the fact that there are at most -many formulas, and thus, at most -many witnesses at each stage. Notice, incidentally, that this calculation relies on the fact that a denumerable union of sets of size at most is itself at most . This also relies on the axiom of choice.The final item is to show that

Mis elementarily equivalent toM: For every formula and every variable-assignmentsonM,M,sif and only ifM,s.We proceed by induction on the complexity of . If is atomic, then the definition of satisfaction entails the equivalence. So let be non-atomic, and assume that

M,sif and only ifM,s, for all assignmentssonMand all formulas less complex than . Letsbe any such assignment. If the main connective of is the negation sign or a binary connective, then the induction hypothesis entails thatM,sif and only ifM,s. The remaining cases are those in which begins with a quantifier, i.e., is eithervorv. Suppose thatM,sv. Then there is a variable-assignmentsthat agrees withsexcept possibly atvsuch thatM,s. By the induction hypothesis,M,sand soM,sv. The converse is a bit tricky, and amounts to showing that the Skolem-hull ofdisd. Assume thatM,sv. We are given thatsis a variable-assignment ond. Since there are only finitely many free-variables in , letnbe any natural number such that for all variablesuthat occur free in ,s(u) is ine_{n}. Lets_{1}be ane_{n}-assignment that agrees withson all of the free variables in . Then, by Theorem 14,M,s_{1}v. Letcbew_{v}(,s_{1}), thev-witness ofovers_{1}. Notice thatcis ine_{n+1}and socis ind. Lets_{1}agree withs_{1}, except possibly atv, and lets_{1}(v)=c. Sos_{1}is a variable-assignment onM. By the definition of the witness function,M,s_{1}. By the induction hypothesis,M,s_{1}, and soM,s_{1}v. By Theorem 14,M,sv. The final case, where has the formv, is similar.

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

Theorem 26. Upward Löwenheim-Skolem Theorem.Let be any set of formulas of1K=, such that for each natural numbern, there is an interpretationM_{n}= <d_{n},I_{n}>, and an assignments_{n}onM_{n}, such thatd_{n}has at leastnelements, andM_{n},s_{n}satisfies every member of . In other words, is satisfiable and there is no finite upper bound to the size of the interpretations that satisfy every member of . Then for any infinite cardinal , there is an interpretationM=<d,I> and assignmentsonM, such that the size ofdisat leastandM,ssatisfies every member of . In particular, if is a set of sentences, then it has arbitrarily large models.

Proof:Add a collection of new constants {c_{}| <}, of size , to the language, so that ifcis a constant inK, thenc_{}is different fromc, and if <<, thenc_{}is a different constant thanc_{}. Consider the set of formulas consisting of together with the set {¬c_{}=c_{}| }. That is, consists of together with statements to the effect that any two different new constants denote different objects. Let be any finite subset of , and letmbe the number of new constants that occur in . Then expand the interpretationM_{m}to an interpretationM_{m}of the new language, by interpreting each of the new constants in as a different member of the domaind_{m}. By hypothesis, there are enough members ofd_{m}to do this. One can interpret the other new constants at will. SoM_{m}is a restriction ofM_{m}. By hypothesis (and Theorem 15),M_{m},s_{m}satisfies every member of . AlsoM_{m},s_{m}satisfies the members of {¬c_{}=c_{}| } that are in . SoM_{m},s_{m}satisfies every member of . By compactness, there is an interpretationM= <d,I> and an assignmentsonMsuch thatM,ssatisfies every member of . Since contains every member of {¬c_{}=c_{}| }, the domaindofMmust be of size at least , since each of the new constants must have a different denotation. By Theorem 15, the restriction ofMto the original language 1K= satisfies every member of , with the variable-assignments.

The proofs of the downward and upward Löwenheim-Skolem
theorems can be combined to show that for any satisfiable set
of sentences, if there is no finite bound on
the models of
, then for any infinite cardinal
,
there is a model of
whose domain has size
*exactly*
. Moreover, if *M* is any interpretation
whose domain is infinite, then for any infinite cardinal
,
there is an interpretation
*M* whose domain has
size exactly
such that
*M* and
*M* are elementarily equivalent.

These results indicate a weakness in the expressive resources of
first-order languages like 1*K*=. No
satisfiable set of sentences can guarantee that its models are all
denumerably infinite, nor can any satisfiable set of sentences
guarantee that its models are uncountable. So in a sense, first-order
languages cannot express the notion of "denumerably infinite", at
least not in the model theory.

Let *A* be any set of sentences in a first-order language
1*K*=, where *K* includes
terminology for arithmetic, and assume that every member of
*A* is true of the natural numbers. We can even let *A*
be the set of all sentences in
1*K*= that are true of the natural
numbers. Then *A* has uncountable models, indeed models of
any infinite cardinality. Such interpretations are sometimes
called *unintended*, or *non-standard* models of
arithmetic. Let *B* be any set of first-order sentences that
are true of the real numbers, and let *C* be any first-order
axiomatization of set theory. Then if *B* and *C* are
satisfiable (in infinite interpretations), then each of them has
denumerably infinite models. That is, any first-order, satisfiable
set theory or theory of the real numbers, has (unintended) models
the size of the natural numbers. This is despite the fact that a
sentence (seemingly) stating that the universe is uncountable is
provable in most set-theories. This situation, known as the
*Skolem paradox*, has generated much discussion, but we must
refer the reader elsewhere for a sample of it.

- Anderson, A. and N. Belnap [1975],
*Entailment: The logic of relevance and necessity I*, Princeton: Princeton University Press. - Anderson, A. and N. Belnap, and M. Dunn [1992],
*Entailment: The logic of relevance and necessity II*, Princeton: Princeton University Press. - Corcoran, J. [1973], "Gaps between logical theory and
mathematical practice",
*The methodological unity of science*, ed. by M. Bunge, Dordrecht: Holland, D. Reidel, 23-50. - Church, A. [1956],
*Introduction to mathematical logic*, Princeton: Princeton University Press. Classic textbook. - Davidson, D. [1984],
*Inquiries into truth and interpretation*, Oxford: Clarendon Press. - Dummett, M. [1977],
*Elements of intuitionism*, Oxford: Oxford University Press. - Gödel, K. [1930], "Die Vollständigkeit der Axiome des
logischen Funktionenkalkuls",
*Montatshefte für Mathematik und Physik 37*, 349-360; translated as "The completeness of the axioms of the functional calculus of logic", in van Heijenoort [1967], 582-591. - Lycan, W. [1984],
*Logical form in natural language*, Cambridge, Massachusetts: The MIT Press. - Montague, R. [1974],
*Formal philosophy*, ed. by R. Thomason, New Haven: Yale University Press. - Quine, W. V. O. [1960],
*Word and object*, Cambridge, Massachusetts: The MIT Press. - Quine, W. V. O. [1986],
*Philosophy of logic*, second edition, Englewood Cliffs, New Jersey: Prentice-Hall. - Shapiro, S. [1998], "Logical consequence: models and modality",
in
*The philosophy of mathematics today*, edited by M. Schirn, Oxford: Oxford University Press, 131-156. - Tennant, N. [1987], "Conventional necessity and the contingency
of deduction",
*Dialectica 41*, 79-95.

- Boolos, G., and R. Jeffrey [1989],
*Computability and logic*, third edition, Cambridge, England: Cambridge University Press. Textbook on mathematical logic. - Enderton, H. [1972],
*A mathematical introduction to logic*, New York: Academic Press. Textbook in mathematical logic. - Forbes, G. [1994],
*Modern Logic*, Oxford: Oxford University Press. Elementary textbook. - Mendelson, E. [1987],
*Introduction to mathematical logic*, third edition, Princeton: van Nostrand. Textbook in mathematical logic. - Shapiro, S. [1996],
*The limits of logic: Second-order logic and the Skolem paradox*,*The international research library of philosophy*, Dartmouth Publishing Company, 1996. An anthology containing many of the significant later papers on the Skolem paradox. - Van Heijenoort, J [1967],
*From Frege to Gödel*, Cambridge, Massachusetts: Harvard University Press. An anthology containing many of the major historical papers on mathematical logic in the early decades of the twentieth century.

*First published: September 15, 2000*

*Content last modified: September 15, 2000*