Sebastian Hayes

                                                 Contra Cantor

 

 

 

Passing in review the various paradoxes, linguistic and mathematical, that bothered logicians around the beginning of the last century, Russell and Whitehead — I shall henceforth just say Russell — found that “they all result from a certain kind of vicious circle” that consists in “supposing that a collection of objects may contain members which can only be defined by means of the collection as a whole” (RW, 37). As an example of what they had in mind they cited the statement “All propositions are either true or false”.  Russell comments:

 

   “It would seem that such a statement could not be legitimate unless ‘all propositions’ referred to some already definite collection, which it cannot do if new propositions are created by statements about ‘all propositions’ ” (RW, 37).

 

            More mathematical examples are the Set of All Sets — is it a member of itself? — or Burali-Forti’s paradox of the Ordinal Number of All Ordinals.

            Russell suggests stopping such statements being made, or at any rate being accepted as meaningful by logicians — “Whatever involves all of a collection must not be one of the collection”  (RW, 37). Poincaré coined the term ‘impredicative’ for statements that define an object in terms of a collection to which the object being defined belongs. He considered that impredicative definitions should be banned from mathematics.

            But what happens if we do want to talk about ‘all’ the members of such a collection? This, Russell assures us, need not pose any insuperable difficulties. A statement about ‘all’ of a certain collection is of ‘higher type’ than a statement about specific members of the collection and in consequence must be excluded from the range of application of the statement. The Set of All Sets is ‘of higher type’ than any Set you like to mention which will be one of its members, and so we do not get the ridiculous situation of the Set of All Sets being at one and the same time a member, and yet not a member, of itself.

            At first sight Russell’s solution sounds both sensible and effective. However, it soon became a major embarrassment to him, for not only did strict application of the theory of types make a lot of proofs very cumbersome it actually invalidated a lot of them. As Weyl and others pointed out, analysis turned out to be littered with impredicative formulae. This stimulated the Intuitionists to reformulate the whole subject but Russell had no intention of taking such a heroic course. He states airily in the Introduction to the 1927 re-edition of  Principia Mathematicae that “though it might be possible to sacrifice infinite well-ordered series to logical rigour, the theory of real numbers….can hardly be the object of reasonable doubt (RW, xlv, 1927). But why not? Russell’s reply sounds suspiciously like an eighteenth century clergyman’s assertion that “the eternal existence of a Creator God cannot seriously be questioned”.  

            Subsequent mathematical discussion of these issues has clouded rather than clarified the basic principles at stake: in particular far too much attention has been given to the validity or otherwise of the so-called Axiom of Choice. As it seems to me, the problem is not ‘impredicative statements’ as such — this is something of a red herring — but a failure to distinguish between  ‘definite’ sets  and ‘indefinitely extendable’ sets. By definition the former are fully constituted once and for all, and thus listable, whereas the latter are not. Confusing the two is the real ‘category mistake’ at the root of all the kerfuffle. 

            In conversation we normally deal with two, and only two, types of sets or collections, those that are what I call definite and those that are continually being extended. The persons living in the UK at the present moment constitute a definite set which can be (and actually is) listed — at any rate within the bounds of bureaucratic error. The set of all human beings, past, present and future, is not a definite set but a continually expanding one, and one that will presumably continue to expand as long as the species exists. 

            Self-referential statements of the type “Whatever I say is untrue” only cause trouble because there is a certain ambivalence about the type of collection we are dealing with. One schoolboy philosopher exclaims to another during the lunch-break, “You know, there’s not a single thing I’m sure about!” His companion rejoins, “Ah! but there is one thing at least you’re sure about, and that is that you aren’t sure about anything!”

            Sceptic’s first statement only referred to the fully definite set of all beliefs he had actually considered up to that moment, and a standpoint of all-round scepticism was  not one of them. It would be quite perverse to consider his first statement as referring to the collection of all possible beliefs the human species might conceivably entertain. The belief “I don’t believe in anything” was not, at the beginning of the discussion, a member of the Set of All Beliefs Sceptic Had Considered (a definite set) but after the end of the conversation it was. His first statement was time and context dependent : it was not an intemporal assertion.

            At a future time Sceptic, if he were consistent, would say, “I’m not sure about anything — except the statement I made to you yesterday that I wasn’t  sure about anything I’d considered up to then.” The Set of Beliefs Sceptic Was Sure About started off empty, then contained one member, perhaps went on to containing two members if Sceptic carried on with declarations in the same style, and so on.

            All this hardly seems worth dwelling on. So why the fuss ? Because, when it comes to mathematics, the situation is very, very different. Mathematical assertions are not generally considered to be time and context dependent, they are in some sense held to be ‘eternally true’, true even before human beings or the universe we live in existed. Once true, always true, when it comes to mathematics. 

            So far it has not been necessary to introduce the fatal word ‘infinite’ but it cannot be withheld any longer. Can any so-called ‘infinite’ set ever be a fully constituted totality, a ‘definite set’ ? I do not see that it can. The only sensible way of treating ‘infinite’ sets is to view them as open-ended partly definite sets which can be extended as far as we wish. This is entirely in line with the way we proceed in normal speech and conversation — which, one strongly suspects, is the main reason mathematicians disapprove of such an approach.  

            What we must above all not do is to treat an open-ended indefinite set as a fully constituted one. But in mathematics, ever since the advent of Cantor and Dedekind, this is exactly what is done in mathematics. This is the essential ‘category mistake’, the sin for which there is no forgiveneness, not Russell’s ‘self-referential misapprehension’. Some mathematicians, notably Cantor himself, were frank enough to put their hands on the table and declare that they really did believe in the existence of the transfinite. Even Russell, though at the time a positivist, introduced into his Principia the controversial Axiom “That infinite classes exist” (RW, *120.03). Most modern mathematicians are, however, content to evade the issue : as Davis and Hersh point out, the modern mathematician is two things at once, a Platonist in the study, but a Formalist when confronting the outside world.

 

