blog.kennypearce.net

Sets and Possible Worlds

This semester I'm directing an independent study on modal logic with a couple of students with strong math background. Yesterday some questions about sets and possible worlds came up, so I wrote up some notes for my students on the subject. This blog post is adapted from those notes.

Introduction

The development of axiomatic set theory was launched by consideration of Russell's Paradox: let A be the set of all sets that do not contain themselves. Does A contain itself or not? (This was on Existential Comics just yesterday!) The collection of axioms mathematicians developed to avoid paradox has the consequence that there is no set of all sets, nor is there any set equinumerous with the sets.

With that in mind, we ask three questions: (1) could possible worlds be sets of sentences? (2) Could possible worlds be sets of propositions? (3) Could there be a set of all possible worlds? In all three cases, there are reasons to suspect that the answer is 'no'. This doesn't create any problem for using the possible worlds semantics as a heuristic for modal reasoning, or as a formal model to show the consistency of our modal logic, but it does create problems for trying to use possible worlds to give an analysis of necessity.

Sets of Sentences

Start with (1). Assuming that every language must have (at most) countably many basic symbols, and that the sentences of the language are strings of those symbols, we get the result that the set of all sentences of a given language is countable, which is to say that
there are as many sentences as there are natural numbers. We can see this in two ways:

First, by Gödel Numbering. According to the Fundamental Theorem of Arithmetic, every natural number has a unique prime factorization. Assign a natural number to each symbol in our language. (We can do this, since we assumed there were at most countably many symbols.) Let the sequence of primes stand for the positions in the sentence. Then raise each prime to the power of the number for the symbol that belongs there. So, for instance, 5 is the 3rd prime. If we assign the symbol '&' to the number 2, and '&' is the 3rd symbol in our sentence, then we'll have 5^2 in the prime factorization of the number for the sentence. This allows us to assign a unique natural number to every sentence in our language, which shows that there are (at most) as many sentences as the natural numbers.

Second, by effective enumerability. A set is effectively enumerable iff there is an algorithm that will iterate over all the members of the set without missing any. If the set is infinite then the algorithm will never terminate, but you'll get to any member of the set if you run the algorithm long enough. Any effectively enumerable set is countable, since every member of the set must be the nth to be produced by the algorithm for some natural number n. Now, suppose for a moment that the set of basic symbols is finite. Then we can have our algorithm first produce all the sentences of length 1, then all those of length 2, and so forth. For each length, there are only finitely many sentences, so we won't get stuck and will eventually get through all of our sentences.

If we have a countable infinity of basic symbols the enumeration is a little more complicated, but we can still do it. Since we have countably many symbols, we can put them in some arbitrary order. Then we can get through all of them using the same iteration procedure used to prove the countability of the rationals. (See this picture.) So we first generate all the sentences of length 1 that use only the first symbol, then the sentences of length 2 using only the first symbol, then the sentences of length 1 using the first 2 symbols, then the sentences of length 1 using the first 3 symbols, and so on through the diagram. (The numerator is the length of the sentences, the denominator is the number of symbols.) In this way, we'll generate all possible sentences.

Ok, so there's a set - and a countable set at that! - of all the sentences in a given language. We might therefore try to define possible worlds as maximal consistent sets of sentences in some language. ('Consistent' meaning there's no contradiction; 'maximal' meaning if we added another sentence we'd get a contradiction.) But there's a problem: we don't seem to have enough sentences for all the ways the world could be. For instance, it seems possible that there could be point particles with perfectly precise locations in Euclidean space (even though our world is apparently not like this). Then, for every real number x, there should be a possible world where all that exists are two particles exactly x meters apart. But we don't have enough sentences to distinguish all of these worlds from one another. (There are theories about space that would allow you to deny that these worlds are possible, but there are also other such examples that could be constructed. Of course, you could try to reject all of them.)

Sets of Propositions

So maybe we can define possible worlds as maximal consistent sets of propositions. Unfortunately, as Patrick Grim pointed out there is no set of all true propositions. One way of seeing this is simply that, for every set, there is a true proposition that says that set exists. So if there's no set of all sets then there's no set of all truths. (Grim uses a different argument.) If there's no set of all truths, then it can't be that each possible world is defined as the set of propositions true at that world, because if we went that way then the actual world would have to be the set of all truths.

A Set of Worlds

The possible worlds semantics also assumes there's a set of all worlds. This faces a problem too, though: someone might think that, for any cardinal number k, it's possible that there should be exactly k electrons. If this were right, then there couldn't be a set of all possible worlds. (You could get out of this by denying that it's possible for there to be more than continuum many concrete objects - that's not too implausible. Other examples can be constructed, but again you could try to reject all of them.)

Conclusion

Again, these are problems for trying to use possible worlds to give an analysis of talk about necessity and possibility, i.e., to say what we really mean by such talk, or what makes such claims true. There have been various attempts to overcome these difficulties, but even if those attempts all fail we can still use the possible worlds semantics for other purposes.

Posted by Kenny at September 15, 2015 9:53 AM