A Metalogical Primer

Jason Turner

Spring 2010

Metalogic is the study of logic. When you learn a logic, you learn a logical
system: a system of rules for taking sentences of a given language (usually, a
symbolic language) and proving other sentences using those rules.
After you’ve messed about with logical systems for a bit, you can start asking
questions about those systems. Like: can I construct a proof for every valid
argument, or only for some of them? Or: are there any valid arguments with
infinitely many premises, where each of the premises is needed? (That is, where
if you took any finite subset of the premises, the conclusion wouldn’t follow
from it?) These questions are the questions of metalogic.

1 Notation
When we do proofs, we use expressions (of our formal, technical language).
But when we do metalogic, we want to talk about expressions of this language,
and the way expressions of this language are related to each other. To avoid
confusion — to make it clear whether we’re using a sentence, or talking about
it — we’ll use a certain kind of notation.
First of all, if we want to talk about particular expressions, we use quotation-
names to talk about them. For instance, if I want to say that the third letter of
the alphabet is curved, I would say that ‘C’ is curved. See how I used the quotes
there? This is important. In the following sentences,

(1) Leeds is in the middle of the dictionary.

(2) ‘Leeds’ is in the middle of the dictionary.

(2) is true — ‘Leeds’ is a word, and since it begins with ‘L’, it’s in the middle of
the dictionary. But Leeds is not a word — it’s a city — and cities can’t fit in the
middle of dictionaries.
So far, so good. But what if we don’t want to talk about a particular word or
sentence, but a whole bunch of words or sentences of thus-and-so a type? That
is, what if we want to quantify over expressions?
In this case, to avoid confusion, we adopt a convention. Different authors
will use different conventions. The convention I’ll use for this document is
Quine’s corner-quote convention. In this convention, we use greek characters as
‘metalinguistic’ variables — variables that go as proxy for expressions. Using
this convention we can say, for instance, that every word φ that begins with ‘L’
is closer to the middle of the dictionary than every word χ that begins with ’B’.
Sometimes, however, we want to talk about a whole bunch of complex ex-
pressions that all have the same form. For instance, we might want to talk about
all sentences that have the following form: their first part is a sentence, and then

1
the word ‘and’ occurs, and then their final part is another sentence. Talking like
this is a bit of a mouthful. Quine’s corner-quote convention lets us instead use
corner-quotes. In this convention, I can say something about all sentences of the
form pφ and ψq. The expression

pφ and ψq

should be literally read as

the result of writing φ and then leaving a space and then writing
‘and’ and then leaving another space and then writing ψq

But again, that’s a mouthful to say, so it’s quicker and easier to use the corner-
quote notation instead.

2 Example: Propositional Logic

To fix ideas, let’s look at a special case: propositional logic, which you learned
about in your introduction to logic class.
Propositional logic has three components: a language, a deduction system,
and model theory. The first two components are what you need to do logic —
they’re what the introduction to logic class is all about. The model theory is
something more abstract that we use when we do metalogic — it’s something
we use to reason about the system. We’ll talk about the significance of model
theories more as we go along.

2.1 The Language

Let’s begin with the language. It consists of two bits: a syntax, and a semantics.
The syntax is a specification of exactly what symbols are part of the lan-
guage, which ones are sentences, and so on. The semantics is a specification
of what the symbols, and sentences made out of them, mean, and how the
meanings (and truth-conditions!) of complex sentences are built up out of the
meanings (and truth-conditions) of simpler expressions.
The syntax of propositional language has two parts: a grammar, which tells
us what symbols count as simple expressions of the language, and a set of
formulation rules, which tell us which combinations of symbols count as sen-
tences.
First, the grammar. The language of propositional logic has:

• Atomic propositions: capital letters ‘A’, ‘B’, . . . , with or without

subscripts.
• Sentential Connectives: ‘∼’, ‘∨’, ‘&’, ‘⊃’, ‘≡’.
• Brackets: ‘(’, ‘)’.

