Why aren't the rationals more numerous than the integers?
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 475
 Joined: Wed Sep 21, 2011 3:44 am UTC
Why aren't the rationals more numerous than the integers?
I understand the logic that it's possible to create a 1:1 mapping between the set of integers and the set of rational numbers, and that for this reason the two sets are regarded as the same size. But by the same token, it's possible to create a mapping whereby the set of rational numbers still has an infinite number of elements remaining after mapping elements to all the integers(for example, map all integers to themselves in the set of rational numbers), and this would suggest that the rational numbers are a larger set. Why is the former regarded as the definitive case when evaluating the relative size of the two sets?
The only reason that occurs to me is if it was analogous to the fact that infinity plus infinity still just results in infinity, so that one set could be construed as larger than the other even though they're equal in size. Except that if that's all it was, I would expect it to be possible to construe either set as larger than the other, but it doesn't seem possible to create a mapping whereby the integers have elements remaining after mapping to the rational numbers. So it is only the rational numbers that can be construed as the larger set.
The only reason that occurs to me is if it was analogous to the fact that infinity plus infinity still just results in infinity, so that one set could be construed as larger than the other even though they're equal in size. Except that if that's all it was, I would expect it to be possible to construe either set as larger than the other, but it doesn't seem possible to create a mapping whereby the integers have elements remaining after mapping to the rational numbers. So it is only the rational numbers that can be construed as the larger set.
Re: Why aren't the rationals more numerous than the integers
It's a natural question, but every infinite set can be put in onetoone correspondence with a proper subset of itself. And there's no sense in saying that the integers are more numerous than the integers just because the integers can be put into onetoone correspondence with the even integers and so all the odds are frosting. That's why the definition is that you say that A is more numerous than B if there is NO surjection from B to A (or no onetoone mapping from A to B, your pick).

 Posts: 475
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: Why aren't the rationals more numerous than the integers
Tirian wrote:It's a natural question, but every infinite set can be put in onetoone correspondence with a proper subset of itself. And there's no sense in saying that the integers are more numerous than the integers just because the integers can be put into onetoone correspondence with the even integers and so all the odds are frosting. That's why the definition is that you say that A is more numerous than B if there is NO surjection from B to A (or no onetoone mapping from A to B, your pick).
Except that construing the integers to be more numerous than the integers is automatically bidirectional since you're only talking about one set to begin with, so it's analogous to being able to create a mapping where the integers are more numerous than the rationals, effectively cancelling out the implications of a mapping that make the rationals seem more numerous than the integers.
But your example of mapping integers to even integers makes me realize that it is in fact possible to create such a mapping where the integers are the set with elements left over. Simply take the 1:1 system of mapping integers to rationals, apply the same system instead to the set of even integers, and the set of rationals gets used up while all the odd integers remain. So either set could be construed as larger than the other, and the situation becomes completely analogous to "infinity plus infinity equals infinity".
Thanks.
Re: Why aren't the rationals more numerous than the integers
RIght, and you can also say that the integers are more numerous than the rationals because you can map ±p/q (expressing the rational in least terms) to ±(2^p)(3^q) and there are plenty of integers that aren't in the range. So defining the order for cardinality by the existence of a mapping would make for an unusual order.
Re: Why aren't the rationals more numerous than the integers
Arrange the rationals as so...
1/1 1/2 1/3 1/4 1/5...
2/1 2/2 2/3 2/4 2/5...
3/1 3/2 3/3 3/4 3/5...
4/1 4/2 4/3 4/4 4/5...
5/1 5/2 5/3 5/4 5/5...
. . . . .
. . . . .
. . . . .
Now start at the top left hand corner of the grid and begin to draw a line snaking through the grid.
So the line starts at 1/1 and goes on to 1/2 > 2/1 > 3/1 > 2/2 > 1/3 > 1/4 > 2/3 > etc...
Now stretch out this line and put it in 11 correspondence with the set of all integers. You Now have a bijection from Z to Q.
While the integers are a subset of the rationals, every infinite set has a bijection to every single subset of itself, that's actually one of the definitions of infinity.
You seem to be having an issue with how you think of counting. Don't think of infinity cardinals as a numbers but rather just as measures, ask the question "Can I line up set A to set B?"
1/1 1/2 1/3 1/4 1/5...
2/1 2/2 2/3 2/4 2/5...
3/1 3/2 3/3 3/4 3/5...
4/1 4/2 4/3 4/4 4/5...
5/1 5/2 5/3 5/4 5/5...
. . . . .
. . . . .
. . . . .
Now start at the top left hand corner of the grid and begin to draw a line snaking through the grid.
So the line starts at 1/1 and goes on to 1/2 > 2/1 > 3/1 > 2/2 > 1/3 > 1/4 > 2/3 > etc...
Now stretch out this line and put it in 11 correspondence with the set of all integers. You Now have a bijection from Z to Q.
While the integers are a subset of the rationals, every infinite set has a bijection to every single subset of itself, that's actually one of the definitions of infinity.
You seem to be having an issue with how you think of counting. Don't think of infinity cardinals as a numbers but rather just as measures, ask the question "Can I line up set A to set B?"
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Why aren't the rationals more numerous than the integers
Cardinality isn't the only notion of size that can be given to sets, its just the one that looks only at the number of points in the sets, not the way that operations, or topology or what have you, shape the set.
One that is pretty nice is dimension, which is usually used to describe vector spaces (and by extension manifolds) but you can also talk about the dimension of a space in terms of modules defined over rings.
http://en.wikipedia.org/wiki/Module_%28mathematics%29
Long story short, they're a set where you have an addition and a multiplication by scalars taken from another set, here the integers. You could then say that there is no n such that there is a homomorphism, f:Z^n > Q, which you could phrase, a little inaccurately, as saying that the rationals are an infinite dimensional Zmodule. So, in that sense, the rationals are much larger than the integers.
Another algebraic sense in which I would also say that Q is bigger than Z is that the rationals are closed under multiplicative inverses but the integers aren't.
I could probably find a whole bunch of other ways in which the rationals are bigger than the integers, but my point is that being the same size in one sense shouldn't dissuade you from your intuition that one set is much bigger than other in another, and for some applications more important, sense.
One that is pretty nice is dimension, which is usually used to describe vector spaces (and by extension manifolds) but you can also talk about the dimension of a space in terms of modules defined over rings.
http://en.wikipedia.org/wiki/Module_%28mathematics%29
Long story short, they're a set where you have an addition and a multiplication by scalars taken from another set, here the integers. You could then say that there is no n such that there is a homomorphism, f:Z^n > Q, which you could phrase, a little inaccurately, as saying that the rationals are an infinite dimensional Zmodule. So, in that sense, the rationals are much larger than the integers.
Another algebraic sense in which I would also say that Q is bigger than Z is that the rationals are closed under multiplicative inverses but the integers aren't.
I could probably find a whole bunch of other ways in which the rationals are bigger than the integers, but my point is that being the same size in one sense shouldn't dissuade you from your intuition that one set is much bigger than other in another, and for some applications more important, sense.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Why aren't the rationals more numerous than the integers
Does the fact that there exist both mappings where the rationals are more numerous than the integers, and vice versa, tell us anything about whether both sets have the same cardinality?
gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one metame to experience both body's sensory inputs.
 Talith
 Proved the Goldbach Conjecture
 Posts: 848
 Joined: Sat Nov 29, 2008 1:28 am UTC
 Location: Manchester  UK
