I asked that near the end of my previous post; and the answer, counterintuitively, is that these two sets are also equally big. Remember that the standard definition we're working with is that two sets are equally big if there's a way of mapping each element of the first to precisely one element of the second. So here's the mapping, with the unbracketed item in each cell being a rational number (e.g., 2/3), and the bracketed item being the positive integer to which the mapping is being done. (To make it simple, I'll ignore the double counting that happens when some fractions equal some others that came before, for instance when we get to 2/2 and 3/3, which equal 1/1; to make it more precise, we can just skip over them.

1/1 [1] | 2/1 [2] | 3/1 [4] | 4/1 [7] | 5/1 [11] | 6/1 [16] ... |

1/2 [3] | 2/2 [5] | 3/2 [8] | 4/2 [12] | 5/2 [17] ... | |

1/3 [6] | 2/3 [9] | 3/3 [13] | 4/3 [18] ... | ||

1/4 [10] | 2/4 [14] | 3/4 [19] ... | |||

1/5 [15] | 2/5 [20] ... | ||||

1/6 [21] ... |

As you can see, if the rational numbers in the form p/q are organized in an infinite matrix, we can start counting by diagonals, and eventually get to any p/q you care to mention. So every positive rational number has precisely one positive integer to which it's mapped. And therefore the sets are equal in size.

If you want another mapping, try mapping any p/q (where p and q are relatively prime) to 2^p x 3^q; that maps the positive rationals to a subset of the positive integers. Of course, if you grasp why that works, you've probably learned the diagonals proof already.

Related Posts (on one page):

- Beyond Infinity:
- Are There More Positive Rational Numbers than Positive Integers?
- To Infinity, and Beyond:

Coming soon: proof of the independence of the Axiom of Choice.

The answer was every bit as mind blowing, if not more, than the riddles involving countably infinite sets that Eugene has already blogged.

If you enjoy this stuff, you should read Everything and More by the novelist David Foster Wallace, a literary type who did his best to understand the and explicate the history of the infinite in a pop-science format.

Positivist!

Paradoxes in Legal Thought, 85 Colum. L.Rev. 1263-92 (1985), which discusses what Godel's Incompleteness Theorem says about jurisprudence.By the way, though there are as many integers as rational numbers, there are more REAL numbers than integers. Proof by contradiction:

1. Assume that real numbers and integers are equally infinite; that is, that for every real number there is an integer, and vice versa.

2. Therefore, you can write a list of the real numbers. So envision two columns, one with the list of integers, another with the list of real numbers, thus:

1 : .000054586...

2 : .583959603...

3 : .141592654...

and so on.

3. Now, we're going to construct a number that's not in this list. Ignore the integer part of the number; the key is in the part after the decimal point. Choose a non-zero digit for the tenths place that differs from the number in the tenths place of the first real number in the list. Then choose a non-zero digit for the hundredths place that differs from the number in the hundredths place of the second real number in the list. Then choose a non-zero digit for the thousandths place that differs from the thousandths place of the third real number of the list. Keep going until you've gone through the whole list.

4. This number cannot be found anywhere in the list by definition; however, one of the implications of having real numbers be as numerous as integers is that there must be an integer for every real number, and vice versa. Therefore, that assumption must be incorrect, and there are more real numbers than integers.

There's some kinks that have to be worked out of this proof, like making sure that you don't end up with an infinite sequence of 9's, but that's the nuts and bolts of it.

Now, the million-dollar question (literally, there's a prize out): Is there an infinity smaller than the infinity of real numbers, but larger than the infinity of integers?

=)

Hence the surprise of the result is a bit of cheat. It comes not from some truly counter-intuitive property of infinite sets but from an implicit confusion of definitions: the mathematician is using the mathy definition, while the listener is using the intuitive definition.

In standard set theory, the cardinality of the set of primes = that of the set of rationals = that of the algebraic numbers = etc. = aleph zero. Intuitively, though, a set of cardinality aleph zero that is a proper subset of another set with cardinality aleph zero is in some sense "smaller." This is why Cantor's proof is so surprising.

But it seems our contra-Cantorean intuition could be given formal content as follows: Assume A is a proper subset of B, and that both are denumerable. Now suppose we have a randomizing function f that assigns to any given argument drawn from a set an arbitrary output drawn from the same set. The probability that f will yield an element from A when run over A, then, is obviously higher than that it will yield an element in common with A when run over B, because B contains all the elements A does, plus others that A does not. Thus, A has a lower "cardinality" (in my hypothetical, extended sense) than B.

So, for example, the likelihood, say, of f's calling up a prime number is higher over the set of all odd integers (call this set A) than it is over the set of all odd integers plus all even integers (call this set B). A thus has lower "cardinality" than B -- which matches our intuition that, in some sense, there are "more" elements in the set of all integers than there are in just the set of all odd integers.

Again, I'm not sure that the idea is coherent, and if it is whether it would even matter. Just thought I'd throw it out there for more competent disposal.

Hence the surprise of the result is a bit of cheat. It comes not from some truly counter-intuitive property of infinite sets but from an implicit confusion of definitions....In terms of mathematics, you just said the same thing twice. Properties are implied by definitions, and giving something different properties necessarily means it has a different definition.

Here is the basic idea,

Start with linear polynomials. The only root of a linear polynomial is a single rational number, and the set of the rationals is as given above countable.

