Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been told that there are precisely the same number of rationals as there are of integers. The set of rationals is countably infinite, therefore every rational can be associated with a positive integer, therefore there are the same number of rationals as integers. I've ignored sign-related issues, but these are easily handled.

To count the rationals, consider sets of rationals where the denominator and numerator are positive and sum to some constant. If the constant is 2 there's 1/1. If the constant is 3, there's 1/2 and 2/1. If the constant is 4 there's 1/3, 2/2 and 3/1. So far we have counted out 6 rationals, and if we continue long enough, we will eventually count to any specific rational you care to mention.

The trouble is, I find this very hard to accept. I have two reasons. First, this logic seems to assume that infinity is a finite number. You can count to and number any rational, but you cannot number all rationals. You can't even count all positive integers. Infinity is code for "no matter how far you count, you have never counted enough". If it were possible to count to infinity, it would be possible to count one step less and stop at count infinity-1 which must be different to infinity.

The second reason is that it's very easy to construct alternative mappings. Between zero and one there are infinitely many rational numbers, between one and two there are infinitely many rational numbers, and so on. To me, this seems a much more reasonable approach, implying that there are infinite rational numbers for every integer.

But even then, this is just one of many alternative ways to map between ranges of rationals and ranges of integers. Since you can count the rationals, you can equally count stepping by any amount for each rational. You can use 1..10 for the first rational and 11..20 for the second etc. Or 1..100 and 101..200 etc, or 1..1000 and 1001..2000 etc. You can map finite range of integers of any size to each rational this way and, since there is no finite upper bound to the stepping amount, you could argue there are potentially infinite integers for every single rational.

So... can anyone convince me that there is a single unambiguous correct answer to this question? Are there more rational numbers than integers, or not?

EDIT

Although I've already accepted an answer, I'll just add some extra context.

My reason for questioning this relates to the Hilbert space-filling curve. I find this interesting because of applications to multi-dimensional indexing data structures in software. However, I found Hilberts claim that the Hilbert curve literally filled a multi-dimensional space hard to accept.

As mentioned in a comment below, a one meter line segment and a two meter line segment can both be seen as sets of points and, but (by the logic in answers below), those two sets are both the same size (cardinality). Yet we would not claim the two line segments are both the same size. The lengths are finite and different. Going beyond this, we most certainly wouldn't claim that the size of any finite straight line segment is equal to the size of a one-meter-by-one-meter square.

The Hilbert curve reasoning makes sense now - the set of points in the curve is equal to the set of points in the space it fills. Previously, I was thinking too much about basic geometry, and couldn't accept the size of a curve as being equal to the size of a space. However, this isn't based on a fallacious counting-to-infinity argument - it's a necessary consequence of an alternative line of reasoning. The two constructs are equal because they both represent the same set of points. The area/volume/etc of the curve follows from that.

share|improve this question
4  
Second to last paragraph: you can also argue that there are potentially infinite integers for every single integer. –  Qiaochu Yuan Jul 31 '10 at 20:17
    
@Qiaochu Yuan - that had occured to me, but I thought trying to argue that there are more integers than integers or visa versa was well down the road to insanity ;-) –  Steve314 Jul 31 '10 at 20:51
1  
Re edit: There's a confusion here between two distinct concepts of cardinality and measure. The cardinality of the set of points on a one-metre line segment and on a two-metre line is the same, but they have different measure (length, in this case). Similarly, the Hilbert space-filling curve fills all the points, but being a curve, it has measure 0 relative to the square it fills (it has length, but no area). The confusion arises because "size" is used loosely to refer to either concept. –  ShreevatsaR Jul 31 '10 at 21:32
    
@ShreevatsaR - yes, that's my point. Why should "size" mean "cardinality of the set"? Simple answer - it's the only way to get a meaningful answer. But if you approach the issue worrying about curves and areas, it's hard not to see a different sense of the word "size". –  Steve314 Jul 31 '10 at 21:45
    