2
 Second, the formulation rules. These form a recursive definition of ‘sentence’:
they tell us what the basic sentences are, and how to build up more complex
sentences from that. The rules:

• All atomic propositions are sentences.

• If φ and ψ are sentences, then so are p∼φq, p(φ ∨ ψ)q, p(φ & ψ)q,
p(φ ⊃ ψ)q, and p(φ ≡ ψ)q.
• Nothing else is a sentence.

Notice that, technically speaking, ‘A & B’ is not a sentence, but ‘(A & B)’ is.
There are good reasons for this (they have to do with making sure the defini-
tions don’t screw up scope distinctions), but they create clutter because every
compound sentence has an outermost pair of brackets. So we adopt the conven-
tion of not writing the outermost pair of brackets, while secretly acknowledging
that, strictly speaking, this is a mistake.
What about the semantics — the meaning of these expressions? Well, we tend
to be silent about just what the atomic propositions mean, because it turns out it
doesn’t matter what they mean to the study of logic. All we demand is that they
have meanings which can be either true or false. But we do specify meanings
for the sentential connectives, as follows:
Connective Meaning
∼ not
∨ or
& and
⊃ if,. . . then
≡ if and only if

2.2 The Proof Procedure

A proof procedure is a method for taking some sentences of the language of
propositional logic and ‘proving’ other sentences. It is a purely syntactic method,
in the following sense: whether or not you can construct a proof depends only
on the ‘shapes’ of the sentences involved. You don’t have to know what the
sentences mean.
That’s not to say that the meanings of the sentences are irrelevant. The reason
we choose a certain procedure for our proof procedure depends heavily on what
the expressions in our language mean. It’s just that, once chosen, the procedure
itself doesn’t make any further appeal to the meanings of the expressions.
Here’s a way to see the point. In propositional logic, you can construct a
proof from ‘A & B’ to ‘B’. The method you would use to do this — the proof pro-
cedure you would employ — would depend only on the fact that your premise
had a certain shape — that it had the shape pφ & ψq. You could teach a computer
to use the procedure, and it would also be able to prove ‘B’ from ‘A & B’, and it
would be able to do this even if it had no idea what ‘&’ meant.

3
 However, the reason we use that procedure and call it a ‘proof’ procedure is
because we know that ‘&’ means ‘and’. If ‘&’ had meant ‘or’ instead, although
this procedure would still exist, we wouldn’t want to use it or call things made
from it ‘proofs’. And we wouldn’t teach it to computers, and so on.
There are, in general, three kinds of proof procedures that get used: natural
deduction, semantic tableaux (or ‘truth-trees’), and axiomatic systems. In your
introduction to logic course, you probably learned one of the first two. In the
first sort, you have a whole lot of different rules, including ones involving mak-
ing and discharging assumptions, that let you ‘infer’ one sentence from some
others. In the second sort of procedure, you have rules for constructing trees
from an initial list of sentences, and then ‘closing off’ ones with contradictions
on them.
But we will focus on the third sort here, because it ends up being more useful
for doing metalogic. An axiom system consists of

i) A specification of axioms, which are just special sentences of the

language.
ii) An inference rule, which tells you how to infer which sentences
from which.

A proof from φ1 , . . . , φn in an axiom system is just a list of sentences, where each

sentence is either an axiom, one of φ1 , . . . , φn , or can be gotten by the inference
rule from sentences higher up in the list.
For example, in propositional logic, the axiom system has one inference rule
— modus ponens — and a whole lot of axioms. What axioms? Every sentence
that has the following shape counts as an axiom:

(A1) φ ⊃ (ψ ⊃ φ)
(A2) (φ ⊃ (ψ ⊃ χ)) ⊃ ((φ ⊃ ψ) ⊃ (φ ⊃ χ))
(A3) (∼φ ⊃ ∼ψ) ⊃ ((∼φ ⊃ ψ) ⊃ φ)
(D≡) (φ ≡ ψ) ⊃ ∼((φ ⊃ ψ) ⊃ ∼(ψ ⊃ φ))
(D&) (φ & χ) ≡ ∼(φ ⊃ ∼χ)
(D∨) (φ ∨ χ) ≡ (∼φ ⊃ χ)

Notice that what gets put in for φ, ψ, and χ in the axioms can be simple or
complex:

A ⊃ (B ⊃ A), and
(P ≡ ∼R) ⊃ (((∼B ∨ C) ⊃ ∼R) ⊃ (P ≡ ∼R))
are equally good instances of (A1), and are equally well axioms. The difference
is that, in the second one, ‘P ≡ ∼R’ is put in for φ (note how I remembered to
add back the outermost brackets!) and ‘(∼B ∨ C) ⊃ ∼R’ is put in for ψ.
Let’s work through a simple axiomatic proof: we want to prove, from the
premise ‘∼P ⊃ P’, the conclusion P. We begin our list with the premise:

4
 (1) ∼P ⊃ P

Now, putting ‘∼P’ in for φ and ‘∼P ⊃ ∼P’ in for ψ, we get an instance of (A1),
which we’ll make the second entry on our list:

(2) ∼P ⊃ ((∼P ⊃ ∼P) ⊃ ∼P)

This time, we’ll substitute ‘∼P’ in for both φ and χ in (A2), along with ‘∼P ⊃
∼P’ for ψ:
(3) (∼P ⊃ ((∼P ⊃ ∼P) ⊃ ∼P)) ⊃
((∼P ⊃ (∼P ⊃ ∼P)) ⊃ (∼P ⊃ ∼P))
Since the antecedent of (3) just is sentence (2), we can use modus ponens to get:

(4) (∼P ⊃ (∼P ⊃ ∼P)) ⊃ (∼P ⊃ ∼P)

Now we substitute ‘∼P’ for both φ and ψ into (A1) to get a different axiom
instance:

(5) ∼P ⊃ (∼P ⊃ ∼P)

But this is the antecedent of (4), so by modus ponens we get

(6) ∼P ⊃ ∼P

Next, we substitute ‘P’ for both φ and ψ in (A3), to get:

(7) (∼P ⊃ ∼P) ⊃ ((∼P ⊃ P) ⊃ P)

which we then combine with (6) by modus ponens to conclude

(8) (∼P ⊃ P) ⊃ P

Now we get

(9) P

by modus ponens with (8) and (1).

Officially, the proof would be written:

(1) ∼P ⊃ P Premise
(2) ∼P ⊃ ((∼P ⊃ ∼P) ⊃ ∼P) A1
(3) (∼P ⊃ ((∼P ⊃ ∼P) ⊃ ∼P)) ⊃
((∼P ⊃ (∼P ⊃ ∼P)) ⊃ (∼P ⊃ ∼P)) A2
(4) (∼P ⊃ (∼P ⊃ ∼P)) ⊃ (∼P ⊃ ∼P) MP: 2, 3
(5) ∼P ⊃ (∼P ⊃ ∼P) A1
(6) ∼P ⊃ ∼P MP: 4, 5
(7) (∼P ⊃ ∼P) ⊃ ((∼P ⊃ P) ⊃ P) A3

5
 (8) (∼P ⊃ P) ⊃ P MP: 6, 7
(9) P MP: 1, 8