Cantor’s Proofs

 

Cantor’s proofs are of two main types, one acceptable (to me), one not. Let us first take his proof that the rational numbers between 0 and 1 form a null set.

            This depends on two prior results, his ingenious diagonalisation of  Q, the  rational numbers, and the well-known limit (as usually stated)

              lim.  n ® ¥  (1/2 + 1/4 + 1/8 + ………+ 1/2ⁿ)  =  1.

            Since, for any positive rational number you like to name, say 1/N, I can always find a smaller one, namely 1/(N+1), it looks at first sight as if it were impossible to list the rational numbers, first, second, third &c., i.e. put them in one-one correspondence  with N, the natural numbers. But Cantor showed how this could be done. For example, those between 0 and 1 can be listed as follows:

 

            0, 1, 1/2, 1/3, 2/3, 1/4, 2/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6…..

 

            This is not an ordering by increasing or decreasing size but that does not matter, nor does it matter (too much) that there will be some redundancy — 2/4 will appear though we already have 1/2. The point is that given any specified fraction between 0 and 1, it will eventually crop up and can be attributed an ordinal from the natural numbers, hundred and seventy-seventh, ten-thousandth, or what have you. We do not need to know what this ordinal is, but we do know that we can provide it if challenged to do so if given enough time.   

            There is nothing objectionable in this procedure since we do not have to envisage the rational numbers between 0 and 1 as a definitively constituted totality existing in some Platonic never-never land — though this is undoubtedly how Cantor himself viewed them.

            The sequence S = 1/2, 1/4, 1/8……..1/2^n-1  is a geometric sequence with constant ratio 1/2. The terms are respectively t₁ = 1/2, t₂ = 1/2², …..t_n = 1/2ⁿ.   If we take partial sums s₁ , s₂ , …. s_n we have

            s₁ = 1/2 = (1–1/2); s₂ = 1/2 + 1/4 = (1–1/2) + (1/2 – 1/4) = 1 –1/4 ;  and