You may find helpful some of the answers to the similar question math.stackexchange.com/questions/398 –  Noah Snyder Apr 11 '13 at 0:48
show 1 more comment

7 Answers

up vote 16 down vote accepted

Mathematicians have very precise definitions for terms like "infinite" and "same size". The single unambiguous correct answer to this question is that using the standard mathematical definitions, the rationals have the "same size" as the integers.

First, here are the definitions:

  1. Define "0" = emptyset, "1" = {0}, "2" = {0,1}, "3" = {0,1,2}, etc. So, the number "n" is really a set with "n" elements in it.

  2. A set A is called "finite" iff there is some n and a function f:A->n which is bijective.

  3. A set A is called "infinite" iff it is not finite. (Note that this notion says nothing about "counting never stops" or anything like that.)

  4. Two sets A and B are said to have the "same size" if there is a some function f:A-> B which is a bijection. Note that we do NOT require that ALL functions be bijections, just that there is SOME bijection.

Once one accepts these definitions, one can prove that the rationals and integers have the same size. One just needs to find a particular bijection between the two sets. If you don't like the one you mentioned in your post, may I suggest that Calkin-Wilf enumeration of the rationals? (Simply google search Calkin Wilf counting rationals. The first .pdf has what I'm talking about).

Of course, these give bijections between the naturals (with out 0) and the rationals, but once you have a bijection like this, it's easy to construct a bijection from the integers to the rationals by composing with a bijection from the naturals to the integers.

share|improve this answer
1  
Excellent answer. I hadn't really considered that this was set theory (someone else added that tag). Now, I can see that this is the only way to interpret relative "size" that makes sense in this context. Thanks. –  Steve314 Jul 31 '10 at 20:08
    
My last class in math was in the German high school equivalent, 37 years ago, so I'm a bit rusty ;-) -- However I found Jason's explanation convincing for me. -- Now I've got this idea: could one apply a concept of "density" upon both sets of numbers (integers and rationals) and somehow proof that "while both are of same size, the rationals have a higher density " ? [Of course it would all depend on a stringent definition for "density"... but maybe such a thing/concept/idea already exists in math and number theory?? -- I would be interested to know if that is the case. –  Kurt Pfeifle Jul 31 '10 at 21:08
2  
Sure. One can study the topology of the rational numbers and the integers as subsets of the real line, and they are very different. The rational numbers are, in the technical sense, dense (their closure is R), and the integers are discrete. That's one sense in which the rationals are more dense than the integers. –  Qiaochu Yuan Aug 1 '10 at 5:21
    
Another interpretation of density might be Lebesgue measure. Funnily enough, the integers and the rationals both have measure zero, as does any countable subset of R. –  Qiaochu Yuan Aug 1 '10 at 5:22
2  
I think one of the main difficulties here is that there are many notions of "size". Off the top of my head, there are the number of elements of a set, the measure as a subset of R^n, and whether or not something has high density. The problem is that mathematically, all 3 of these concepts diverge, while our everyday experience (or at least mine) tells us the 3 should be (roughly) the same. –  Jason DeVito Aug 1 '10 at 18:18
show 2 more comments

I don't know why cardinality even exists but here is how it goes. Positive integers are the smallest of all the sets. Add 0 and you get a slightly larger infinite set. Add negative integer and you get an infinitely larger infinite set. These are all countable. There are however infinite rational numbers between rationals and so on and so forth. They are uncountable. Heres why. Take a certain list of decimals that either repeat or terminate. Add them all or subtract them all or something and you get something that wasn't listed. You cannot list all the fractions even with a ... to show it goes infinitely far. Add irrational numbers and you have all the real numbers which you can't list either. Add complex numbers, even larger infinity. Than hyperreals and surreals and hypercomplex numbers like split octonians and it is infinitely larger. That proves my ∞ inside ∞ inside ∞... hypothesis.

share|improve this answer
    
The rationals are countable. Perhaps you meant to refer to the uncountable number of reals in any finite interval $[a,b],a\neq b$? –  abiessu Mar 3 at 19:10
    
