Is Countability Relative?
In order to create a system for mathematics (or, indeed, any logical system) we need (at least) two things. Firstly, we need a theory for the language - that is, a set of syntactic rules for what is a valid sentence, how to form sentences, etc., and which also tell you how the symbols can be manipulated, and what sentences can be derived from any premises in the language. Whilst formulating a theory for the language is a large part of the work, any theory remains merely syntactic - it can only represent a system for manipulating (pretty much) arbitrary, meaningless symbols. The second part, therefore, is to match this theory with a model - that is a semantic framework, establishing what the symbols of the language represent. In this way we are able (for example) to relate a theory to the world, and hopefully match it to our intuitions about what is so and what isn't. Traditionally mathematics has relied on a strict separation as to the parts which are simply related to the theory and the model - the system - and that which is about the world, about what is true, out there, unrelated to how we construct our formalisation to describe it.
Lowenheim formulated a theorem later expanded upon by Skolem which basically said that any sentence true on a model with any infinite domain will be true on a model with the smallest, enumerably infinite domain. So, the theorem goes, there are no sentences which are true only on a model with a non-enumerably infinite domain, for if it is true on this model, it will be true on a model requiring only an enumerably infinite domain. I shall argue that the Lowenheim-Skolem theorems have forced philosophers of mathematics to reassess whether a number of seemingly simple notions, which had been thought to be facts about the world, are actually relative to the model in which they are being discussed.
In his exposition of Lowenheim-Skolem theorems Machover asks us to consider Hugh, who lives in a enumerably infinite universe, unlike our own - which is usually conceived to have an unimaginably large number of things, in fact such a large infinity of things that this number of things is not enumerable. Hugh, being adequately adept at mathematics, is able to understand a formulation of set theory within his world, with similar relations to ours (but whose domain is this smaller subset of our own). Within his universe, U, for example, are U-sets to which individuals can be said to belong with a relation of U-belonging, which we shall write E. So we may write a Eb to signify that a bears the relation E to the U-set b. U, however, follows the same theory, that is is in the same language of set-theory as we use, and is simply a different model on this language - so anything that can be deduced according to our set-theory can be deduced within Hugh's, since the symbols still occupy the same positions, and obey the same rules - Hugh's mathematics differs simply in how sentences of his language are to be construed. If we were to discuss mathematics with Hugh, therefore, he could participate quite productively, and would never have cause to doubt that he was talking about the same relations and sets, even though we know that he is not.
One theorem of our set-theory, however, states that 'there exists an uncountable set', and our mathematics would be substantially different if this were not so. Hugh's mathematics, however, as we have seen, differs from ours only in how it relates to what actually exists (or, I suppose U-exists, in Hugh's case) in the universe it discusses. Hugh's mathematics, therefore, must include a theorem, which Hugh could derive, which states that 'there (U-) exists an uncountable set'. It seems to be the case, therefore, that in Hugh's world there is a set which contains uncountably-many members, whereas Hugh's entire world contains only countably many members: this is paradoxical. Clearly it would be very strange if, whilst all the members of a world are countable, the intersection of the members of the world and a set within it were not.
An explanation of this perceived paradox, and how we might escape it, requires an examination of just what we mean when we say that an infinity is 'enumerable'. We understand the natural numbers to be enumerable, and this is indeed why this term is used - it is possible to count, systematically, from the first natural number (0) to, given enough time, any natural number you might choose. Whilst the naturals are infinite, and we never run out of next-numbers-to-count, we are able to specify a simple way to cover every member of the set - namely saying them in order incrementing by 1 each time. A set is said to be enumerable if and only if there is a function which maps each member of the set to a member of the set of natural numbers - that is, it is possible systematically to assign a number (or position) to every member of the set. Clearly it is possible to do this with many infinite sets - for example the even numbers, where the function n/2 maps every member n onto the natural numbers.
With various other sets, however, such as that of the real numbers, it is not possible to form a list of every member. There is no way to systematically order every infinite decimal in such a way that every member has a (finite) position within the sequence. We might try first stating the natural numbers, then those with a single decimal place, then those with two decimal places, etc., but this clearly will not work, since 1.1 will be in position infinity + 1. We could try starting from 0, and counting first to 1, stating every number in between, but this does not work, since the second position will be occupied with 1 preceded by an infinite number of decimal places filled with 0s, and therefore there will always be another number, with one fewer 0. With any attempt to create a list of the reals, we find ourselves counting to infinity many times over, without getting any closer to our goal of listing them all. There is, to put it slightly more formally, no function that will map the real numbers onto the natural numbers.
Let us compare this conception of enumerability with that of finiteness. Whilst our definition states that a set is non-enumerable if there is no function which maps every member of the set onto a member of the set of natural numbers, our definition of finiteness (as can be seen from the axiom of infinity) is that if a set is finite, there is no 1-to-1 function capable of mapping every member of the set onto a subset of itself. We have already seen that such a mapping is possible with an infinite set - the even numbers are a subset of the natural numbers, yet it is possible to map, 1-to-1, every member of the natural numbers onto the evens, namely by mapping each natural number n to the even number 2n.
The problem for this formulation of enumerability arises, however, when we consider exactly what we mean by 'there is no function which maps a non-enumerable set onto the natural numbers'. Whilst previously it had been thought that enumerability was a primitive, simple property of a set, the Lowenheim-Skolem theorems shows that it cannot be, and instead whether something is enumerable or not is a function of the model in which the set is being discussed. Whilst we have a function capable of mapping the members of Hugh's world onto the natural numbers, it seems that Hugh himself does not. Can we be sure of this, or is it simply a convenient hypothesis for explaining away the Lowenheim-Skolem theorems but for which we have no other evidence? The answer is that we can, indeed, prove that Hugh cannot map the members of his world onto the natural numbers.
Let us call '^a' the E-extension of a, a set in Hugh's world. We thus have a set:
^a = {x : xEa}
and where:
x belongs to ^a <--> xEa .
^a is clearly a set in our world, and for any subset A of our universe U we can form an E-extension such that ^a = A. So any set a in Hugh's world will correspond to a set in our world, yet it is clearly not the case that the opposite is true: not all sets in our world correspond to sets in Hugh's world (for example, none of our non-enumerable infinite sets correspond to ones in Hugh's world). So we can see that whilst wemight be able to map the member of Hugh's world onto the natural numbers, and thus for us the set is enumerable, Hugh cannot, and thus for him it is not. Thus enumerability, previously thought objective, is found to be relative to the model in which one is working, as, in fact, do other notions such as finiteness, for similar reasons - that what functions exist to produce mappings depend on the model - without a function mapping every member of Hugh's universe onto a subset of it, for him the universe, which we know to be infinite, turns out, by definition, to be finite.
It seems, then, that the model-variant aspects of mathematics which the formulation into set theory had sought to remove are simply pushed back to set theory itself. It seems that various important notions depend on facts about what functions exist in a world, and it turns out that what functions exist in a world are just as much relative to the model as the relations we had sought to explain objectively in terms of these functions. We are back, then, where we started, except that it seems a good deal more likely that, rather than just not having found the system of mathematics which is not more bogged down in the model than the nitty-gritty of what there actually is in the world, there simply isn't one!