I’m familiar with the diagonal argument, and I understand why the set of points in a line segment is of greater cardinality than the set of natural numbers. But is there a simple or intuitive reason why the number of points in a segment is of the same cardinality as the number of points on the real number line?
One thing that might make it intuitive is that there are functions that map an interval to the real number line. For example, the trigonometric function tan maps the interval (-pi/2,+pi/2) to the real number line, and has an inverse function. That proves that there are the same number of points on the interval as on the whole line.
To make it simple, consider one specific case:
Take the open interval (0, 1) (that is, all numbers from 0 to 1 NOT including the endpoints 0 and 1), and the open-ended infinite interval (0, inf) (again, NOT including the end-point 0).
It’s easy to develop a function that maps any real number in (0, 1) to some real in (0, inf). And the function is invertible, meaning the correspondence works exactly in the other direction too. Once you’ve done this, you have your one-to-one mapping between the two sets, thus showing that they are of the same cardinality.
To map a number x in (0, 1) to (0, inf): Take the reciprocal of x (giving a number in (1, inf)) and subtract 1 (giving a number in (0, inf)). That is, y = 1/x - 1
To map a number y in (0, inf) to (0, 1): Do the reverse: Add 1 (giving a number in (1, inf)) then take the reciprocal of that (giving a number in (0, 1)). That is, x = 1/(y+1)
With just a little ingenuity, you can create a similar mapping between any open interval (m, n) and (0, inf). With just a bit more ingenuity, you can extend the mapping so it maps (m, n) to (-inf, +inf).
Getting it to work when you include the end-points of the interval [m, n] may take a bit more work. At this hour of the morning, I’m not prepared to think about that just now.
The easy way to see this is to look at the graph of the tangent function mentioned above. See how the line goes nearly vertical at some points, both upwards and downwards? It’s going to infinity. If you follow that line along the x axis, you can go as high as you want up into the positive y axis in one direction, and as low as you want down into the negative y axis in the other. It never stops; that’s an example of an asymptote (in this case, a vertical asymptote).
The point about it being a bijection is important as well: Within any section of the tangent function, any single piece of the graph between asymptotes, you can map every unique x value found between the asymptotes to a unique y value and vice-versa.
And there, of course, is the magic: The region of the x axis between the asymptotes is just a tiny fraction of the real line, but the nature of a vertical asymptote is that the y values go to infinity. Since every section of the tangent function goes both positive (at one end) and negative (at the other) when encountering an asymptote, that means we’ve just mapped the entire real line (y axis) to a section of the real line (x axis).
Here’s a Java applet that lets you play with the tangent function. You can, in fact, make the sections between asymptotes as narrow as you want.
Here is a simple geometric argument. Imagine the open interval (-pi/2,pi/2) bent into a half circle of radius 1 centered at the point with coordinates (0,1). (Careful how the two uses of ( , ) conflict with each other.) Now each ray from the center of the circle meets the x-axis in exactly one point and sets up a 1-1 correspondence between that interval and the whole line. There is nothing special about that interval; anyone will do.
The tangent function isn’t the only function that does this, of course. Another function that maps an interval to all the real numbers is f(x) = x/(1 - x[sup]2[/sup]), which maps (-1, +1) to (-∞,+∞).
I’m missing something here.
It looks like EVERY example of a mapping shown in this thread so far (including my own example several posts above) will map an OPEN interval (not including its end-points), such as (0, 1) onto the real numbers (-∞,+∞).
If you try to map a closed interval, such as [0, 1] (including its end-points) to (-∞,+∞), none of these examples seem to work – the end-points don’t get mapped anywhere. I noted this myself in my earlier post.
How can you develop a mapping between a CLOSED interval and (-∞,+∞), that will work?
It has to be discontinuous. On the real line, any closed interval is compact, and compactness is preserved by continuous mappings. The real line is not compact, so it’s not the image of any closed interval under any continuous function.
As ultrafilter says, there’s no nice (i.e., continuous) bijection between the closed interval [0, 1] and the entire real line (equivalently, between the closed interval [0, 1] and the open interval (0, 1)). [In fact, in intuitionistic mathematics, one cannot prove that [0, 1] and (0, 1) have the same cardinality (intuitionistic mathematics is consistent with the principle that all functions from reals to reals are continuous).]
To show the equicardinality of open and closed intervals, you use something like the Cantor-Schroeder-Bernstein argument: it’s easy to see that each can be made to inject into the other, and from this a (discontinuous) bijection can be produced.
For example, one can put [-1, 1] and (-1, 1) in bijection as follows: let’s say a point is “ugly” if it is of the form 1/2[sup]n[/sup] or -1/2[sup]n[/sup]. Let f(x) be the map from [-1, 1] to (-1, 1) which is identity on non-“ugly” points, and which divides by 2 on “ugly” points. This will set up a bijection between a closed and an open interval.
I have only a passing familiarity with intuitionistic math, but surely this should be all bijective functions or some similar modifier, since it’s trivially easy to come up with functions with discontinuities otherwise.
It’s trivially easy in classical mathematics. But not in intuitionistic mathematics (in which the excluded middle “No matter what, either P(x) or NOT P(x) holds” is not always available).
For example, one “trivial” example of a discontinuous function is the function defined such that f(0) = 1 and f(x) = 0 for x not equal to 0. But intuitionistically, this is not a totally defined function: one has only given it values on those x which either are or are not equal to 0. Without the law of the excluded middle, this needn’t cover all the reals; thus, this putative definition of f needn’t actually give a full-fledged function from reals to reals. So one can still go ahead and consistently adopt the principle that all functions from reals to reals are continuous, accepting the consequence that not all reals either are or are not equal to 0.
Aha! I think I see what you’re doing there.
Let me paraphrase the underlying strategy in plain English, to see if I’ve got the right concept:
From the set of reals [-1, 1] you’ve selected a countable-infinite subset of discrete points (your “ugly” ducklings). For all the others, the mapping is just f(x)=x. For the discrete “ugly” points, you’ve done substantially the same trick as mapping all integers -> even integers to show the 1-to-1 mapping there.
ETA: Or maybe I should have said: …substantially the same trick as mapping all non-negative integers {0, 1, 2, 3, …} to all positive integers {1, 2, 3, 4, …} to show the 1-to-1 mapping there.
More precisely, there’s a one-to-one mapping from the ugly points to the ugly points in the interior of the interval.
Yup, that’s right.
Well, then, obviously a line segment has two more points than the line!
That is, each “ugly” point is mapped to the next-one-over, towards the interior, which is something you can do with countable discrete points. The end-points can thus get mapped to something, and the displaced interior points each still have a next-one-over to get mapped to. Ah, the mysteries of the infinite!
BTW, I’m not familiar with the term “bijection” except for seeing it used here and in other similar threads (like that one last week). Is “bijection” just a synonym for “one-to-one mapping of two sets” ?
Yes, in the sense of “one-to-one” as meaning both injective and surjective. (But beware, “one-to-one” is also often used to mean just injective)
In other words, a bijection is a function with an inverse. In contexts other than set theory, it’s what would be called an isomorphism.
Yes, specifically, a bijection is some kind of mapping that maps every element of one set A exactly one element of another set B and vice-versa. (Which implies that the sets have to be the same size.)
Like wow, I think my mind is being injected into the complex plane a little bit here.
So youse guys are saying (and I just went and read some Wikis too), that “one-to-one mapping” doesn’t always mean, like, you know, “one-to-one mapping” as I’ve always thought I knew it?
I always thought 1-to-1 meant exactly: “For every x in X there corresponds exactly one y in Y and for every y in Y there corresponds exactly one x in X”. Now I’m learning that the phrase “1-to-1” doesn’t mean quite that?
(Anyway, I hope this thread constitutes the “simple or intuitive” explanation Reyemile was looking for.)