Class Notes
(808,046)

United States
(312,889)

Philosophy
(46)

2250
(23)

James Hildebrand
(23)

Lecture

# N09Compactness - Compactness of SL.pdf

Unlock Document

Buffalo State College

Philosophy

2250

James Hildebrand

Spring

Description

THE COMPACTNESS OF SL
The language SL has a surprising feature: it is “compact.” A (possibly infinite) set, Γ, of
sentences of SL is t-f inconsistent if and only if at least one finite subset of Γ is t-f inconsistent.
Half of this result is not surprising. If a finite subset, Δ, of a set, Γ, is t-f inconsistent then there is
no truth value assignment on which every sentence in Δ is true. Adding more sentences to Δ to
create the infinite set, Γ, is not going to change this fact. There is still going to be no truth value
assignment that makes all the sentences in Γ true because there is already no truth value
assignment that makes just some of them (those in Δ) true.
But it is rather surprising that the converse should be true as well: that if Γ is t-f inconsistent then
at least one finite subset of Γ must be t-f inconsistent. There is no problem seeing why that
should be the case if Γ is itself finite. Since every set is a subset of itself, if Γ is t-f inconsistent
then it can be the finite subset of itself that is t-f inconsistent. But what is surprising is that if Γ
has infinitely many members it should need to have a finite subset, one containing fewer
members than it itself contains, that is already t-f inconsistent. In general, this is not true.
Consider the following infinite set (thanks to Wayne Myrvold for this example):
Γ: {There are only finitely many Tim Horton’s in Canada,
There is at least one Tim Horton’s in Canada,
There are at least two Tim Horton’s in Canada,
There are at least three Tim Horton’s in Canada,
…}
(The ellipses of course indicate that there are infinitely more sentences in the set, saying that
there are at least four, at least five, at least six, and — importantly — so on to infinity. That’s
what makes the set inconsistent.)
Any finite subset of this infinite set is logically consistent. But the entire set is logically
inconsistent.
Interestingly, though this set is logically inconsistent, it is not truth functionally inconsistent.
(The set gets translated into SL as an infinite list of distinct atomic sentences, and since there is
a truth value assignment that assigns a T to every atomic sentence of SL, any such set must be
t-f consistent.) And in fact, though compactness is true of infinite sets of sentences of SL, it is
not true of all sets of sentences whatsoever. It fails for sentences in more complex logics than
SL (or, for that matter, more complex than the first-order predicate lo
gic we will study for most of
next term — the failure only emerges when we move up to consider second order logic).
The fact that compactness holds of first-order logics like SL means that any valid argument in
first order logic need have only finitely many premises. Recall that the argument from a set of
premises, Γ, to a conclusion, P, is deductively valid if and only if Γ ∪ {~P} is logically
inconsistent. According to compactness, if this larger set, Γ ∪ {~P} is an infinite set of
sentences of first-order logic, it must have a finite subset that is already inconsistent in first
order logic. So any conclusion that follows from a set of infinitely many premises, Γ, must
already follow from just a finite subset of those premises. This underwrites what would
otherwise be the arbitrary stipulation that a sentence, P, is derivable from Γ if and only if P is
derivable from a finite subset of the sentences in Γ. The surprising part of the compactness metatheorem — that if Γ is t-f inconsistent it must have a
finite subset that is already t-f inconsistent — can be proven by contraposition. We argue that if
Γ does not have at least one finite subset that is t-f inconsistent, that is, if each finite subset of Γ
is t-f consistent, then Γ cannot be t-f inconsistent. From this it follows that if Γ is t-f inconsistent
it must have at least one finite subset that is t-f consistent, because if it didn’t, — if each of its
finite subsets was t-f consistent, it would have to be t-f consistent.
We prove that if each finite subset of Γ is t-f consistent then Γ must be t-f consistent by showing
that if each finite subset of Γ is t-f consistent, then there is a way to construct a single truth value
assignment on which each sentence in Γ is true, from which it follows that Γ must be t-f
consistent. It is from obvious that this must be the case. For any finite subset, Δ, of Γ, if that
finite subset is t-f consistent then there must be at least one truth value assignment on which all
the sentences in that set are true. But why should it be the case that the truth value assignment
that works for one finite subset should also work for any other? Why couldn’t it turn out to be
the case that the truth value assignment on which all the sentences in one finite subset are true
is different from the truth value assignment on which all the sentences in another finite subset
are true, so that, even though each finite subset is t-f consistent, there is no single truth value
assignment on which all the sentences in each of them is true?
To show why there must be such a truth value assignment, I need to introduce four preliminary
notions, the notion of a partial truth value assignment, of an expansion on a partial truth value
assignment, of the crashing of a partial truth value assignment, and of a total order for the
atomic sentences of SL.
A partial truth value assignment, α , ansigns exactly one of the two truth values to a proper
subset of all the atomic sentences of SL, that is, to some, but not all of the atomic sentences of
SL. So a partial truth value assignment leaves some atomic sentences, and hence any
compound sentences containing those atomic sentences, without any truth value. In contrast, a
complete truth value assignment, α*, makes an assignment to each atomic sentence of SL. An
expansion, α n+1 on a partial truth value assignment, α , in a truth value assignment that makes
all the same assignments that α doesn but that also makes an assignment to atomic sentences
not in the set that α nakes assignments to. We can construct a sequence of expansions on a
partial truth value assignment as follows:
α 0s the partial truth value assignment that makes an assignment to the sentences in { },
the null set.
α 1s the partial truth value assignment that expands on α to make0an assignment to one
atomic sentence, A , a1d so to the sentences in the unit set, {A }. 1
α 2s the partial truth value assignment that expands on α to make1an assignment one
additional atomic sentence, A 2, and so to the sentences in {A , 1 }. 2It makes the
same assignment to A that α does.)
1 1
α 3s the partial truth value that expands on α to m2ke an assignment one additional
atomic sentence, A , a3d so to the sentences in {A , A , A1}. 2It 3akes the same
assignment to A 1and A t2at α do2s.)
We would like to make a sequence like this that will end up with the result that the union of all
the partial truth value assignments in the sequence is a complete truth value assignment. (Note
that I say the union of all the expansions in the sequence rather than the last expansion in the
sequence. That is because, since there are infinitely many atomic sentences of SL, there is no
last expansion.) However, a problem arises because, when you have an infinitely large set, it is
possible to pick sentences out from that set in such a way that, even though you go on picking forever, you never pick all the set members. Think of the set of positive integers, {1, 2, 3, …}. I
can pick one integer after another from this set but if I only ever pick even integers then, even
though I go on picking out integers forever, I will never pick an odd integer.
Fortunately, the sentences of SL can be lined up in an inclusive order, which makes it possible
for us to pick each of them out in turn with assurance that we will never miss any — that each
sentence will come up for consideration at some finite point in the process. There are many
ways of lining up the atomic sentences of SL in such an order. Here is one:
We assign two place numerals to each of the sentence letters and numeric subscripts as
follows:
A 11 M 23 Y 35
B 12 N 24 Z 36
C 13 O 25 1 37
D 14 P 26 2 38
E 15 Q 27 3 39
F 16 R 28 4 40
G 17 S 29 5 41
H 18 T 30 6 42
I 19 U 31 7 43
J 20 V 32 8 44
K 21 W 33 9 45
L 22 X 34
We then take the “catalogue number” of any atomic sentence to be the number associated with
its vocabulary elements. So “A” has the catalogue numbe2711, “A ” the catalogue number
113843, “214 the catalogue number 12383740, and so on. Every different atomic sentence
differs from every other in at least one vocabulary element. Since each vocabulary ele

More
Less
Related notes for 2250