Go next to quadratic polynomials. All solutions look like a + sqrt(b), where a and b are rational. Align all possible a's and b's in an array as above, and this shows that the set of quadratic roots is countable. You can extend this to as many degrees as you want. It helps also to know that a countable collection of countable sets is also countable.

I know this is a bit of hand-waving, but this is the best I can do on the fly. Also, having been an attorney came close destroying my interest in rigorous proofs (as well as enhanced my interest in hand-waving arguments), but that is another topic for another day.

1) The fact that the algebraic numbers are countable (while the reals are not) implies the existence of the transcendental numbers, which cannot be described by any polynomial equation.

2) While the set of solutions to polynomials with rational coefficients is countable, the set of solutions to power series with rational coefficients is not countable.

Notation: (1) Let [x] denote the floor of x, i.e. the largest integer that is less than or equal to x.

(2) By f o g we mean the composition of g with f. So (f o g)(x) = f(g(x)) for all x.

(3) Let R, Q_+, and N denote the sets of real numbers, positive rational numbers, and natural numbers, respectively.

Consider the function g: R --> R defined by

g(x) = 1/(1 + 2[x] - x).

Define f: N --> Q_+ by

f(n) = (g o g o ... o g)(0).

\------\/-------/

(n+1)-times

Exercise: Prove that f is a bijection between N and Q_+.

Eugene's map is a surjection from N to Q_+, and so one may conclude, naively (but not incorrectly) that the quantity of positive rationals is less than or equal to the quantity of natural numbers. It is pretty obvious that there is also a surjection from Q_+ to N: for example, the function that sends any natural number to itself, and which sends any positive rational that is not a natural number to zero. So, again, naively, we can say that the quantity of natural numbers is less than or equal to the quantity of positive rationals.

But then there's the question of whether we can really quantify infinite sets like this, i.e. by saying that the quantity of a set A (or the cardinality of a set, to speak more properly) is less than or equal to the quantity of another set B if there is a surjection from B to A.

In other words, we must provide justification for thinking that what I naively called "quantities" in the paragraph above in reference to infinite sets, are arranged in a total ordering like that of finite quantities. More precisely, for finite numbers, we know the following to be true: if m is less than or equal to n and n is less than or equal to m, then m is equal to n. Is it the case that if there exists a surjection from A to B, and there exists a surjection from B to A, then there exists a bijection between A and B? This is the crux of the matter, for a bijection is what ultimately establishes whether two sets have the same quantity of elements.

The answer is yes, but it is not at all trivial, and that is why I think Eugene's choice of function is not ideal, but I guess I'm being a bit pedantic.

Math_Mage: You ask

This is not one of the million dollar questions. (See the Clay Math site for the list). In fact, Goedel and Cohen showed that the answer to this question cannot be determined using the standard axioms of mathematics. Recently, Woodin has put forth arguments for an enhanced set of axioms which allow one to determine that the answer to the question is "no". As far as I know, there is not yet consensus among the experts in this area that this enhanced set of axioms should be adopted. (Messing with the fundamentals on which of all of modern mathematics is based is something of a tough sell.) See "Continuum hypothesis" on wikipedia for more.

nordsieck: Yes, the conclusion seems quite surprising. The point of the proof is that when you start messing around with infinite quantities, you sometimes get surprising results. The place we have chosen to start is essentially the following: Given a set, you cannot change its cardinality by giving all the elements different names (mathematicians essentially take this property as the definition of cardinality). Once you accept that, enough staring at Eugene's proof (or pedro's, if you wish to be more precise) should convince you that all that's happening whilst going from the rationals to the natural numbers is a renaming process.

-Jason

bright shining as the sun,

We've no less days to sing God's praise,

Than when we'd first begun.

For each natural number n > 2, there is a corresponding rational number n/n-1. Since n and n-1 are always relatively prime, all of these rationals are distinct and are not integers. So there is a one-to-one mapping between naturals and this subset of the rationals. But, there are also other rational numbers not in this set (e.g., 3/7 or 7/3, or any other pair of relatively prime integers). Thus, the set of all rationals must be larger than the set of all integers.

Two points: First, you seem to be concerned with the set of rationals which are not natural numbers. But that is not what we are concerned with here. (n/1) is a perfectly fine natural number. That doesn't answer your question, but it does mean that you could just as well have sent the natural number n to the rational number (n/1) and asked the same question.

To answer what you asked, consider the following argument. For each natural number n, there is a corresponding natural number 2n. The numbers of the form 2n are all distinct natural numbers (the even ones). So, there is a one-to-one mapping between naturals and this subset of the naturals we call the even numbers. But there are also natural numbers not in this set (the odds). Thus the set of all natural numbers must be larger than the set of all natural numbers.

Hopefully you agree that there is a flaw in the argument above. It is arguments like this that have lead mathematicians to agree on definitions that are equivalent to the following statement:

Given a set X and a set Y, a one-to-one mapping from X to Y (or a subset of Y) shows that the cardinality of X is less than

or equal tothe cardinality of Y. If a one-to-one mapping from Y to X (or a subset of X) exists, the two cardinalities are equal (informally, the two sets have the same size).So, you showed that the cardinality of the naturals is less than or equal to the cardinality of the rationals. In his post, Eugene showed the cardinality of the rationals is less than or equal to the cardinality of the naturals. Thus the two cardinalities are equal.

I knew that course in topology would come in handy some day.