As you can see, this a list where every line is either (i) a premise (line 1), (ii)
an instance of an axiom (lines 2, 3, 5, and 7), or (iii) licensed by modus ponens
from earlier lines (4, 6, 8, and 9).
Proving the same result from the same premises would have been a lot easier
in either natural deduction or semantic tableaux systems. In general, proofs
are more difficult to construct in an axiomatic system than in either natural
deduction or semantic tablueaux systems.
So why do we use them? Because, although actually doing logic is harder
in them, reasoning about logic is easier. And, as it turns out, whatever can be
proven in an axiomatic system can be proven in a natural deduction or tableaux
system, or vice versa. So we can do our metalogic focusing (mainly) on axiomatic
systems, secure in the knowledge that our results will apply equally well to
other types of proof procedures.
If ∆ is a set of sentences, and φ is a sentence, then we say that ∆ proves φ, or
∆ φ, if and only if there is a (possible) proof of φ with only sentences in ∆ as
premises. If ∅ φ — that is, if φ can be proved with a proof where every line is
either an axiom or comes in by modus ponens — then we call φ a theorem, and
write φ.

2.3 Model Theory

When doing formal logic, we provide models — formal (usually set-theoretic)
representations intended to, in some sense, capture the meaning, or logical
structure, of the sentences in question.
In propositional logic, a model is a truth-value assignment — a function V
from atomic propositions to truth-values. We generally use the numbers 0 and
1 to model truth-values: 0 represents truth, and 1 represents falsehood. If φ is
an atomic sentence, and V a model, then V (φ) will be either 0 or 1.
If we have a model V, we can define truth on V recursively, as follows:

i) If φ is an atomic sentence, then φ is true on V iff V (φ) = 1.

ii) If φ is a negation of some sentence ψ — that is, if φ = p∼ψq —
then φ is true on V iff ψ is not true on V.
iii) If φ is a conjunction of sentences ψ and χ — that is, if φ =
pψ & χq — then φ is true on V iff both ψ and χ are.
iv) If φ is a disjunction of sentences ψ and χ — that is, if φ = pψ ∨ χq
— then φ is true on V iff either ψ or χ is.
v) If φ is a conditional with antecedent ψ and consequent χ — that
is, if φ = pψ ⊃ χq — then φ is true on V iff either ψ is not true
on V or χ is true on V.

6
 vi) If φ is a biconditional of sentences ψ and χ — that is, if φ =
pψ ≡ χq — then φ is true on V iff ψ and χ are either both true
on V or both not true on V.

Let’s look at an example of how this works. Consider the sentence

(∗) ∼A ⊃ (B ∨ A)

Let V be a truth-value assignment where V (A) = 0 and V (B) = 1. Is (∗) true

on V, or false on V?
Well, (∗) is of the form pψ ⊃ χq, so, by clause (v), it is true on V iff either its
antecedent is false on V or its consequent is true on V.1
Let’s start with its antecedent, ‘∼A’. Is this sentence true, or false, on V?
Well, it’s a negation, so by clause (ii), it is true on V iff the sentence it’s a
negation of — ‘A’ — is not true on V. By clause (i), ‘A’ is true on V if V (A) = 1,
and false on V otherwise. But since V (A) = 0, ‘A’ is false on V, and so ‘∼A’ is
true on V.
So (∗)’s antecedent is true on V. If its consequent is also false on V, (∗) will
be false on V; otherwise, it will be true on V. So let’s look at the consequent
now.
The consequent is a disjunction, so by clause (iv), it is true on V if and only
if at least one of its disjuncts is true on V. We already know, from above, that
one of its disjuncts — ‘A’ — is not true on V. What of the other? Well, by clause
(i), ‘B’ is true on V iff V (B) = 1. But it does, so ‘B’ is true on V, so ‘A ∨ B’ is
true on V.
Since its consequent is true on V, (∗) is true on V. We’ve thus figured out
the truth-value of (∗) on V.
You might remember truth-tables from your first year logic class, and won-
der how they apply to models. Here, for instance, is the truth-table for (∗):

A B ∼A ⊃ (B ∨ A)
T T T
T F T
F T T
F F F

