4 ms·

If the pixels are laid out in a grid then each has a coordinate (x, y), where x and y are integers. Then we form a bijection (x, y) <-> x/y and we see that ther

by HZet0r 12y ago

If the pixels are laid out in a grid then each has a coordinate (x, y), where x and y are integers. Then we form a bijection (x, y) <-> x/y and we see that there are as many pixels as rational numbers. We know that the set of rational numbers is countably infinite, so the number of pixels is countably infinite.

pdonis 12y ago
> If the pixels are laid out in a grid then each has a coordinate (x, y), where x and y are integers. This is true for a finite number of divisions of the pixels. But is it still true for an infinite number of divisions?
- roywiggins 12y ago
  The set of pixels along the edge of your choice is countable. The reason is basically the same as was given, except it's simpler since you're only subdividing in one dimension. You'll never drop a pixel exactly at 1/3 or anywhere that isn't an integer multiple of a power of 2. You can identify each pixel by two other pixels along your chosen edges (axes). The set of pairs drawn from countable sets is always countable.
  - pdonis 12y ago
    > The set of pixels along the edge of your choice is countable. It is for a finite number of divisions. But is it for an infinite number of divisions? You are basically assuming that the limit point of a given sequence must have the same properties as every item in the sequence. That is obviously false; for example, many limit points of sequences of rational numbers are not rational numbers. So you can't just help yourself to the assumption that, because each pixel's coordinates have a certain property after a finite number of divisions, the coordinates will still have the same property after an infinite number of divisions.
    - Dylan16807 12y ago
      Each pixel always starts at coordinate n / 2^k. There are no limits involved here. Just a construction of an infinite series of rational coordinates.
function_seven 12y ago
> Then we form a bijection (x, y) <-> x/y and we see that there are as many pixels as rational numbers. I don't think that works, though. Take for example these two coordinates: (30, 75) (90, 225) Those would both map to the same rational—2/5—and that would make it not a one-to-one mapping.
- HZet0r 12y ago
  You're right - good point. For one way, I guess you could let p_i represent the ith prime number (there are infinitely many) and use p_x / p_y instead. Unsure about the other way.
  - roywiggins 12y ago
    There's a general result that the set of "All pairs of elements from two countable sets" is, itself, countable. (the Cartesian product of two countable sets is countable). For example, the set of all pairs of natural numbers can be counted something like this: 1,1 2,1 2,2 1,2 3,1 3,2 3,3 1,3 2,3 ...
  - function_seven 12y ago
    Nice! I'm convinced now.
- rmidthun 12y ago
  There is a way to map each rational to a specific positive integer. First, you need to define a mapping between positives and integers, this is pretty simple. 0 1 2 3 4 0 -1 1 -2 2 in c code: if(x<0) ? (x * -2)-1 : x * 2; (pretend that's fixed width above) Next, any rational can be broken down into a unique prime factorization. 4/6 = 2^1 * 3^-1, 4/15 = 2^2 * 3^-1 * 5^-1 From the factorization, define a transform where the exponent for each prime is replaced using the mapping above: so (2^2 * 3^-1 * 5^-1) becomes (2^4 * 3^1 * 5^1) = 240. Since the original rational can be negative, you'll need to use the first transformation again, so 4/15 = 240, -4/15 = -240, which work out to 480 and 479 respectively. 0 and 1 are left unchanged by the factorization process so 0 maps to 0, 1 to 2, and -1 to 1.

by HZet0r 12y ago

pdonis 12y ago

> If the pixels are laid out in a grid then each has a coordinate (x, y), where x and y are integers. This is true for a finite number of divisions of the pixels. But is it still true for an infinite number of divisions?

roywiggins 12y ago
The set of pixels along the edge of your choice is countable. The reason is basically the same as was given, except it's simpler since you're only subdividing in one dimension. You'll never drop a pixel exactly at 1/3 or anywhere that isn't an integer multiple of a power of 2. You can identify each pixel by two other pixels along your chosen edges (axes). The set of pairs drawn from countable sets is always countable.
- pdonis 12y ago
  > The set of pixels along the edge of your choice is countable. It is for a finite number of divisions. But is it for an infinite number of divisions? You are basically assuming that the limit point of a given sequence must have the same properties as every item in the sequence. That is obviously false; for example, many limit points of sequences of rational numbers are not rational numbers. So you can't just help yourself to the assumption that, because each pixel's coordinates have a certain property after a finite number of divisions, the coordinates will still have the same property after an infinite number of divisions.
  - Dylan16807 12y ago
    Each pixel always starts at coordinate n / 2^k. There are no limits involved here. Just a construction of an infinite series of rational coordinates.

function_seven 12y ago

> Then we form a bijection (x, y) <-> x/y and we see that there are as many pixels as rational numbers. I don't think that works, though. Take for example these two coordinates: (30, 75) (90, 225) Those would both map to the same rational—2/5—and that would make it not a one-to-one mapping.

HZet0r 12y ago
You're right - good point. For one way, I guess you could let p_i represent the ith prime number (there are infinitely many) and use p_x / p_y instead. Unsure about the other way.
- roywiggins 12y ago
  There's a general result that the set of "All pairs of elements from two countable sets" is, itself, countable. (the Cartesian product of two countable sets is countable). For example, the set of all pairs of natural numbers can be counted something like this: 1,1 2,1 2,2 1,2 3,1 3,2 3,3 1,3 2,3 ...
- function_seven 12y ago
  Nice! I'm convinced now.
rmidthun 12y ago
There is a way to map each rational to a specific positive integer. First, you need to define a mapping between positives and integers, this is pretty simple. 0 1 2 3 4 0 -1 1 -2 2 in c code: if(x<0) ? (x * -2)-1 : x * 2; (pretend that's fixed width above) Next, any rational can be broken down into a unique prime factorization. 4/6 = 2^1 * 3^-1, 4/15 = 2^2 * 3^-1 * 5^-1 From the factorization, define a transform where the exponent for each prime is replaced using the mapping above: so (2^2 * 3^-1 * 5^-1) becomes (2^4 * 3^1 * 5^1) = 240. Since the original rational can be negative, you'll need to use the first transformation again, so 4/15 = 240, -4/15 = -240, which work out to 480 and 479 respectively. 0 and 1 are left unchanged by the factorization process so 0 maps to 0, 1 to 2, and -1 to 1.