Re: Why aren't the rationals more numerous than the integers
If I understand you correctly, it's basically another way of stating the CantorBernsteinSchroeder theorem which says that if A maps injectively on to B and B maps injectively on to A, then there exists a bijection between A and B. If you also have the theorem that says if A maps injectively on to B then A is less than or equal to B, then you can reform the CBS theorem to say ([imath]A\leq B[/imath] and [imath]B\leq A[/imath]) implies A=B iff A~B.
Re: Why aren't the rationals more numerous than the integers
Timefly wrote:Arrange the rationals as so...
1/1 1/2 1/3 1/4 1/5...
2/1 2/2 2/3 2/4 2/5...
3/1 3/2 3/3 3/4 3/5...
4/1 4/2 4/3 4/4 4/5...
5/1 5/2 5/3 5/4 5/5...
. . . . .
. . . . .
. . . . .
Now start at the top left hand corner of the grid and begin to draw a line snaking through the grid.
So the line starts at 1/1 and goes on to 1/2 > 2/1 > 3/1 > 2/2 > 1/3 > 1/4 > 2/3 > etc...
Now stretch out this line and put it in 11 correspondence with the set of all integers. You Now have a bijection from Z to Q.
This is not quite right. To get a bijection you need to skip all the repeat occurrences. So you don’t take 2/2 after you already have 1/1, for instance. You also don’t have zero or negative numbers represented. Again, those are easy things to take care of, but they are important enough that you do not, in fact, have a bijection from ℤ to ℚ as you claim.
Timefly wrote:While the integers are a subset of the rationals, every infinite set has a bijection to every single subset of itself, that's actually one of the definitions of infinity.
This is also wrong. Every infinite set has a bijection to at least one of its subsets.
wee free kings
Re: Why aren't the rationals more numerous than the integers
Qaanol wrote:This is also wrong. Every infinite set has a bijection to at least one of its subsets.
And only if you take the axiom of choice.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Re: Why aren't the rationals more numerous than the integers
mikel wrote:Qaanol wrote:This is also wrong. Every infinite set has a bijection to at least one of its subsets.
And only if you take the axiom of choice.
Er, I thought that was one of the definitions of an infinite set... bijection with one of it's proper subsets.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26726
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Why aren't the rationals more numerous than the integers
I think having such a bijection implies infinitude with or without AC, but the converse needs AC.
 Talith
 Proved the Goldbach Conjecture
 Posts: 848
 Joined: Sat Nov 29, 2008 1:28 am UTC
 Location: Manchester  UK
