5 ms·
> I think the followup at the end is wrong I think so too, but maybe not for the same reason you do. The original argument of the article is that there is a o
by pdonis 12y ago
> I think the followup at the end is wrong
I think so too, but maybe not for the same reason you do.
The original argument of the article is that there is a one-to-one mapping between the set produced as the end result of an infinite number of "pixel division" operations, and the set of infinite binary strings. Since the latter set is uncountable (by Cantor's diagonal argument), the former must be as well. This argument appears to me to be correct.
The followup retracts the above argument, basically because of this counter-argument:
"just as there’s no way to follow 0.333... until you reach exactly one-third, there’s no way to carve a pixel until you get to the exact point represented by a certain infinite binary string"
However, this counter-argument is incorrect, because it leaves out a key qualifier. There is no way to "follow 0.333... until you reach exactly one-third" in a finite number of steps. If you take an infinite number of steps, you do reach exactly one-third: that is what the statement "one-third is the limit of the repeating decimal 0.333..." means. True, you can't explicitly take an infinite number of steps, but you can calculate, mathematically, what the result would be if you did; that is how we know what the limit points are of sequences like 0.333...
Similarly, "there's no way to carve a pixel until you get to the exact point represented by a certain infinite binary string" in a finite number of steps. But you can do it in an infinite number of steps, and the article explicitly postulates exactly that--an infinite number of pixel divisions. And even though we can't explicitly do an infinite number of pixel divisions, we can still calculate, mathematically, what the result would be if we did. That result is the set of infinite binary strings; that set is the limit point of the sequence of pixel divisions, as the number of divisions goes to infinity, just as one-third is the limit point of the sequence 0.333... as the number of 3's goes to infinity.
- Dylan16807 12y agoYes, that counter was confusing and kind of wrong. But the followup is mostly correct. It is possible to carve pixels into uncountably more pixels, but you need uncountably many lines to do it. Division by countably many lines, aka rational division, does not increase cardinality. The cardinality of rational numbers is the same as the cardinality of integers.
- SamReidHughes 12y agoIn your post what is your definition of pixel?
- pdonis 12y ago> Division by countably many lines, aka rational division, does not increase cardinality. I understand that this sounds plausible, but I'm not sure it's true. The real numbers, which are uncountable, can be defined as the set of all limit points of countably infinite series of rational numbers. So the set of countably infinite sums is uncountable. Similarly, I think the set of countably infinite divisions is uncountable. Here's another way of looking at it: the number of pixels obtained by division by countably many lines is equal to the number of subsets of the rationals--which is uncountable.
- Dylan16807 12y agoBut the pixels aren't arbitrary subsets. Look at it in a single dimension for a moment. p | p | p | p | p | p There is a dead-obvious 1:1 correspondence between pixels and lines. You could even label each pixel by its bordering line, and then you're literally counting rationals. It's possible to construct the pixels with an infinite series of rationals, but it's also possible to construct them as a single rational in a countable way.
- pdonis 12y ago> the pixels aren't arbitrary subsets. Doesn't matter. They are the set of all subsets of a countably infinite set (the set of rationals of the form k / 2^n in the 2d example), and any such set of subsets is uncountable. There is a theorem in set theory to this effect. > There is a dead-obvious 1:1 correspondence between pixels and lines Yes, but that in itself doesn't show the cardinality of the set of pixels/lines. Nor does it show that the cardinality of the set of pixels/lines when an infinite number of divisions have been made, is the same as the cardinality of the set of pixels/lines when only a finite number of divisions have been made. Assuming that they must be the same is the equivalent of assuming that the cardinality of the reals is the same as the cardinality of the rationals, which is obviously false. > it's also possible to construct them as a single rational in a countable way How? Your construction above does not show that.
- roywiggins 12y agoI think your argument implies that the rationals are uncountable, but they aren't, so your argument must be wrong somewhere- I'm too rusty at this to form a nice argument quickly though.
- pdonis 12y ago> I think your argument implies that the rationals are uncountable No, it doesn't. But it does imply that the set of limit points of all countably infinite series of rationals is uncountable. And that's true: that set of limit points is the set of real numbers, which is uncountable.
- roywiggins 12y agoRight, yes. I was taking the product of the process of subdividing to not actually include the limit points at all. You are only performing the operation a countable number of times, and at each point you only add a finite number of points, so having an uncountable set pop out at the end seems unlikely. A bonehead way to formalize this: The first step outputs {0}, the second, {0, 1/2}, the third {0, 1/4, 1/2, 3/4}, etc. We drop them all into one big set A. A has countably many elements and they all have a finite size: A = {{0}, {1/2}, ... } If B is the union of A, it has to have every point that could ever be output by the process. B is the result of "running the process to infinity." B is obviously countable since it's the union of countably many finite sets. If you can think of a way to define running the process to infinity and -including- the limit points, I'd be interested, but the most natural interpretation to me is that the process produces a set that doesn't include the limit points at all.
- SamReidHughes 12y agoThe points {0, 1/4, 1/2, 3/4, 1}, etc, are the boundaries between pixels, not the pixels themselves.
- pdonis 12y ago> I was taking the product of the process of subdividing to not actually include the limit points at all. That's not correct. The limit point is "the product of the process of subdividing", by definition. > You are only performing the operation a countable number of times, and at each point you only add a finite number of points, so having an uncountable set pop out at the end seems unlikely. By this reasoning, the limit point of every sequence of rational numbers would be a rational number, and the set of all such limit points would be countable. But it isn't; it's the set of reals, which is uncountable.