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 
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 
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
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?
My 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.
Yeah, 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.
If 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.
Any 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).
Yes, 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.
I’m with Qiaochu here. I guess this is the kind of feeling that separates the combinatorialists from the non-combinatorialists.
I’m weird. I agree:
is not to be trusted. Of course, my solution? Go to 
, which is a perfectly trustworthy thing.
The 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…
Yes, 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.
I’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.
1) 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.
Do you have a reference describing the countable model of the reals? This model theory stuff is very philosophically interesting.
Any 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.
So I guess what I really should’ve said is “I don’t trust second-order logic.”
I 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.
For (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.
Is it just a freaky coincidence I said something similar the same day?
http://leakyninja.blogspot.com/2009/11/real-numbers-unreal.html
Doesn’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.
It’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.)
Yes, 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.