Each row on the table represents a different truth-value assignment — that is, a
different model. Or, more accurately, each row represents a class of truth-value
assignments. The first row, for instance, represents all the assignments V where
V (A) = 1 and V (B) = 1; the second represents all V where V (A) = 1 and
V (B) = 0; and so on.
The entries under each sentence tell us whether that sentence is true or false
on the model (or, more appropriately, on all the models) associated with the
given rows. For instance, this truth-table tells us that, on all models V where
1 By ‘false on V’, I just mean ‘not true on V’.

7
V (A) = 0 and V (B) = 0, the sentence (∗) is false, and that on all other models,
(∗) is true. Truth-tables are thus an easy way for verifying facts about all mod-
els. Something like this might have been emphasized in your introduction to
logic course. What probably wasn’t emphasized was that the truth-table method
works because truth-on-a-model is defined via clauses (i)–(vi) above.
Finally, some definitions. What we mainly want to define is model-theoretic
entailment: the relation that some sentences hold to another sentence just in
case the first can’t be true on a model without the second also being true on that
model. We can define it ‘officially’ as follows. First, if ∆ is a set of sentences,
say that ∆ is true on a model iff all of its members are true on that model. Then
we say that ∆ entails φ if and only if every model V on which ∆ is true is
also one on which φ is true. We write this ∆ φ. If ∅ φ, we say that φ is a
model-theoretic validity.

2.4 Soundness and Completeness

We now have both a deduction system and a model theory for propositional
logic. That is, we have a way of checking whether a sentence is a proof-theoretic
consequence of some others (whether ∆ ψ), and we have a way of checking
whether it is a model-theoretic consequence of the others (∆ ψ).
One question we might want to ask is this: do these two come apart? Or
does model-theoretic consequence always go along with provability, and vice
versa? That is, is the following true?
∆ φ iff ∆ φ
Since this is an ‘if and only if’ claim, we can really break it up into two parts.
First:
If we can prove φ from the sentences in ∆, does this mean that φ is a
model-theoretic consequence of ∆? That is, do we know that

If ∆ φ, then ∆ φ

If the system has this property, it is said to be sound — it tells us

that we can never use sentences that are true (on a model) to prove a
further sentence which is not true (on that model).
And second:
If φ is a model-theoretic consequence of ∆, does this mean that we
can use the sentences in ∆ to prove φ? That is, do we know that

If ∆ φ, then ∆ φ

If the system has this property, it is said to be complete — it tells us

that there are no cases where a sentence is a model-theoretic conse-
quence of some others, but we can’t prove the sentence from those
others.

8
 As it turns out, the propositional calculus — the system of propositional
logic we have been looking at — is both sound and complete.

2.4.1 Soundness
First, here’s how we prove soundness. Suppose ∆ ψ. What we want to show
is that, ∆ φ. But to say that ∆ φ is just to say that, for every model M, if all
the sentences in ∆ are true on M, then φ is true on M, too.
So what we do is we begin by assuming two things:

(i) That ∆ φ, and

(ii) That all of the sentences of ∆ are true on some model M.

What we need to show is that φ is also true on M. Then, since M is a totally

arbitrarily picked model, it will follow that for any model, if ∆ are all true on it,
so is φ — that is, it will follow that ∆ φ. And, since ∆ and φ were an arbitrarily
picked set and sentence, it will follow that for any set ∆ and model φ, ∆ φ.
But that’s to get a bit ahead of ourselves, because we still haven’t shown that
φ is true on M. But we can, and here’s how we do it.
First, since we assumed (i) that ∆ φ, we know that there is a proof of φ
from ∆. That is, there’s a sequence of sentences:

ψ1
ψ2
..
.
ψn

where each sentence is either (1) a member of ∆, (2) an instance of an axiom, or