no the rationals are not countable because you cannot list all rational numbers. Doing operations with rational numbers gives you a rational number that was not even in the list. That is why they are uncountable. –  caters Mar 3 at 20:24
    
another reason is infinitely many rationals between 2 rationals. –  caters Mar 3 at 20:24
    
@caters - I think you're confusing "countable" with "finite". Countable means you can think of a scheme for counting that theoretically counts all of them - it doesn't mean the process of counting them has to be achievable. As for doing operations with rationals - actually, rationals are closed over all arithmetic operations, excluding division by zero of course. If start with a counted sequence of rationals 1..n, operations may result in rationals with a count larger than n, but that's just it - rationals are a countably infinite set. There's no requirement for any finite subset to be closed. –  Steve314 Mar 4 at 0:34
    
@caters - usual counting system for positive rationals - 0/1, 1/1, 2/1, 1/2, 3/1, 1/3, 4/1, 3/2, 2/3, 1/4, ... - all the rationals with numerator+denominator=1, then those with numerator+denominator=2, then those with numerator+denominator=3 and so on, but excluding those that are equivalent to rationals already counted. You can count as far as you want, though you can never finish counting - just like counting positive integers. To include negative rationals, just alternate positive then negative in the counting sequence. –  Steve314 Mar 4 at 0:40
show 2 more comments

since one can construct the rationals from a ratio of integers, from here one will see that will be more rational numbers than integers (There are more 'options' to form numbers since it is a fraction two integers, except an integer over zero). Likewise I suspect that natural numbers have a smaller count than the integers since you can construct the integers from using natural numbers and -1*natural numbers along with zero. correct me if i'm wrong but i think this is all valid

share|improve this answer
2  
You are wrong. Did you read any of the answers that were already posted? Did you read the Wikipedia article on countable sets? Or the Wikipedia article on cardinality for that matter? –  Zev Chonoles Apr 11 '13 at 0:43
    
I like the two dimensions/two degrees of freedom argument, but it's really the same thing I was thinking about when I revisited this. On the one hand, two dimensions/degrees of freedom needn't give more meaningful choice. Consider the ratio of two reals - you still have two degrees of freedom, yet the result is always a real (unless the denominator is zero). You don't get more values - the apparent extra choice is an illusion. –  Steve314 Apr 11 '13 at 1:24
    
Starting from integers, your extra degree of freedom can derive new values - but that's just saying that the set of rationals is a strict superset of the set of integers. That gives a sense in which the set of rationals is larger, but that sense is not the same as set cardinality - the two versions of size are equivalent for finite sets, but not (at least in general) for infinite sets. The strict-superset ordering isn't even fully defined, and as most mathematicians consider "size" and "cardinality" synonyms, using "size" for something else causes confusion and grumpiness. –  Steve314 Apr 11 '13 at 1:25
add comment

You may not be very satisfied with this answer, but I'll try to explain anyway.

Countability. We're not really talking about whether you can "count all of the rationals", using some finite process. Obviously, if there is an infinite number of elements, you cannot count them in a finite amount of time using any reasonable process. The question is whether there is the same number of rationals as there are positive integers; this is what it means for a set to be "countable" --- for there to exist a one-to-one mapping from the positive integers to the set in question. You have described such a mapping, and therefore the rationals are "countable". (You may disagree with the terminology, but this does not affect whether the concept that it labels is coherent.)

Alternative mappings. You seem to be dissatisfied with the fact that, unlike the case of a finite set, you can define an injection from the natural numbers to the rationals which is not surjective --- that you can in fact define a more general relation in which each integer is related to infinitely many rationals, but no two integers are related to the same rational numbers. Well, two can play at that game: you can define a relation in which every rational number is related to infinitely many integers, and no two rationals are related to the same integers! Just define the relation that each positive rational a/b is related to all numbers which are divisible by 2a but not 2a+1, and by 3b but not 3b+1; or more generally respectively 2ka and 3kb for any positive integer k. (There are, as you say, sign issues, but these can be smoothed away.)

