## I don’t trust uncountable sets

November 5, 2009 by Qiaochu Yuan

I have a mathematical confession: I don’t trust uncountable sets.

Some time ago on MathOverflow somebody asked what a reasonable definition of “infinite permutation” would be. The first answer that comes to mind is a bijection . The set of all such bijections does form a group, but not only is it uncountably generated, it contains, as Darsh observes, a copy of every countably generated group (acting on itself by left multiplication). In particular it contains a copy of the free group on countably many generators. It also doesn’t seem to carry any natural kind of topology.

On the other hand, a much nicer candidate is the set of “compactly supported” permutations, i.e. those which fix all but finitely many elements. This countable group is generated by transpositions and therefore has a neat presentation given by the usual relations. I believe it’s also the largest locally finite subgroup of the full group of bijections.

I find this group much more philosophically appealing than the full group of bijections, and the reason is simple: each element of the group is computable. On the other hand, only countably many elements of the full group of bijections are computable: the rest can’t be written down by a Turing machine. And I don’t trust anything that can’t be written down by a Turing machine.

**Corollary:** I don’t trust the real numbers.

Instead of explaining what I mean by this, which I don’t think I have time for today, I’ll just throw a question out to the audience: how do you feel about all this?

### Like this:

Like Loading...

*Related*

on November 5, 2009 at 1:48 pm |Akhil MathewMy response: I don’t trust finite sets. They’re unsatisfying approximations to the continuous and geometric, which I (following Scott Aaronson) will call Platonic heaven.

Seriously, I don’t share your scruples.

on November 5, 2009 at 2:36 pm |HarrisonYeah, I’m with Akhil on this one. I guess the workaround is to say that you can’t write down an infinite bijection (or a real number) with a Turing machine, but you can get a sequence of “nice” bijections or rational numbers that converges (or, I guess, “converges” in the first case, since I don’t see an obvious metric that’s well-defined) to it.

on November 5, 2009 at 3:10 pm |Qiaochu YuanIf a real number isn’t computable, that’s the same thing as saying a Turing machine can’t write down a sequence of its rational approximations.

To be more concrete, here’s a perfectly well-defined bijection: and is the smallest positive integer not in . This function is not computable. Any finite sequence of its “approxiations” are, but the set of all of its “approximations” is also not.

on November 6, 2009 at 6:13 am |HarrisonAny given Turing machine can’t, but a sequence of Turing machines can — admittedly this sequence of Turing machines isn’t computable either, though. But it “exists,” and that’s the important thing (IMO).

on November 6, 2009 at 7:17 am |Qiaochu YuanYes, but that totally defeats the purpose of thinking about Turing machines! An arbitrary sequence of Turing machines can write down an arbitrary sequence of numbers.

on November 5, 2009 at 3:12 pm |Yufei ZhaoI’m with Qiaochu here. I guess this is the kind of feeling that separates the combinatorialists from the non-combinatorialists.

on November 5, 2009 at 4:27 pm |Charles SiegelI’m weird. I agree: is not to be trusted. Of course, my solution? Go to , which is a perfectly trustworthy thing.

on November 5, 2009 at 6:45 pm |Charles WellsThe bijections of N, and the real numbers, seem non-trustworthy because you can’t get your hands on them! You can’t name every one. You can’t even name most of them.

*But* mathematicians have been dealing with this kind of set for years and year and proved many theorems and no contradiction has ever shown up. They behave like they are there even though you can’t get your hands on them.

I guess you have to put your hands on the computer monitor and Believe…

on November 5, 2009 at 8:03 pm |Barry CunninghamYes, the vast majority of reals cannot be named or even described precisely. Hence, in any movie about the real numbers, they will not appear in the credits. They are true supernumeraries.

on November 6, 2009 at 11:10 am |Kevin CostelloI’m reminded from a quote from Gowers “Two Cultures of Mathematics”