(3) got into the proof through modus ponens. What we’ll do is show that every
single line of this proof is true on M. Since the last line — ψn — just is φ, it will
follow that φ is also true on M.
We do it using a method known as mathematical induction: we show first
that the very first member of the sequence has the property we care about (in
this case, being true on M), and we then show that, for any member of the
sequence, if all the items that come before it have the property, then it does,
too. Then we know that having of the property ‘runs up’ the sequence. Because
the first one has the property, all the ones before the second have it, and so the
second does, too. And because the first and second have it, all the ones before
the third have it, and so the third has it to. . . and so on.
First, we need to show that ψ1 is true on M. Well, since it’s part of the proof,
we can ask how it got into the proof. It was either (1) a member of ∆, (2) an
instance of an axiom, or (3) it got in by modus ponens. But modus ponens requires
that it had some other lines coming before (to use as premises), so the first line
of the proof couldn’t have gotten there by modus ponens. So we can just focus
on options (1) and (2).

9
 But remember that we are assuming that all the members of ∆ are true on M
(assumption (ii)), so if it got in that way, we know it’s true on M.
But what if ψ1 is an axiom? Well, here’s where some of the important bits
come in. We want to show that, if ψ1 is an axiom, it is true on M. But we don’t
know which axiom it is, and we don’t know which model M is, either. So what
we need to show is that all axioms are true on all models. If that’s the case, then
of course ψ1 is true on M — if all axioms are true on all models, then of course
this axiom is true on this model.
How do we do this? Well, a sentence is true on all models if and only if it
is a model-theoretic validity. And it’s a model-theoretic validity if and only if
it shows up as ‘T’ on every line of its truth-table. So we can check each axiom
schema to see if it will have ‘T’s on every line of its truth-table. For instance, the
first axiom schema comes to:
φ ψ φ ⊃ (ψ ⊃ φ)
T T T T
T F T T
F T T F
F F T T
So any instance of the first axiom schema is a model-theoretic validity, and so
is true on all models. You can use truth-tables to check that the same holds for
the other axiom schemas; I won’t do that here. But then all axioms are true on
all models, so — if ψ1 is an axiom, then ψ1 is true on all models too, and so is
true on M.
So we know that ψ1 is true on M. Now we need to show that, for any sen-
tence ψi in the sequence, if all the sentences that come before it in the sequence
are true on M, then it is, too. So suppose that all the sentences that come before
ψi are true on M. Is ψi also true on M?
Well, as above, ψi either got in the sequence by (1) being a member of ∆, or
by (2) being an axiom, or by (3) modus ponens. We’ve already seen why it will
be true on M if it got in in by (1) or (2); that reasoning still applies. So we only
need to make sure that it will be true on M if it got in by modus ponens.
So: assume that all the sentences before ψi are true on M, and ψi got in by
modus ponens. Then there must be some sentence ψj such that the sentences
ψj
ψj ⊃ ψi
are both in the sequence somewhere before ψi . So they must both be true on M.
But by our definition of truth-on-M, if pψj ⊃ ψi q is true on M, then either ψj is
false on M or φi is true on M. But we know that φj is not false on M — it’s true
on M — so we know that ψi must be true on M, by our definition of truth on a
model.
But this completes our proof: We now know that every sentence of the proof,
no matter how it got into the proof, is true on M, which means that φ — the
final sentence of the proof — is true on M, too.

10
2.4.2 Completeness
Completeness:
If ∆ φ, then ∆ φ
is thought harder to prove than soundness. What we do is to focus not on
completeness as it’s usually stated, but on its contrapositive:

If ∆ 6 φ, then ∆ 6 φ

Here’s how we do it. Say that a set of sentences Γ is consistent if you cannot
use it to prove a contradiction — that is, if Γ 6 φ & ∼φ. Then we prove
completeness by proving the following three lemmas:
Lemma 1: If ∆ 6 φ, then ∆ ∪ {∼φ} is consistent.

Lemma 2: If ∆ ∪ {∼φ} is consistent, then it has a model. (That is, there is a

model where all its sentences are true.)

Lemma 3: If ∆ ∪ {∼φ} has a model, then ∆ 6 φ.