You might complain that the relation I've defined isn't "natural". Perhaps you have in mind the fact that the integers are a subset of the rationals --- a subgroup, in fact, taking both of them as additive groups --- and that the factor group ℚ/ℤ is infinite. Well, this is definitely interesting, and it's a natural sort of structure to be interested in. But it's more than what the issue of "mere cardinality" is trying to get at: set theory is interested in size regardless of structure, and so we don't restrict to maps which have one or another kind of "naturalness" about them. Of course, if you are interested in mappings which respect some sort of structure, you can build theories of size based on that: this is what is done in measure theory (with measure), linear algebra (with dimension), and indeed group theory (with index). So if you don't like cardinality as set theorists conceive it, you can look at more structured measures of size that you find more interesting!

Immediate predecessors. A somewhat unrelated (but still important) complaint that you make is this: "If it were possible to count to infinity, it would be possible to count one step less and stop at count infinity-1 which must be different to infinity." The question is: why would you necessarily be able to stop at 'infinity minus one'? This is true for finite collections, but it does not necessarily hold that anything which is true of finite collections is true also for infinite ones. (In fact, obviously, some things necessarily will fail.) --- This is important if you study ordinals, which mirrors the process of counting itself in some ways (labelling things as being "first", "second", "third", and so forth), because of the concept of a limit ordinal: the first "infinitieth" element of a well-ordering doesn't have any immediate predecessors! Again, you are free to say that these are concepts that you are not interested in exploring personally, but this does not mean that they are necessarily incoherent.

To summarize: the set theorists measure "the size of a set" using a simple definition which doesn't care about structure, and which may violate your intuitions if you like to take the structure of the integers (and the rational numbers) very seriously, and also want to preserve your intuitions about finite sets. There are two solutions to this: try to stretch your intuition to accomodate the ideas of the set theorists, or study a different branch of math which you find more interesting!

share|improve this answer
    
On the "alternative mappings" I gave extremes in both directions - one rational to many integers as well as the other way around. On predecessors, I'm basically restating the classic argument for why infinity is not a number - ie because it doesn't behave as a number. As for your implication that I'm not up to handling set theory - I've coped with it perfectly well when I've needed to. In this case, I didn't realise I was dealing with set theory. BTW - at 39 years old, I am not looking to study anything formally. Don't assume everyone who asks about math is a student please. –  Steve314 Jul 31 '10 at 20:43
    
(1) Whoa man, I never said you're "not up to handling set theory" --- I just suggested that if you find their definitions to be not the ones you care about, there are other areas. I have basically this attitude towards higher cardinalities myself: I understand them, I'm just not sure why we should care, when we can't even prove whether or not the continuum is the smallest uncountable cardinal. (2) It really depends on what you mean by "a number"; why should that property be necessary? (3) I only wrote my answer based on your question, which was typical of students learning about cardinality. –  Niel de Beaudrap Jul 31 '10 at 21:32
    
OK, sorry for the oversensitivity there. In my case, I suspect my confusion is typical of programmers who only occasionally worry about computer science and math. Set theory is OK, but I don't remember the details off the top of my head, and in general I don't need to deal with the infinite. Even the cardinality of the set of integers is usually, to me, a little over 4 billion. –  Steve314 Jul 31 '10 at 21:49
add comment