s_n = (1 –1/2ⁿ)  < 1 for all n Î N.

            The series S_p of successive partial sums is clearly, in my terms, not a fully constituted totality but an indefinitely extendable one. Many slapdash authors, who ought to know better, talk about 1 being “the sum to infinity” of the series: in fact, as is generally the case with series, the limit 1 is unattainable and there is no definitive sum, only a perpetually changing one as n increases, which is why we speak of ‘partial’ sums, though the word is misleading.

            Cantor now invites us to construct a sequence of open intervals where each interval {I_n} has centre r_n . Each interval starts at the point (r_n – k/2ⁿ⁺¹) and ends at the point (r_n + k/2ⁿ⁺¹) so it has length twice k/2ⁿ⁺¹ or k/2ⁿ. Since we have got a way of listing the rational numbers we drop them one after the other into these intervals. And the total length of n intervals is

 

   k/2 + k/2² + k/2³ + …..+ k/2ⁿ   =    k( 1/2 + 1/4 + 1/8+ ………..)  

                                                            =  k(1 –1/2^n-1)  < k  since (1 –1/2^n-1) < 1

 

            Provided we can decrease k as much as we wish, we can squeeze ‘all’ the rationals between 0 and 1 into an arbitrarily small compass. So a line segment a foot (or a millimetre) long is nonetheless capable of containing an ‘infinite’ quantity of numbers, many more than there are stars in the sky. Cantor has thus, to his own satisfaction at least, shown that the rationals between 0 and 1 are what he calls ‘a null set’: they take up so little space it’s as if they weren’t there at all.

            One might baulk a little at this over-literal way of considering numbers as points on a line (which they are not) and, of course, in the real world there would be a definite limit to the size of k — it could not be made smaller than that of an elementary particle, for instance. However, one might be prepared to let this pass as temporary exercise of mathematical licence. The main thing is that there is no need to view this procedure as having been carried out for ‘all’ the rationals 0 < q < 1 but only for as many as someone likes to mention. It is usually stated in maths books that this result (the infinite compressibility of Q) is ‘counter-intuitive’ : it would be more accurate to describe it as being unrealistic. This is not a problem if we make sure to continually bear in mind that a mathematical model or construction is not itself part of the physical world. 

            Other bizarre results such as the length of the Koch curve fall into the same category. Starting with an equilateral triangle, then building one on the middle third of each side and continuing in this way ad infinitum, it appears that the perimeter of the curious jagged figure can be made to exceed any stipulated length provided you go on long enough even though the whole creature can be inserted in a disc of, say, radius one metre. Of course, in any actual situation there would once again be a limiting size beyond which it would not be possible to go : there is certainly no need to conclude that we have here a case of “infinity in the palm of your hand” (Blake), though some people seem to think so.  

            If now we pass to Cantor’s ‘proof’ that the real numbers are not denumerable, we have a very different kettle of fish. A collection is considered denumerable if it can be put in one-one correspondence with N, the natural numbers — broadly speaking can be listed. We have seen that this is possible for the rationals between 0 and 1. Cantor now invites us to consider an enumerated list of all the real numbers (rationals + irrationals) between 0 and 1. These reals are exhibited in the form of non-terminating   decimals — any other base would be just as good. To avoid ambiguity a fraction like 1/5 has been listed as 0.19999999…..  instead of 0.2 —  absurd though it would be to do any such thing. So there they all are :

           

            s₁ = 0.a₁₁ a₁₂  a₁₃ …….    

            s₂ = 0.a₂₁ a₂₂  a₂₃…….         

            s₃ = 0.a₃₁ a₃₂  a₃₃…….         

            …………..

            where every a is a natural number between 0 and 9.

            Cantor now produces out of a hat a ‘number’ that has not appeared in the list, call it b. We concoct b by ‘doing the opposite’ as it were. If a₁₁ is 1, make b₁ (the first digit of b) = 2, if a₁₁ ¹ 1 make b₁ = 1. Likewise for a₂₂ , a₃₃, giving b₂ , b₃  and so on. This defines b = 0.b₁ b₂ b₃ ……   But this ‘number’ has not appeared in the list since it differs from s₁ in the first place, from s₂ in the second place and so on. Therefore, the real numbers between 0 and 1 are not denumerable, and since these are only a small part of R as a whole, R, the Set of all Reals is not denumerable — a paradoxical result since N is already an ‘infinite’ set, so R must be of a higher type of infinity than N, Q.E.D.

            Now this proof by contradiction wholly depends on the original assumption that all the reals between 0 and 1 have been listed — not one has been left out. Since Cantor shows one that has been left out, the assumption must have been wrong in the first place. However, if we do not view the reals between 0 and 1 as a folly constituted totality, listable and enumerable, but as an open-ended extendable set, the argument collapses like a burst balloon. All that could ever be on view at a single moment in time is an array of decimals — or other r-esimals — taken to n places. A competing generator handled by Cantor in person cannot produce any real number for given r and n which is not on show since all possibilities are covered. All Cantor can do is print out an arbitrary ‘diagonal’ rational number between 0 and 1 to m places with m > n.

            Since the base used is immaterial let us use base 2 and print out numbers between 0 and 1 using only the symbols 0 and 1. In the first print out we only go so far as one digit, then we print out all numbers with two digits after the point and so on. We have

 

            0.0       0.00                 0.000

            0.1       0.01                 0.001

                        0.10                 0.010

                        0.11                 0.011

                                                0.100

                                                0.101

                                                0.110

                                                0.111

           

            To keep ahead Cantor has to counter with a number containing at least one more digit after the point, but whatever he chooses this number will come up at the next print out. Thus the struggle is ding-dong and inconclusive. It should be stressed that the ability to view R as a whole does not depend on our limited range of vision or the size of the memory of the computer or any other technicality : the reals are simply not exhibitable in their full extent because strictly speaking they do not have a ‘full extent’. Even God would not be able to view ‘all’ the real numbers at one fell swoop because there is no ‘all’ to view.

            Very similar is Cantor’s ‘proof’ that, for all non-empty sets A, the cardinality of A  <  the cardinality of the Power Set of A. (The Power Set, remember, consists of the sets that can be constructed  from the members of A e.g. if A = {1, 2, 3}, the P(A) consists of  A itself = {1, 2, 3}, also the sets {1, 2},

{1, 3} and {2, 3}, the singleton sets {1}, {2} and {3} and Ø, the Empty Set.)  Obviously, for ordinary ‘finite’ sets the theorem holds, but, since things become so disconcerting when we pass to consider transfinite sets, Cantor wonders whether it remains valid.

            In typical fashion Cantor proceeds to assume that an exhaustive mapping from A to P(A) has been carried out. Since for any a we can, faute de mieux, pair it off with the set of which it is the sole member, namely {a}and this is far from exhausting all the possibilities, Cantor concludes that the cardinality of P(A) cannot be less than the cardinality of A.

            We are now invited to consider the Set B given by:

 

