Why aren't the rationals more numerous than the integers?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

arbiteroftruth
Posts: 476
Joined: Wed Sep 21, 2011 3:44 am UTC

Why aren't the rationals more numerous than the integers?

Postby arbiteroftruth » Mon Oct 31, 2011 2:15 pm UTC

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.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Tirian » Mon Oct 31, 2011 2:24 pm UTC

It's a natural question, but every infinite set can be put in one-to-one 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 one-to-one 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 one-to-one mapping from A to B, your pick).

arbiteroftruth
Posts: 476
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Why aren't the rationals more numerous than the integers

Postby arbiteroftruth » Mon Oct 31, 2011 2:31 pm UTC

Tirian wrote:It's a natural question, but every infinite set can be put in one-to-one 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 one-to-one 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 one-to-one mapping from A to B, your pick).


Except that construing the integers to be more numerous than the integers is automatically bi-directional 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.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Tirian » Mon Oct 31, 2011 3:05 pm UTC

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.

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Timefly » Mon Oct 31, 2011 4:29 pm UTC

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 1-1 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?"

User avatar
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

Postby jestingrabbit » Mon Oct 31, 2011 4:33 pm UTC

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 Z-module. 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.

User avatar
Sizik
Posts: 1244
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Why aren't the rationals more numerous than the integers

Postby Sizik » Mon Oct 31, 2011 8:28 pm UTC

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?
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
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

Postby Talith » Mon Oct 31, 2011 8:56 pm UTC

If I understand you correctly, it's basically another way of stating the Cantor-Bernstein-Schroeder 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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Qaanol » Mon Oct 31, 2011 9:42 pm UTC

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 1-1 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

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Why aren't the rationals more numerous than the integers

Postby mike-l » Tue Nov 01, 2011 3:06 pm UTC

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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby WarDaft » Tue Nov 01, 2011 4:25 pm UTC

mike-l 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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26738
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

Postby gmalivuk » Tue Nov 01, 2011 4:35 pm UTC

I think having such a bijection implies infinitude with or without AC, but the converse needs AC.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
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

Postby Talith » Tue Nov 01, 2011 4:59 pm UTC

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?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26738
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

Postby gmalivuk » Tue Nov 01, 2011 5:05 pm UTC

Talith wrote:But then if you don't have AC must we then conclude there are sets which are neither finite nor infinite?
No. If bijection then infinite. If not infinite then no bijection. How does that leave room for a third type of set?
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
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

Postby jestingrabbit » Tue Nov 01, 2011 5:22 pm UTC

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/Dedekind-f ... _of_choice
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Qaanol » Tue Nov 01, 2011 5:23 pm UTC

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 Dedekind-infinite. 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 Dedekind-infinite. 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 Dedekind-finite. 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 Dedekind-finite. So it follows immediately that Dedekind-infinite implies infinite.
wee free kings

User avatar
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

Postby jestingrabbit » Tue Nov 01, 2011 5:28 pm UTC

Qaanol wrote:Anyway, without choice in any form, we must conclude there exists an infinite set that is Dedekind-finite.


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.

User avatar
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

Postby Talith » Tue Nov 01, 2011 5:29 pm UTC

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 a-infinite if it's not finite by the previous definition, and b-infinite if there exists a bijection between X and a proper subset of X. Then do we have (X a-infinite <=> X b-infinite) 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]

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Qaanol » Tue Nov 01, 2011 7:22 pm UTC

Is there a name for the statement, “Dedekind-finite implies finite”? (Equivalently, “infinite implies Dedekind-infinite”.) 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.
Last edited by Qaanol on Tue Nov 01, 2011 8:04 pm UTC, edited 8 times in total.
wee free kings

User avatar
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