Re: Why aren't the rationals more numerous than the integers
What definition of infinite set are you using if it's not that there exists a bijection from the set to a proper subset?
I suppose you could define a finite set to be any set that can be put in bijection with the set {0,1,2,...,n} for some n in the naturals. You can then define an infinite set to be any set which is not finite. But then if you don't have AC must we then conclude there are sets which are neither finite nor infinite?
I suppose you could define a finite set to be any set that can be put in bijection with the set {0,1,2,...,n} for some n in the naturals. You can then define an infinite set to be any set which is not finite. But then if you don't have AC must we then conclude there are sets which are neither finite nor infinite?
 gmalivuk
 GNU Terry Pratchett
 Posts: 26726
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Why aren't the rationals more numerous than the integers
No. If bijection then infinite. If not infinite then no bijection. How does that leave room for a third type of set?Talith wrote:But then if you don't have AC must we then conclude there are sets which are neither finite nor infinite?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Why aren't the rationals more numerous than the integers
Talith wrote:What definition of infinite set are you using if it's not that there exists a bijection from the set to a proper subset?
I suppose you could define a finite set to be any set that can be put in bijection with the set {0,1,2,...,n} for some n in the naturals. You can then define an infinite set to be any set which is not finite. But then if you don't have AC must we then conclude there are sets which are neither finite nor infinite?
A third option is for an injection from the naturals to the set. That pretty quickly implies the existence of a bijection between an infinite set and a proper subset.
To get that there is a distinction here, read this (or the whole page really):
http://en.wikipedia.org/wiki/Dedekindf ... _of_choice
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Why aren't the rationals more numerous than the integers
Talith wrote:What definition of infinite set are you using if it's not that there exists a bijection from the set to a proper subset?
I suppose you could define a finite set to be any set that can be put in bijection with the set {0,1,2,...,n} for some n in the naturals. You can then define an infinite set to be any set which is not finite.
The former property, about bijections to proper subsets, is called Dedekindinfinite. The latter, about bijections to natural numbers, is called simply called “infinite”.
Talith wrote:But then if you don't have AC must we then conclude there are sets which are neither finite nor infinite?
You don’t need all of AC to show infinite implies Dedekindinfinite. You don’t even need all of countable choice, and most people intuitively are fine with everything up to dependent choice, which is stronger than countable choice and weaker than choice.
Anyway, without choice in any form, we must conclude there exists an infinite set that is Dedekindfinite. As in, the set cannot be put in bijection with any set of natural numbers {1, 2, …, n}, and also the set cannot be put in bijection with any of its proper subsets.
Almost trivially, in plain old ZF we see that finite implies Dedekindfinite. So it follows immediately that Dedekindinfinite implies infinite.
wee free kings
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Why aren't the rationals more numerous than the integers
Qaanol wrote:Anyway, without choice in any form, we must conclude there exists an infinite set that is Dedekindfinite.
No. Any model of ZF+AC is a model of ZF, and in no model of ZF+AC is there such a set. Without choice, we can't rule out the existence of such a set, but its not necessary that such a set exists.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Talith
 Proved the Goldbach Conjecture
 Posts: 848
 Joined: Sat Nov 29, 2008 1:28 am UTC
 Location: Manchester  UK