In mathematics a set is called infinite if it can be put into a 1-1 correspondence with a proper subset of it, and finite it is not infinite. (I know it seems crazy to have the concept of infinite as primitive and finite as a derivate, but it's simpler to do this, since otherwise you must assume that the integers exist before saying that a set is finite)

As for your remarks: - with your method (if you don't forget to throw out fractions like 4/6 which is equal to 2/3) you actually counted the rationals, since for each number you have a function which associates it to a natural number. It's true that you cannot count ALL rationals, or all integers; but you cannot either draw a whole straight line, can you? - with infinite sets you may build infinite mappings, but you just need a single 1-1 mapping to show that two sets are equal.

share|improve this answer
    
The straight line argument is significant. I cannot draw a 1 meter line segment by plotting a finite number of points, and the same for a 2 meter line segment. The cardinalities of the sets of points for these two lines I can (now, given other answers here) accept as equal. However, very few people would argue that the size of a 1 meter line segment is equal to the size of a 2 meter line segment. This isn't irrelevant since a co-ordinate system is simply a bijection of number-tuples to points in some space. There's more than one meaning of "size" IOW, but only one can answer my question. –  Steve314 Jul 31 '10 at 20:32
    
size matters :-), but I was thinking of an infinite straight line. –  mau Jul 31 '10 at 20:44
    
that's why I specifically said "line segment". –  Steve314 Jul 31 '10 at 20:46
add comment

The cardinality of the set of rationals is the same as the cardinality of the integers is the same as the cardinality of the natural numbers.

When we count a finite set of elements, we are constructing a one-one map from the set onto a finite initial segment of the natural numbers. If we want to know if two finite sets have the same cardinality (are equi-cardinal) we can either: 1) count both sets and see if we get the same number, or 2) attempt to construct a one-one map from one set onto the other. If we can construct the map aimed at in (2), then the sets are equi-cardinal.

Generalizing that procedure from the finite sets to arbitrary sets, we get that for any two sets, the sets have the same cardinality (are equi-cardinal) if there exists a bijection (a one-one map between the sets that is onto the target rather than merely into). For the finite case, if there is a one-one map that is a bijection, all one-one maps are bijective. That is not the case for infinite sets, which is the root of your second concern.

To address that second concern, consider the map from the negative integers to the positive integers which maps each negative integer to its absolute value. The existence of that map shows that the two sets are equi-cardinal. We can, of course, construct one-one maps from the negative integers to the positive integers that are into rather than on to. (Consider the map that takes each negative integer to its product with -2.) But, the existence of these alternative maps doesn't affect the fact that there is at least one bijection between the sets, and that is all it takes for those sets to be equi-cardinal.

As for your first concern, I don't see why you think the procedure assumes that "infinity is a finite number". What it involves is specifying a mapping function from one set to the other that is one-one and onto. That attempt can certainly fail, as Cantor's Diagonalization Argument that the cardinality of a set is always strictly less than the cardinality of its power set shows. (A relevant application of that technique is the well-known proof that the cardinality of the reals is greater than the cardinality of the natural numbers.)

share|improve this answer
    
My concern about infinity was that it seemed to me that you could only justify one particular bijection as "the" bijection if there were a finite number of items in each set. If you can't count them all, you can't show that the last from one set maps to the last one from the other set. I guess it's really not a separate reason, but just an aspect of my "but there are other bijections" fallacy. –  Steve314 Jul 31 '10 at 20:23
    
Actually, there being other bijections isn't a fallacy. Each one-to-one mapping implies the cardinalities are the same. There would only be a problem if you insisted that the existence of other kinds of injections, other than the bijections, was an issue. –  Niel de Beaudrap Aug 1 '10 at 4:20
add comment

You can think about it a different way. Consider the set of real numbers between 0 and 1, and then the set of real numbers between 0 and 2.

By intuition, it seems that the set of real numbers between 0 and 2 has double the size of the set between 0 and 1. However, this is not the case, because the two sets have the same cardinality.

Consider the function $f(x) = 2x$. Every real between 0 and 1 is bijected to a real between 0 and 2. Therefore the sets are of the same size.

share|improve this answer
    
This in itself isn't convincing. There are alternative bijections, therefore it looks ambiguous at best. And the word "cardinality" is just a word - naming something doesn't make logical difficulties go away. Jason DeVitos answer was better - it's a consequence of the definition of "size" used, in which the existence of any bijection is sufficient. If I ask "why choose that particular bijection", the answer is "because it exists". –  Steve314 Jul 31 '10 at 20:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.