“Sometimes, the set of all eventually zero sequences of zeros and ones is a good model for separable Banach spaces, or at least allows one to generate interesting hypotheses.”

Here, it’s the set of all “eventually identity” bijections that seem to be the interesting object.

on November 6, 2009 at 12:41 pm |Josh1) In terms of philosophical appeal regarding groups of “infinite permutations,” I’d say that the group of computable bijections of the natural numbers is much more appealing. It lacks some of the nice properties of the group of compactly supported permutations (e.g. I don’t know of a nice generating set, let alone a nice presentation). But it also contains genuinely infinite permutations!

2) There is a natural topology on the full group of bijections from $\N \to \N$ (and on many of its “natural” subgroups): let $U_n$ be the collection of all bijections that fix 0,1,2,…,n. Then the {$U_n$} form a basis of open sets around the identity, which you then turn into a basis for a topology of the group in the usual way (namely, by translation). This topology is the one you were implicitly talking about when you mentioned convergence.

3) This circle of ideas around not trusting the reals is closely related to the fact that, say, there is a countable model of the reals.

on November 6, 2009 at 1:21 pm |Qiaochu YuanDo you have a reference describing the countable model of the reals? This model theory stuff is very philosophically interesting.

on November 6, 2009 at 1:32 pm |JoshAny book that includes first-order logic and “Skolemization.”

I think it’s best to view this kind of result as basically saying: “We write math down using a finite alphabet. They are only countably many formulae that can be written in this finite alphabet. So we can never write enough formulae to uniquely specify more than countably many elements in our model.” This does NOT mean that the cardinality of the reals is countable, just that there is a countable set and anything (first-order) that is true about that set is true about the reals, and vice versa. (In particular, note that the property of having uncountable cardinality cannot be specified in first-order logic.) You can think of this set as the set of “describable” elements.

on November 6, 2009 at 2:39 pm |Qiaochu YuanSo I guess what I really should’ve said is “I don’t trust second-order logic.”

on November 7, 2009 at 10:21 am |JoshI don’t know that second-order logic is the root of the problem (except that perhaps you can actually formulate the notion of uncountable, but I don’t know that that’s the root of the problem either). Even using second- (or third-, fourth-, etc.) -order logic, you can still only ever write down countably many sentences, so you can still only ever specify countably many objects. Some of the objects you specify might now be, say, relations on the reals, or functions, but even then, you can only specify their values at countably many points… That’s enough to “know” the entire function if, for example, you write down that the function is continuous (which is easy to do in first-order logic even). I don’t really know where I’m going with this, except to say that I don’t think it’s the power of your logic that is the problem, but rather that we always work over a finite alphabet, which gets back to your original concern.

on November 7, 2009 at 3:54 pm |Todd TrimbleFor (externally) countable models of the reals and generally of countable first-order theories like ZFC, try googling Löwenheim-Skolem.

A brief remark on the topology of the permutation group on : the typical thing to do is consider this as a subspace of , the space of all endofunctions on $\mathbb{N}$ (or equivalently of all countable sequences of natural numbers), equipped with the product topology. That coincides with the topology to which Josh referred. This infinite product space is homeomorphic to the space of irrational numbers between 0 and 1 with its usual topology (to see this, use continued fractions).

I’d also like to point out that the theory of the real numbers (as an ordered field) is much nicer than the theory of natural numbers: it’s decidable! This is essentially due to Tarski (or Tarski-Seidenberg); to me it says that real (semi)algebraic geometry is nice and tame whereas the natural numbers are wild. This remains true under various enlargements of the theory, e.g., the theory of the reals as an ordered exponential field is still decidable.

on November 14, 2009 at 1:26 pm |Luke GIs it just a freaky coincidence I said something similar the same day? :)

http://leakyninja.blogspot.com/2009/11/real-numbers-unreal.html

