How can an infinite cosmos "expand"?

I get this question often, especially when I remind people that space has no substance of its own. That when we talk about cosmic expansion, we are literally talking about things flying apart. Space is not doing anything.

But, they ask, if space is infinite, what is it expanding into? How is "new space" created?

Well... that's not how it works. But infinity in mathematics is tricky business. So before I talk about the cosmos, allow me to bring up something much simpler: the number line.

The number line may be familiar from your school days. You know, a line on which we mark, say, all the (negative and positive) integers (doing some crude ASCII graphics here):

...--+----+----+----+----+----+----+----+----+----+----+--...
    -5   -4   -3   -2   -1    0    1    2    3    4    5

and of course on both ends, the number line stretches to infinity.

But now let me do something really evil. First, erase all the odd numbers:

...-------+---------+---------+---------+---------+-------...
         -4        -2         0         2         4

Next, replace whatever numbers remain by half their value:

...-------+---------+---------+---------+---------+-------...
         -2        -1         0         1         2

Again, the line stretches to infinity on both ends. So again, I have all the (negative and positive) integers marked. Same line, same set of points, yet their density has been cut in half.

The expansion of the cosmos is somewhat similar. For that, allow me to turn to a two-dimensional representation. Let's make the vertical axis time (increasing upward), the horizontal axis one of the spatial dimensions; just ignore the other two.

Now imagine the half-plane that is above the horizontal axis, with the horizontal axis itself not a part of it:

                              T
   ///// ** ///////////////   | //////// * ///////////////
   /////// ** /////////////   | /////// * ////////////////
   ///////// ** /////////// 2 + ////// * /////////////////
   /////////// ** /////////   | ///// * //////////////////
   ///////////// ** ///////   | //// * ///////////////////
   /////////////// ** /////   | /// * ////////////////////
   ///////////////// ** /// 1 + // * /////////////////////
   /////////////////// ** /   | / * //////////////////////
   ////////////////////// **  |  * ///////////////////////
   //////////////////////// **| * ////////////////////////
...-------+---------+---------+---------+---------+-------.. X
         -2        -1         0         1         2

So the universe is the area shaded with slash marks. I also marked two particle trajectories using stars, one going right, one going left but moving twice as fast.

 So here is the thing. Pick a time here on this chart. A time as close to 0 as you want, but still above the horizontal axis. Say, T = 1. Or T = 0.1. Or even T = 0.0000000001. Next, pick a point on the horizontal axis. Say, X = 1. Or X = 10. Or even X = 1,000,000,000.

 No matter how close you are to 0 on the T axis, and no matter how far you are from 0 on the X axis, it's still part of the cosmos. Say, the vertical axis marks years, the horizontal axis marks distance in light-years. You can pick T = 0.0000000316881 years (that is, 1 second) and you can pick X = 1 billion light years, and it's still part of the universe.

Not only that, but you can always find a particle trajectory that intersects the origin and follows a straight line to the point of your choice. It could be a very flat trajectory of course, corresponding to a very fast moving particle (NB: This model is not relativistic; relativistic equivalents exist but I didn't want to make things more confusing with conformal projections, time dilation and whatnot) but it is still there.

This is why we can make the following two, seemingly contradictory, yet general statements about an expanding, infinite cosmos:

1. No matter how far apart two things are today, we can always find a time early in the history of the cosmos when they were extremely close.
2. No matter how early a time in the history of the cosmos we pick, we can always find things that are already arbitrarily far away from each other at that time.

Lastly, when you think about it, the half-plane depicted in my crude ASCII diagram can be thought of as an infinite number of copies of the number line, stacked on top of each other. The higher up a copy of the number line is placed, the less dense it is. The lower in the stack the number line is, the denser the markings. But it is still always the same, infinite number line marked by the same numbers. Same infinite cosmos, same number of things in it, yet the density decreases with time.