The third lemma follows from the definition of ‘ ’: if ∆ ∪ {∼φ} has a model,
then there is at least one model where all the sentences of ∆ and also ∼φ are
true. But since ∼φ is true on this model iff φ is not true on this model, there is
at least one model where all the sentences of ∆ are true but φ is not — which is
just to say that ∆ 6 φ.
The first lemma is not quite as straightforward. I’m not going to prove it
here, but just give you the general idea of why it’s true. Te contrapositive of
lemma 1 says that, if ∆ ∪ {∼φ} is inconsistent, then ∆ φ. In other words, it
says that if you can prove a contradiction from ∆ combined with ∼φ, then ∆
by itself proves that φ. This is just a statement of the proceedure of ‘proof by
contradiction’ or ‘reductio ad absurdum’ whereby you assume the opposite of
what you want to show, derive a contradiction, and conclude that the thing you
wanted to show is right all along. A proof of lemma 1 would be a proof that
our axiom system guarantees proof by contradiction. It does, but I won’t prove
that here.
Lemma 2 is the most interesting; it says that every consistent set has a model.
I won’t prove this either, but I’ll give you the general idea. It’s this. Call a set of
sentences maximally consistent if and only if (i) it’s maximal, and (ii) any set you
get by adding another sentence to it would be inconsistent. Here’s a fact (which
we would need to prove if we were doing this properly): every consistent set is
a subset of some maximally consistent set.
So: if ∆ ∪ {∼φ} is consistent, then there is some maximally consistent set S
that it is a subset of. What we need to show is that S has a model. If it does, then
— since all the members of ∆ ∪ {∼φ} are also members of S — then ∆ ∪ {∼φ}
also has a model.
To show that S has a model, we essentially construct a model of it. What we
do is notice that, since S is maximal, it contains all of the atomic sentences that

11
it can. That is, if any atomic sentence is not in S, then that atomic sentence is
inconsistent with the members of S.
So let’s let M be a model where, for any atomic sentence χ, M(χ) = 1 if and
only if χ ∈ S. Now we need to show that, if ψ ∈ S, then ψ is true on M. We
also do this by a mathematical induction, this time an induction on how many
connectives ψ has in it.
More precisely, we show that, for all sentences ψ, ψ ∈ S iff ψ is true on M.
We start by showing that this holds for cases where ψ has zero connectives —
that is, where ψ is atomic. (This should be easy — it just comes out of how we
constructed M from S.) Then we show that, if all sentences shorter that ψ have
this property, then ψ does to. The proof starts by noticing that ψ will have the
form ψi Cψ2 for some connective C. And ψ1 and ψ2 will be true on M iff they
are members of S. So now all we need to show is that ψ is true on M iff it is a
member of S, too.
We do this by going case-by-case through all the connectives that C might
be. I’ll just do one, to show you how it goes.
Suppose that C is the conjunction connective, ‘&’. We know that ψ1 ∈ S iff
ψ1 is true on M, and same for ψ2 .
Suppose first (for reductio) that ψ ∈ S but ψ is not true on M. Since ψ is a
conjunction of ψ1 and ψ2 , it is consistent with both of these; since it’s consistent
with both of these, and is in S, then both ψ1 and ψ2 must be in S, too. But if
they’re both in S, since they have the property we care about, they must both be
true on M — in which case ψ will be true on M, too. Contradition.
Suppose second (for reductio) that ψ < S but ψ is true on M. Since ψ is true
on M, and is the conjunction of ψ1 and ψ2 , both of these must be true on M,
too. But if they’re both true on M, then since they have the property we care
about, they must both be in S. But ψ1 and ψ2 are clearly consistent with their
conjunction, so, since S is maximal, their conjunction, which is ψ, must be in S,
too. Contradiction.
We’ve looked at the only two ways ψ could fail to have the property; since
they both lead to contradiction, ψ must have the property after all.

12