B:   {a Î A, a ¹ f(a)}

 

i.e. the set containing all those elements which are not members of the sets they have been paired off with in the mapping. It would seem that B is non-empty. But if so, B, being a bona fide subset of P(A) must have a pre-image under this mapping, a_b say, i.e. there is an a_b in A such that f(a_b) = B. But a_b itself must either belong to B, or not belong to B. We find that if it does it doesn’t and if it doesn’t it does. Thus contradiction. Therefore there can be no such mapping

f: A  ®  P(A) and so  card. A < card. P(A)  Q.E.D.

            This argument is worthless because Cantor has envisaged a mapping that cannot ever be carried out in full, even in theory : he is treating an ongoing, indefinitely extendable mapping as a completed act.

 

Sets with oscillating membership

 

If we regard the proposed function f, not as already existent, but as in the process of being defined, we get a different picture. Suppose we have carried out a bijection from A to P(A) to n places — which is all we can ever hope to do — and we have a non-empty set B satisfying Cantor’s condition, namely that individual members of B have not been paired off with themselves viewed as sets. B does not as yet have a pre-image in A so, noting this, we pick some element in A not yet used, a_b say, and form (a_b , B).

            Now, prior to its being assigned an image under the function f, the element a_b did not have an image ; however, now that it has acquired one we realize that it has automatically become a member of B (which it was not before) and so is disqualified from being the pre-image of B. We thus remove a_b from (a_b, B) and look for another pre-image. The same situation develops and one might justifiably conclude that, since we are perpetually going to have to change B‘s pre-image as soon as we assign one, then any function of the desired type A to      P(A) is going to be of a very provisory nature and so, we might decide, for this reason, to conclude that the cardinality of P(A) must be ‘greater’ than that of A. This is not quite what Cantor says though.

            This oscillating procedure whereby one or more element changes sets perpetually is entirely normal outside mathematics — in fact it is really only in the unreal world of mathematics that sets ever do get constituted definitively once and for all. Individuals are always changing their set membership as their age changes, as their beliefs mature, as the frontiers of countries  are  redrawn and so forth. Even species evolve and change into radically different ones, so we are told, and nothing stays exactly the same for very long.  

            A typical example of ‘oscillating membership’  is provided by Russell’s Village Barber Paradox though Russell did not realize this. Russell invites us to consider a Village Barber who claims he shaves everyone in the village who does not shave himself and only such persons. The big question is : Does he shave himself? If he does shave himself, he shouldn’t be doing so — since, as a barber, he shouldn’t be shaving self-shavers. On the other hand, if he doesn’t shave himself, that is exactly what he ought to be doing.

            The contradiction only arises because Russell, like practically all modern mathematicians, insists on viewing sets as being constituted once and for all in the usual Platonic manner. Let us see what would actually happen in real life.  It is first of all necessary to define what we mean by being a self-shaver : how many days do you have to shave yourself consecutively to qualify ? Ten? Four? One? It doesn’t really matter as long as everyone agrees on a fixed length of time, otherwise the question is completely meaningless. Secondly, it is important to realize that the Barber has not always been the Village Barber : there was a time when he was a boy or perhaps inhabited a different village. On some day d he took up his functions as Village Barber in the village in question. Suppose our man has been shaving himself for the last four days prior to taking on the job, so, if four days is the length of time needed to qualify as a self-shaver, he  classes himself on day d as a self-shaver. He does not get a shave that day since he belongs to the Self-shaving set and the Village Barber does not shave such invididuals.

            The next day he reviews the situation and decides he is no longer in the Self-shaving category — he didn’t get a shave the previous day — so he shaves himself on Day 2. On Day 3 he carries on shaving himself — since he has not yet got a run of four successive self-shaving days behind him. This goes on until Day 6 when he doesn’t shave himself. The Barber spends his entire adult active life oscillating between the Self-shaving and the Non-self-shaving sets. There is nothing especially strange about this : most people except strict teetotallers and alcoholics oscillate between being members of the Set of Drinkers and Non-drinkers — depending of course on how much and how often you have to drink to be classed as a ‘drinker’.

            This example was originally chosen by Russell to show that the self-referential issue has nothing necessarily to do with infinity. Nor does it, but it does depend on the question of whether sets or collections are time and context dependent.

 

Conclusion

 

One understands, of course, why mathematics as the exact science par excellence does not want to be bothered with such messy creatures as sets with varying membership but it is worth stressing how different the abstract systems of mathematics are from conditions in the real world. Perhaps, in the future a kind of mathematics will arise which will be time and context dependent while still remaining more precise than ordinary speech. Mathematics does indeed model time dependent processes, notably via differential equations, but only from the outside : time itself in the sense of change is never allowed to be present within the boundaries of the mathematical system. Mathematics has managed to do something which sounds equally difficult, namely to model randomness (up to a point) and there is an interesting chapter discussing this complex issue in a recent book, How Mathematicians Think, by William Byers (Chapter 7). However, randomness is still, like time, studied from the outside although it is getting steadily closer and closer to the fixed ideal world of mathematics via Heisenberg, chaos theory, Gödel’s Incompleteness and so forth.  Maybe the twin shadows of time and chance will in the end blot out the pure light of eternity after all.    

 

NOTE:  This article appeared in Issue 223 of  M500, the magazine of the Department of Mathematics of the Open University, UK.