`pageok`
`pageok`
`pageok`
Are There More Positive Rational Numbers than Positive Integers?

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):

1. Beyond Infinity:
2. Are There More Positive Rational Numbers than Positive Integers?
3. To Infinity, and Beyond:
Fitzwilliam_Darcy99:
I suppose that there's a reason why a post on elementary set theory is appropriate on this blog, but it eludes me what it is.

Coming soon: proof of the independence of the Axiom of Choice.
11.21.2007 6:53pm
John Armstrong (mail) (www):
Ahh, the guardian of "approved content" speaks up! I love it when your compatriots come over to my mathematical weblog and insinuate that I'm not allowed to muse on the Gunpowder Plot if the mood so strikes me.
11.21.2007 6:59pm
Eugene Volokh (www):
Fitzwilliam Darcy: Of course there's a reason -- I, the blogger, am interested in blogging about it! That is also why posts on language, song lyrics, puzzles, and whatever else we find interesting are appropriate on this blog.
11.21.2007 7:02pm
Curt Fischer:
How about this one: are there "more" points in a two-dimensional plane (described by a 2-vector of real numbers), or on a one-dimensional "line" (described by a single real number)?

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.
11.21.2007 7:40pm
John Armstrong (mail) (www):
And I can vouch that DFW's book is actually very accurate for a popular work.
11.21.2007 7:51pm
Drake (mail) (www):
"I, the blogger, am interested in blogging about it! That is also why posts on language, song lyrics, puzzles, and whatever else we find interesting are appropriate on this blog."

Positivist!
11.21.2007 8:42pm
Zathras (mail):
As far as the applicability of set theory to legal thought, take a look at Fletcher, Paradoxes in Legal Thought, 85 Colum. L.Rev. 1263-92 (1985), which discusses what Godel's Incompleteness Theorem says about jurisprudence.
11.21.2007 8:44pm
Zathras (mail):
This proof also works to show that the set of algebraic numbers is also countable (the same size as the integers). The algebraic numbers are those which are the solutions of a polynomial equation with rational coefficients. This allows you to include the square root of 2, the 6th root of 29911.125, etc.
11.21.2007 8:47pm
Math_Mage (mail):
Yah, infinities are fun to work with.

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?

=)
11.21.2007 8:48pm
Math_Mage (mail):
Ack, sorry for double post, but could you show that one/point to a proof, Zathras?
11.21.2007 8:53pm
Splunge:
The problem with this standard proof is that the definition of the size of the set does not correspond to what people intuitively mean by "size." I would suggest what we intuitively understand by "size" corresponds more with mole number, or volume, or mass, or some other measure of the extent of a physical body, because we understand every abstract concept ultimately in terms of some concrete realization, or actions upon or by same. From that point of view, the "size" of an infinite set is undefined, inasmuch as no concrete realization of one exists, or can exist.

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.
11.21.2007 9:14pm
Drake (mail) (www):
In all seriousness, I've always wondered: Would anything set-theoretically interesting come of construing the cardinality of denumerable sets in terms of a probability function? I'll try to explain what I mean with at least enough clarity to be wrong.

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.
11.21.2007 9:21pm
Zathras (mail):
Splunge: 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.
11.21.2007 9:37pm
Zathras (mail):
Drake, the tricky part to what you want to do is the definition of the f. The properties do not uniquely define f. Therefore, you can change its definition of so that you get a weight different from what might be intuitive. It would be interesting to see what additional properties f would have to have in order to match our intuition.
11.21.2007 9:40pm
Zathras (mail):
Math_Mage,

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.
11.21.2007 9:52pm
Zathras (mail):
Two last comments on the above proof.

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.
11.21.2007 9:57pm
pedro (mail):
There is a very nice description of a bijection between the natural numbers (including zero, of course) and the positive rational numbers.

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_+.
11.21.2007 10:48pm
pedro (mail):
Darn it. The (n+1)-times should refer to the number of copies of g in the definition of f(n). Somehow, the spaces I left when I wrote the comment disappeared. At any rate, one more comment. Eugene's map is not a bijection. If regarded as a map from N to Q_+, it fails to be injective, since 2/2 = 1/1 but 1 is not equal to 2, and if regarded as a going from Q_+ to N, it actually fails to be a function. It would have been better, in my humble opinion, to count the positive rationals in such a way as to skip already counted positive rationals.

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.
11.21.2007 11:09pm
pedro (mail):
Typo-fix: "If regarded as a map from N to Q_+, it fails to be injective, since 2/2 = 1/1 but 1 is not equal to 2" above should read "If regarded as a map from N to Q_+, it fails to be injective, since 2/2 = 1/1 but 1 is not equal to 5".
11.21.2007 11:11pm
nordsieck (mail) (www):
This proof seems quite suspect. There are an infinite number of rational numbers between any pair of integers. The converse is not true.
11.21.2007 11:13pm
MathLurker:
From a mathematician and frequent lurker to lazy to sign up for an account, a couple of points:

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?

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
11.22.2007 5:16am
When we've been there ten thousand years,
bright shining as the sun,
We've no less days to sing God's praise,
Than when we'd first begun.
11.22.2007 1:13pm
ck:
I'd appreciate it if someone could point out the flaw in this counterargument (I'm not a mathematician and I assume there is some flaw):

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.
11.22.2007 1:28pm
MathLurker:
ck:

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 to the 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.
11.22.2007 1:54pm
Gregory Conen (mail):
Yet another mapping is to let any rational number in base ten 123/789 map to the base 11 integer 123/789 with '/' representing 10.
11.24.2007 12:41pm
PKScott (mail):
Goodness gracious. In mathematics there are two sizes of infinite: countable and uncountable. If a set of infinite numbers can be mapped to the integers (i.e. is the same size) then it is countably infinite. The integers, positive integers, and rational numbers are countably infinite. Without detailed proof, the rationals are countably infinite because the can be represented as the ratio of integers. Uncountabily infinite sets are the real numbers and the set of irrational numbers (real numbers that can't be represented as the ratio of two integers).

I knew that course in topology would come in handy some day.
11.26.2007 12:23pm