Postby jestingrabbit » Tue Nov 01, 2011 7:25 pm UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Qaanol » Tue Nov 01, 2011 7:36 pm UTC

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 Dedekind-infinite (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 an. Define the subset T of S by T = S∖{a0}. Then take the function f:S→T given by f(ak)=ak+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

User avatar
skeptical scientist
closed-minded 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

Postby skeptical scientist » Tue Nov 01, 2011 11:36 pm UTC

Here is a short paper by A. Levy entitled "The independence of various definitions of finiteness". In it, Levy gives 8 definitions of finiteness, I-finite, Ia-finite, II-finite, III-finite, ..., VII-finite, 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 Q-finite set which is not P-finite. 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.

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 ≠ fm-n(x), and so by injectivity, fn(x) ≠ fm(x). Therefore {fn(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

User avatar
PM 2Ring
Posts: 3707
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Why aren't the rationals more numerous than the integers

Postby PM 2Ring » Wed Nov 02, 2011 5:42 am UTC

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 Fomega would seem to require infinitesimals. But maybe something tricky could be done to give lim n->infinity of Fn 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).

User avatar
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

Postby jestingrabbit » Wed Nov 02, 2011 6:13 am UTC

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 ≠ fm-n(x), and so by injectivity, fn(x) ≠ fm(x). Therefore {fn(x) : n in N} is a countably infinite subset of X.


Good point.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Why aren't the rationals more numerous than the integers

Postby mike-l » Wed Nov 02, 2011 1:43 pm UTC

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.

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Why aren't the rationals more numerous than the integers

Postby Dason » Wed Nov 02, 2011 6:12 pm UTC

mike-l 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;

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Why aren't the rationals more numerous than the integers

Postby mike-l » Wed Nov 02, 2011 7:45 pm UTC

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.

User avatar
skeptical scientist
closed-minded 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

Postby skeptical scientist » Wed Nov 02, 2011 11:11 pm UTC

mike-l 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 aN and aN+1 are not relatively prime. N≠0, since a0=a1=1. So N is either 2n+1 or 2n+2 for some 0≤n<N, where an and an+1 are relatively prime. But if N=2n+1, then aN=an and aN+1=an+an+1 are relatively prime. Similarly, if N=2n+2, then aN=an+an+1 and aN+1=an+1 are relatively prime. Thus for all N, aN and aN+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

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby WarDaft » Thu Nov 03, 2011 7:22 am UTC

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.

User avatar
skeptical scientist
closed-minded 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

Postby skeptical scientist » Thu Nov 03, 2011 8:43 am UTC

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

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby Qaanol » Thu Nov 03, 2011 8:51 am UTC

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

User avatar
skeptical scientist
closed-minded 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

Postby skeptical scientist » Thu Nov 03, 2011 9:43 am UTC

Actually, there's an easy proof that every rational occurs.

Spoiler:
Let p/q be a rational (in least terms) which doesn't occur such that p+q is minimal. If p<q, then p/(q-p) occurs, say as an/an+1. As p,q are relatively prime, p,q-p are relatively prime, and by my post above, an,an+1 are relatively prime, so an=p and an+1=q-p. But then a2n+1=p and a2n+2=q, so p/q occurs. Similarly, if p>q, then (p-q)/q is also a rational in least terms which must occur as an/an+1, i.e. an=p-q and an+1=q. But then a2n+2=p and a2n+3=q, so p/q occurs. Finally, if p=q, then p/q occurs as a0/a1.
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

User avatar
PM 2Ring
Posts: 3707
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Why aren't the rationals more numerous than the integers

Postby PM 2Ring » Fri Nov 04, 2011 1:56 pm UTC

Thanks, guys. That's a very pretty sequence.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Why aren't the rationals more numerous than the integers

Postby tomtom2357 » Sat Dec 24, 2011 9:38 am UTC

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.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Why aren't the rationals more numerous than the integers

Postby antonfire » Sat Dec 24, 2011 12:42 pm UTC

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.
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?


Return to “Mathematics”

Who is online

Users browsing this forum: chridd and 7 guests