# 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

*-sets to which individuals can be said to belong with a relation of*

__U__*-belonging, which we shall write*

__U__*. So we may write*

__E__*a*

*to signify that*

__E__b*a*bears the relation

*to the*

__E__*-set*

__U__*b*.

*, 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.*

__U__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 (

*-) 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.*

__U__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 2*n*.

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 *: *x*__E__a}

and where:

` `*x *belongs to *^a* <-->* x*__E__a .

*^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

*we*might 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!