on February 14, 2010 at 4:34 pm |Gary DavisDoesn’t the free group F[x,y] on 2 free generators contain a copy of the free group on countably many generaots? Yet F[x,y]is relatively well-behaved.

on February 14, 2010 at 6:02 pm |Qiaochu YuanIt’s been pointed out to me that any uncountable group is uncountably generated, so maybe these aren’t the best reasons to think of a group as unmanageable. I guess subgroups of a group can be more complicated than the group itself. (There is an analogy to be made here to topological spaces: quotient spaces of a space can be more complicated than the original space.)

on February 15, 2010 at 8:50 am |Gary DavisYes, that I think is the, seemingly counter-intuitive, point: subgroups of even countable groups can be more, rather than less, complicated than the orginal group, as F[x,y] shows.

on February 27, 2014 at 8:46 pm |PennI realize this blog was posted 4 years ago, but I have come to the same conclusion. It’s a concept that’s extremely tough to formulate into words. On physics forums, I tried asking about constructing the set of all permutations of an uncountable group, namely, the real numbers, since . My question that no one on there seemed to grasp, but you do seem to grasp, is if an uncountable group cannot be “enumerated”, for lack of a better word, then how does one construct a well-defined permutation of this group? It makes absolutely no sense, especially if that group is complete, compact and connected, so that for all intensive purposes you cannot even distinguish between two points if they are close enough together. It doesn’t seem very natural to me. On top of this, when you think about it, in approximating the real numbers by some sequence of epsilon precisions greater than zero, for each member of this sequence, we are essentially approximating the real line by some countable group generated by this epsilon and it’s additive inverse, i.e. starting at zero and drawing line segments of length epsilon to both positive and negative infinity. When we say “for each epsilon greater than zero” we are essentially just taking the uncountable union of all of these countable groups. So, the set of all permutations of the real lines would have to be uncountably uncountable.

Actually, I think it stems from the fact that the natural numbers are inadequately defined. For example, multiplication is commutative on the natural numbers, and each natural has a unique prime factorization. But, there are no infinitely long natural numbers, for if I had a box containing all the prime numbers, and I chose one at random handing it to you to handle the commutativity part and form the prime factorization of some “number”, in theory, I could hand you a 2, then an infinite number of other primes before I handed you another 2, so how would you invoke commutativity on an infinite string of primes? Moreover, in some book on number theory, I think it was either Hardy or Apostol, it showed that the termination or periodicity in the decimal expansions of rational numbers with respect to some base is determined by the exponents of the remaining primes in the denominator after reducing and factoring out the base. By this reasoning, we should find that irrational numbers are really just ratios of infinite products of primes, so that the decimal expansion is actually cyclic, just infinitely so. This is actually a fact since for each real number we can create an infinite sum converging to said real number, each of whose terms in the rationals. Yet, in transforming such a sum into an infinite product, these infinite ratios are not in the rationals, since the numerator and denominator are not in the integers since they are not in the naturals since they are infinitely long. And also, in every single proof of irrationality I have ever seen, there is a deduction assuming “reducibility” or something logically equivalent to it. Now, “reducibility” in terms of the current definition of the rationals, therefore definition of the integers, therefore definition of the naturals, is well-defined, but on the other hand, how could one “reduce” an infinitely long product? You can only “reduce” if the infinite sequence of powers of the primes in both of these prime factorizations terminates, thus leaving you with the current definitions of the rationals as “reducible” and naturals as “countable”. There doesn’t seem to be any intuitive way to circumvent these inconveniences and expand these concepts either, so, like you, until there is, I don’t trust any uncountable set.

In other words, I believe that the inadequacy in the current definition of the naturals and everything that comes from them to be the fact that we expect them to be countable. I think this is just a property that some person came up with and then some other assumed to hold for the entire set of naturals. Likewise, with reducibility in the rationals.

Above all else, I think that in the current epsilon-delta approximations of analysis, the only thing guaranteed about the real numbers is an approximation to them by some countable group.