|
On May 15 2009 01:58 qrs wrote:Show nested quote +On May 14 2009 23:16 jtan wrote:On May 14 2009 qrs wrote:On May 14 2009 22:04 jtan wrote:For some positive integer N, uncountably many spiders have width at least 1/N Is this really true though? Couldn't it be that the spiders remain countable until you allow for infinitely small legs? I wondered that as well, at first glance, but no, it couldn't be. If for all positive integers N the spiders with width at least 1/N were countable, you could count all the spiders by listing the spiders of width at least 1, then the spiders of width at least 1/2 (that haven't been counted yet), and so on. Any given spider must have some finite width, and for any finite number some 1/N is smaller than it, so you will count that spider when you get to the requisite N. Yep, you are right. actually, not quite right, on second thought. The method I gave for counting them all doesn't work (because you may never finish counting the first set of spiders), but they are still countable by other methods, e.g. count 1 from the first set, then 2 each from the first two sets, then 3 each from the first three sets, etc. It's the countable union of countable sets, like ninjafetus said.
Yeah, that's the standard way of counting a countable union of countable sets, I thought that was what you meant in the first place
|
On May 15 2009 02:08 -orb- wrote:
If it's an infinite plane why can't you just line them up going out to infinity....
The problem is not to just place infinietly many spiders in the plane, but uncountably many, that's a big difference http://en.wikipedia.org/wiki/Countable_set
|
On May 15 2009 02:33 jtan wrote:Show nested quote +On May 15 2009 01:58 qrs wrote:On May 14 2009 23:16 jtan wrote:On May 14 2009 qrs wrote:On May 14 2009 22:04 jtan wrote:For some positive integer N, uncountably many spiders have width at least 1/N Is this really true though? Couldn't it be that the spiders remain countable until you allow for infinitely small legs? I wondered that as well, at first glance, but no, it couldn't be. If for all positive integers N the spiders with width at least 1/N were countable, you could count all the spiders by listing the spiders of width at least 1, then the spiders of width at least 1/2 (that haven't been counted yet), and so on. Any given spider must have some finite width, and for any finite number some 1/N is smaller than it, so you will count that spider when you get to the requisite N. Yep, you are right. actually, not quite right, on second thought. The method I gave for counting them all doesn't work (because you may never finish counting the first set of spiders), but they are still countable by other methods, e.g. count 1 from the first set, then 2 each from the first two sets, then 3 each from the first three sets, etc. It's the countable union of countable sets, like ninjafetus said. Yeah, that's the standard way of counting a countable union of countable sets, I thought that was what you meant in the first place
Right, I know it's the standard way, but I wasn't thinking, and I didn't phrase it that way the first time.
|
On May 14 2009 14:53 Muirhead wrote:Congratulations cascade and qrs! I hope it was entertaining and enlightening even if it took all your time. Here's my solution from when I first solved the problem: + Show Spoiler +Suppose, for the sake of contradiction, that there are uncountably many spiders in the plane.
Let the width of a spider be the minimum distance from its center to one of its three endpoints.
For some positive integer N, uncountably many spiders have width at least 1/N. Erase all the spiders with width less than 1/N
Cover the plane with countably many disks of diameter 1/N. At least one such disk has uncountably many centers of spiders. Erase all spiders with centers not in the disk.
Each spider divides the disk into three distinct regions. Associate a triplet of rational points to the spider, one point in each region.
I don't know if the last part works. You haven't said anything about the spiders not intersecting. For example, if I had an ε-disk at the origin, and I took an uncountable set of spiders centered along the y- axis between (-ε/2, ε/2), each of which with legs going to the same three points, I could find a single rational triplet which could be associated with all of them. So I have uncountable spiders, but only countably many (in fact, only 1) rational triplet, and therefore no contradiction yet.
Now, this construction clearly won't be possible for the original problem (since their legs intersect), but your solution has nothing to prevent th construction I mentioned. I would think a complete solution would need to show how intersections being impossible implies that the uncountable rational triplets can be chosen distinctly.... which would then be the contradiction you need.
|
On May 15 2009 14:19 ninjafetus wrote:Show nested quote +On May 14 2009 14:53 Muirhead wrote:Congratulations cascade and qrs! I hope it was entertaining and enlightening even if it took all your time. Here's my solution from when I first solved the problem: + Show Spoiler +Suppose, for the sake of contradiction, that there are uncountably many spiders in the plane.
Let the width of a spider be the minimum distance from its center to one of its three endpoints.
For some positive integer N, uncountably many spiders have width at least 1/N. Erase all the spiders with width less than 1/N
Cover the plane with countably many disks of diameter 1/N. At least one such disk has uncountably many centers of spiders. Erase all spiders with centers not in the disk.
Each spider divides the disk into three distinct regions. Associate a triplet of rational points to the spider, one point in each region. I don't know if the last part works. You haven't said anything about the spiders not intersecting. For example, if I had an ε-disk at the origin, and I took an uncountable set of spiders centered along the y- axis between (-ε/2, ε/2), each of which with legs going to the same three points, I could find a single rational triplet which could be associated with all of them. So I have uncountable spiders, but only countably many (in fact, only 1) rational triplet, and therefore no contradiction yet. Now, this construction clearly won't be possible for the original problem (since their legs intersect), but your solution has nothing to prevent th construction I mentioned. I would think a complete solution would need to show how intersections being impossible implies that the uncountable rational triplets can be chosen distinctly.... which would then be the contradiction you need.
No intersections implies different triplets.Take any two spiders in the disc. The first spider divides the disc in three zones, and the second must have it's center node in one of these zones. Since they cannot intersect the second spider will have at least two points of its triplet inside this same zone, hence different triplets.
|
By that logic, couldn't I take the irrationals in [0,1], state that each irrational splits [0,1] into two distinct regions, associate a pair of rationals to each irrational, and therefore irrationals are countable since they have a correspondence to QxQ? Which we know doesn't work?
|
On May 15 2009 22:31 ninjafetus wrote:
By that logic, couldn't I take the irrationals in [0,1], state that each irrational splits [0,1] into two distinct regions, associate a pair of rationals to each irrational, and therefore irrationals are countable since they have a correspondence to QxQ? Which we know doesn't work?
No, because nothing in your construction prevents two irrationals from being mapped to the same element of QxQ
|
That was my point. But I see how it works now, it is because of no intersections of the legs... it's just that the phrase "Each spider divides the disk into three distinct regions. Associate a triplet of rational points to the spider, one point in each region" leaves a bit of the solution off, and I have a bad habit of posting what I'm thinking before I've spent enough time on it =p
Actually, by the way Muirhead defined 'width' of a spider, all three points of a second spider would be contained in a single region of the first, since all three legs would reach the edge of the disk.
|
On May 16 2009 02:07 ninjafetus wrote:
Actually, by the way Muirhead defined 'width' of a spider, all three points of a second spider would be contained in a single region of the first
Not nessessarily if you think about it, but atleast two of them would
no big deal though
|
On May 16 2009 02:47 jtan wrote:Show nested quote +On May 16 2009 02:07 ninjafetus wrote:
Actually, by the way Muirhead defined 'width' of a spider, all three points of a second spider would be contained in a single region of the first Not nessessarily if you think about it no? Looks to me like they would: the center of the spider is in one of the 3 regions; for any of its endpoints to be in a different region, that leg would have to cross the line bounding that region.
|
On May 16 2009 04:25 qrs wrote:Show nested quote +On May 16 2009 02:47 jtan wrote:On May 16 2009 02:07 ninjafetus wrote:
Actually, by the way Muirhead defined 'width' of a spider, all three points of a second spider would be contained in a single region of the first Not nessessarily if you think about it no? Looks to me like they would: the center of the spider is in one of the 3 regions; for any of its endpoints to be in a different region, that leg would have to cross the line bounding that region.
Ah, I wasn't talking about leg-points, but the points of the rational triplet of that spider
|
Oh, I see what you mean. Yeah, you could choose a rational point for the second spider in a completely different sector of the first. My intuition wants the coordinates for the points to not cross any boundaries, either, though :p
|
|
|
|
|
|
EPT
