3 ms·
> 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.
by 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.
- Dylan16807 12y ago>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. They are not the set of all subsets. Not even close. Each pixel is a very particular kind of contiguous subset. You can describe it with one or two rationals (Edit: two or four for 2D). "Set of all subsets" requires the ability to either include or not include an infinite number of elements independently. It's obvious that the sets {1,2,3}, {5,6,7}, {9,10,11}, etc. are countable, right? It's a list of subsets of integers but not all subsets. >How? Your construction above does not show that. The pixels are defined by their borders, the algorithm for outputting all borders looks like this: print 0 print 1 d = 2 loop: n = 1 while n < d: print (n / d) n += 2 d *= 2 This constructs all the pixels nice and rationally. Rational numbers are dense, and there are no irrational pixels.
- SamReidHughes 12y agoYou can define "pixel" however you want, but that has nothing to do with your claim that you can't divide an interval into uncountably many disjoint sets with countably many lines (points). pdonis and I are not arguing about which way you'd prefer to define the word pixel. But I think pdonis lost the train of what he/she was precisely speaking about in one sentence of the last post. Edit: > You can describe it with one or two rationals (Edit: two or four for 2D). Considering the one-dimensional case for a second: if you define a pixel with two "rationals" (I think you mean two numbers of the form k/2^n here, you're describing (I presume) its left and right boundary, creating an interval (a, b) where a < b. Fine. How do you describe a pixel with one rational (I think you mean one number of the form k/2^n)? For example, which pixel is described by the rational number 3/8?
- deleted 12y ago[deleted]
- Dylan16807 12y agoWell my argument is that there is a trivial bijection between the disjoint sets and the parallel lines/points. Do you have a counterargument? I admit I might be making a fundamental mistake but you're going to have to show where.
- SamReidHughes 12y ago> 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. Only if you want overlapping pixels or pixels of varying size. Or pixels that are points, in which case you don't need a convoluted recursive mechanism to define where and what they are.
- Dylan16807 12y agoI don't think they have to overlap just because you defined them rationally. I think it just becomes painful to address pixels if you don't have them overlap. I'm not certain on this point, however. But it's painful to use an infinite string as an address too.
- SamReidHughes 12y ago> I don't think they have to overlap just because you defined them rationally. They don't have to overlap, if you just define them as points or sets of points with zero area, or let them have varying size, or define them as weird subsets of the screen that aren't measurable. If your pixels are rectangles, though, they have to overlap or have varying size. Edit: I'm taking countable to mean "countably infinite" since this conversation already assumes we're talking about infinite sets of pixels.
- Dylan16807 12y agoCan they be points but only rational points? How can you tell the difference between dense rational points and dense real points? It seems like you can mark regions of zero size either through countable or uncountable methods...
- SamReidHughes 12y ago> Can they be points but only rational points? They can be, but then the total area of your pixels would be zero. Which is fine, since this isn't a real monitor we're talking about, this is a math monitor. But: One property of our computer monitor that we'd want is that when displaying white, it should have uniform brightness -- the amount of light emitted from a rectangle R should be proportional to area(R). The total amount of light emitted from the monitor should be nonzero, too. Let's say the area of the whole monitor is 1 and so is the luminosity. Your pixels are what's emitting light -- they're point-sources? Suppose p is one of your pixels (or its location). Then let's consider a sequence smaller and smaller squares around p, with side lengths 1/20, 1/21, 1/22, 1/23, ... The luminosity of each of these squares of sidelength 1/n must be the square's area, 1/n^2, because the brightness is uniform. So the pixel p must have zero luminosity, because if it had nonzero luminosity, then some very small rectangle around it would be emitting more light than it should be, and the monitor would not have uniform brightness. From this argument it seems that each pixel's luminosity is zero. And then you can enumerate the pixels, since they form a countable set: p_1, p_2, p_3, .... The luminosity of the whole screen is a countable sum, which is sum[i = 1 to infinity](luminosity(p_i)) = sum[i = 1 to infinity](0) = 0. So I don't think the idea of dividing a math-monitor into countably many pixels, each with zero area, works. It's OK that the total area of the pixels is zero, but you have to accept non-uniform luminosity or say that the pixels aren't point sources, they "bleed". However, if you have uncountably many pixels, then it's okay if each "pixel" (whatever) has zero luminosity. You only get nonzero luminosity when talking about sets of pixels with nonzero area -- their luminosity on the uniformly bright screen is proportional to the set's area. That's perfectly compatible with intuition -- the same way it's intuitive that the area of a unit square is 1, even though it's an uncountable union of sets having one point each, each of whose area is zero.
- SamReidHughes 12y ago> But the pixels aren't arbitrary subsets. Look at it in a single dimension for a moment. > p | p | p | p | p | p It only looks like this with finitely many pixels.