Re: Why aren't the rationals more numerous than the integers
Yeh I dunno why I said that... What I was really wondering is if the two definitions are equivalent without AC. If we call a set X ainfinite if it's not finite by the previous definition, and binfinite if there exists a bijection between X and a proper subset of X. Then do we have (X ainfinite <=> X binfinite) in ZF or only ZFC? If it doesn't hold in ZF, then depending on which definition you take would mean it's possible (though not necessary) for some strange sets to exist that are finite with respect to one definition but infinite with respect to the other definition.
[edit] my question got answered very well by Qaanol who replied before I posted this but I might as well post[/edit]
[edit] my question got answered very well by Qaanol who replied before I posted this but I might as well post[/edit]
Re: Why aren't the rationals more numerous than the integers
Is there a name for the statement, “Dedekindfinite implies finite”? (Equivalently, “infinite implies Dedekindinfinite”.) If not, I propose, “Axiom of Dedekind choice”.
If I’m thinking it through correctly, this axiom of Dedekind choice is exactly strong enough to show that “Every infinite set has a countable subset”, in the sense that it is sufficient and any strictly weaker formulation of choice would not be sufficient.
I’m not entirely sure what a proof of “Dedekind choice implies every infinite set has a countable subset” would look like though. I’m visualizing a countable nested sequence of proper subsets, each in bijection with the previous, but I’m having a spot of trouble showing how to extract a countable sequence from that without using countable choice.
If I’m thinking it through correctly, this axiom of Dedekind choice is exactly strong enough to show that “Every infinite set has a countable subset”, in the sense that it is sufficient and any strictly weaker formulation of choice would not be sufficient.
I’m not entirely sure what a proof of “Dedekind choice implies every infinite set has a countable subset” would look like though. I’m visualizing a countable nested sequence of proper subsets, each in bijection with the previous, but I’m having a spot of trouble showing how to extract a countable sequence from that without using countable choice.
Last edited by Qaanol on Tue Nov 01, 2011 8:04 pm UTC, edited 8 times in total.
wee free kings
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Why aren't the rationals more numerous than the integers
Qaanol wrote:I’m visualizing a countable nested sequence of proper subsets, each in bijection with the previous, but I’m having a spot of trouble showing how to extract a countable sequence from that without using countable choice.
Each is in bijection with the earlier, with the same function making the bijection happen, yeah? So, pick a point such that f(x) != x and see what its f orbit looks like.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Why aren't the rationals more numerous than the integers
jestingrabbit wrote:Each is in bijection with the earlier, with the same function making the bijection happen, yeah? So, pick a point such that f(x) != x and see what its f orbit looks like.
Ah, thanks, that’s a good way to do it.
Now how to show the reverse: Given that “every infinite set has a countable subset”, can we show that every infinite set is Dedekindinfinite (ie. can be put in bijection with one of its proper subsets)?
I feel like we can, and it’s just a simple matter of “shifting the occupants in Hilbert’s hotel”, but I haven’t put any time into thinking it through yet.
Edit: Yeah, it is that simple.
Given an infinite set S that has a countable subset A, enumerate the countable subset as a_{n}. Define the subset T of S by T = S∖{a_{0}}. Then take the function f:S→T given by f(a_{k})=a_{k+1}, and f(x)=x for x∉A. This is a bijection between S and its proper subset T.
So perhaps the “Axiom of Dedekind choice” could be called instead the “Countable subset axiom”, since the two are equivalent.
wee free kings
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Why aren't the rationals more numerous than the integers
Here is a short paper by A. Levy entitled "The independence of various definitions of finiteness". In it, Levy gives 8 definitions of finiteness, Ifinite, Iafinite, IIfinite, IIIfinite, ..., VIIfinite, shows that I => Ia => II => ... => VII (provably in ZF), but that none of the implications reverse (except possibly II => III), in that for each pair P => Q, there is a model of ZF which contains a Qfinite set which is not Pfinite. This should answer some of your questions above. In particular, definition I is equivalent (over ZF) to being in bijective correspondence with a natural number, and definition IV is there is no bijection between A and a proper subset of A.
You don't want a point x such that f(x) ≠ x, because the orbit of x might still be a finite set. Rather you want a point x which is not in the range of f. Then for all n < m, x ≠ f^{mn}(x), and so by injectivity, f^{n}(x) ≠ f^{m}(x). Therefore {f^{n}(x) : n in N} is a countably infinite subset of X.
jestingrabbit wrote:Each is in bijection with the earlier, with the same function making the bijection happen, yeah? So, pick a point such that f(x) != x and see what its f orbit looks like.
You don't want a point x such that f(x) ≠ x, because the orbit of x might still be a finite set. Rather you want a point x which is not in the range of f. Then for all n < m, x ≠ f^{mn}(x), and so by injectivity, f^{n}(x) ≠ f^{m}(x). Therefore {f^{n}(x) : n in N} is a countably infinite subset of X.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Why aren't the rationals more numerous than the integers
Getting back to the topic of making a bijection between Q and N, is there any way to create such a bijection using Farey sequences? My suspicion is that there isn't since a naive algorithm to construct F_{omega} would seem to require infinitesimals. But maybe something tricky could be done to give lim n>infinity of F_{n} a legitimate definition.
One of the nice things about Farey sequences is that they are ordered, but I guess the density of Q makes it tricky to have an ordered bijection between Q and N.
I have no qualms about the bijection given earlier in the thread, but it would be nice to find a bijection that doesn't require the elimination of fractions that aren't in their lowest terms, since that makes it virtually impossible to calculate the index of a given fraction without calculating the previous terms in the sequence (or using some kind of prime counting function in the algorithm).
One of the nice things about Farey sequences is that they are ordered, but I guess the density of Q makes it tricky to have an ordered bijection between Q and N.
I have no qualms about the bijection given earlier in the thread, but it would be nice to find a bijection that doesn't require the elimination of fractions that aren't in their lowest terms, since that makes it virtually impossible to calculate the index of a given fraction without calculating the previous terms in the sequence (or using some kind of prime counting function in the algorithm).
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Why aren't the rationals more numerous than the integers
skeptical scientist wrote:jestingrabbit wrote:Each is in bijection with the earlier, with the same function making the bijection happen, yeah? So, pick a point such that f(x) != x and see what its f orbit looks like.
You don't want a point x such that f(x) ≠ x, because the orbit of x might still be a finite set. Rather you want a point x which is not in the range of f. Then for all n < m, x ≠ f^{mn}(x), and so by injectivity, f^{n}(x) ≠ f^{m}(x). Therefore {f^{n}(x) : n in N} is a countably infinite subset of X.
Good point.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Why aren't the rationals more numerous than the integers
PM 2Ring wrote:I have no qualms about the bijection given earlier in the thread, but it would be nice to find a bijection that doesn't require the elimination of fractions that aren't in their lowest terms, since that makes it virtually impossible to calculate the index of a given fraction without calculating the previous terms in the sequence (or using some kind of prime counting function in the algorithm).
I feel like there was a putnam question back in 2002 or 2003 that iterated through the rationals without repetition.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Re: Why aren't the rationals more numerous than the integers
mikel wrote:PM 2Ring wrote:I have no qualms about the bijection given earlier in the thread, but it would be nice to find a bijection that doesn't require the elimination of fractions that aren't in their lowest terms, since that makes it virtually impossible to calculate the index of a given fraction without calculating the previous terms in the sequence (or using some kind of prime counting function in the algorithm).
I feel like there was a putnam question back in 2002 or 2003 that iterated through the rationals without repetition.
Question A5?
double epsilon = .0000001;
Re: Why aren't the rationals more numerous than the integers
That's the one I was thinking of, I'm at work so I don't have time to check if that repeats rationals or not.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Why aren't the rationals more numerous than the integers
mikel wrote:That's the one I was thinking of, I'm at work so I don't have time to check if that repeats rationals or not.
It doesn't, proof by induction. Let N be least such that a_{N} and a_{N+1} are not relatively prime. N≠0, since a_{0}=a_{1}=1. So N is either 2n+1 or 2n+2 for some 0≤n<N, where a_{n} and a_{n+1} are relatively prime. But if N=2n+1, then a_{N}=a_{n} and a_{N+1}=a_{n}+a_{n+1} are relatively prime. Similarly, if N=2n+2, then a_{N}=a_{n}+a_{n+1} and a_{N+1}=a_{n+1} are relatively prime. Thus for all N, a_{N} and a_{N+1} are relatively prime.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Why aren't the rationals more numerous than the integers
And it hits them all? Or is it one of those sort of questions where you can also prove the converse as an answer?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Why aren't the rationals more numerous than the integers
I didn't bother trying to show it hits them all, but I think we can safely assume that the statement the Putnam problem was asking you to prove is true.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Why aren't the rationals more numerous than the integers
Especially when you can just lop off the last piece of the url to find the page listing problems and solutions by year, search on the page for 2002, and click the “S” link to get the solutions.
wee free kings
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Why aren't the rationals more numerous than the integers
Actually, there's an easy proof that every rational occurs.
Spoiler:
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Why aren't the rationals more numerous than the integers
Thanks, guys. That's a very pretty sequence.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Why aren't the rationals more numerous than the integers
Tirian is wrong, every set cannot be put into a bijection with all of its subsets, an easy counterexample is the real numbers and the natural numbers, by cantor's diagonal argument.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Why aren't the rationals more numerous than the integers
Please don't dig old posts out of the archives unless you have something new and useful to contribute.
In particular, if you're going to claim something is wrong, read it closely. Tirian said that any infinite set can be put into bijection with a proper subset of itself. This is true of the natural numbers: there is a bijection between the natural numbers and the even natural numbers.
In particular, if you're going to claim something is wrong, read it closely. Tirian said that any infinite set can be put into bijection with a proper subset of itself. This is true of the natural numbers: there is a bijection between the natural numbers and the even natural numbers.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Who is online
Users browsing this forum: No registered users and 12 guests