13 ms·

The infinite-pixel screen

36 points by lispython 12y ago

deleted 12y ago
[deleted]
refrigerator 12y ago
What's with everyone's obsession with talking about countable and uncountable infinities? Surely everyone has already read about this stuff by now?
- Leszek 12y ago
  Relevant counterargument: http://xkcd.com/1053/ http://xkcd.com/1053/
  - ChristianBundy 12y ago
    Let me guess – I'm one of today's 10,000? EDIT: Hell to the hell yeah.
    - dragontamer 12y ago
      Which means you weren't one of today's 10,000 (when it comes to xkcd)
- arnold_palmur 12y ago
  > Surely everyone has already read about this stuff by now? classic.
- WhitneyLand 12y ago
  What do you mean by that? First of all I'm not even sure this stuff is taught in college outside of a stem degree so I'm sure there are lots of people who have not encountered it. Even for those who have studied it it's sometimes fun to walk through some light proofs, puzzle things out, refresh your memory. It also a nice hook to get people interested in math because it one of the areas where you can use creativity to solve problems without needing many prerequisites.
- sukilot 12y ago
  We read it so long ago, that we forgot about it.
- wetmore 12y ago
  You and I are math students, and we both have this sort of reaction when we see such articles. The important thing is to realize that not everyone is a math student.
rtpg 12y ago
Just a guess, but I'm pretty sure that if you have a totally-ordered set (like in your infinite pixel screen, dictionary order on first coordinate followed by second), and all subsets S = {x/ a<=x<=b } are countably infinite, then the set is countably infinite. A constructive proof of this is probably doable by inspiring oneself off of Hilbert's hotel paradox (http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gran...)
- ontario 12y ago
  Even though this sounds plausible, it's actually false. The counterxample is the first uncountable ordinal ω₁ [1], viewed as a well-ordered set (and thus a fortiori totally ordered). For every a,b in ω₁, the closed interval [a,b] is countable (by definition), but ω₁ itself is not. [1] https://en.wikipedia.org/wiki/First_uncountable_ordinal https://en.wikipedia.org/wiki/First_uncountable_ordinal
  - rtpg 12y ago
    ah, I remember seeing that in a set theory book I was struggling through at one point. Might be worth a second try so that I don't miss this
miduil 12y ago
Yet another article that is talking about 4k benefits. My primary (and actually biggest) screen at the moment is a laptop with ~12.5 inches 16:9 1366x768 pixels. I do miss a bigger screen, but I'm ok with this size. I'm working with a lot of 'spaces' and I'm using a tiling window manager - which makes things easier. PS: Tree style tab for firefox is really nice for 16:9 screens, since most websites are height and not width.
- dragontamer 12y ago
  The 4k screen thing barely plays a role here. The real discussion is about bijections and infinite sets.
  - miduil 12y ago
    Thank's for pointing that out for me. :) I wasn't sure if I should post the comment, but decided for it - shit happens.
- Dylan16807 12y ago
  The discussion of resolution is entirely in terms of clarity, not size. Imagine if sites and GUIs and fonts no longer had to align to pixels to be crisp.
tedsanders 12y ago
I'm wondering... can't you map all infinite binary strings to all positive integers? If the rightmost digit is the 1s column, the next rightmost digit is the 2s column, and so on, you're just enumerating all possible positive integers. And each time you double (or quadruple) your pixels, you add one (or two) digits in front, getting bigger and bigger integers. But this always stays in the set of integers, which is countable. Am I missing something here? To me, this bijection makes it clear that you'll get a countable number of pixels with a countable number of doublings.
- megablast 12y ago
  Yes, I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? Surely the flipped bit binary string would already appear in the infinite list?
  - pdonis 12y ago
    > I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? That's not quite what the diagonal argument does. Take an enumerated list of infinite binary strings, i.e., the strings are numbered as string #1, #2, #3, etc. Now construct a new infinite binary string in the following way: bit #1 of the new string is the opposite of bit #1 of string #1; bit #2 of the new string is the opposite of bit #2 of string #2; bit #3 of the new string is the opposite of bit #3 of string #3; etc. This new string cannot possibly appear in the list, because for all positive integers n, bit #n of the new string differs from bit #n of binary string #n in the list--i.e., the new string differs from every string in the list by at least one bit. In other words, if we are given any list of infinite binary strings enumerated by positive integers, we can always construct a new infinite binary string that is not in the list. So no such list can ever be complete. Hence, there must be more infinite binary strings than there are positive integers.
- pdonis 12y ago
  > can't you map all infinite binary strings to all positive integers? No. Positive integers are represented by finite binary strings, not infinite ones. Cantor's diagonal argument shows that there is no way to construct a one-to-one mapping between positive integers and infinite binary strings.
cooper12 12y ago
Slightly off topic but: I actually did bail out when I saw the math warning. I had enough of math and infinities in college and just am not curious right now. Still, I think it's very interesting how he tailored his blog post to two audiences: first a general tech/designer audience, and then a second math-oriented audience. Makes me thing how maybe in the future we can have dynamic content like a Wikipedia article about a computer science topic that gets more specific the more programatically/academically inclined the audience is. (As to how you could identify this, one example is adsense, but users might be able to fill in or identify their interests themselves) You can't really make something that fits everyone's purpose perfectly, but it would be a first good step.
- ronyeh 12y ago
  One crazy idea for implementing this would be for everyone to set a flag in their browser that indicates how academically inclined the user is. NERD=0,1,2...9 Then wikipedia paragraphs can just be labeled with the minimum NERD value as a CSS style. The browser can hide paragraphs that exceed your NERD level. If you set NERD=9, you'll see the super dense/academic wikipedia articles.
  - noonespecial 12y ago
    I wholeheartedly agree so long as I can hold ctrl and spin my mouse wheel to increase my Nerd-Zoom.
- gumby 12y ago
  > Makes me thing how maybe in the future we can have dynamic content like a Wikipedia article about a computer science topic that gets more specific the more programatically/academically inclined the audience is. We already have a mechanism for this, which is simply to get increasingly nerdly as you go and let the reader bail out (or skip to the next section) as desired. Newspaper articles are an extreme form of this, with the first paragraph a high level summary and then decreasingly relevant paragraphs with the explicit design objective that the editor / page layer-outer [1] can cut the article pretty much at any paragraph break. So the reader reads until their interest is sated and then stops. Academic articles are (in principle) the extreme opposite of this, with a summary up front and then a largely coherent mass following. [0] is the "d" in nerdly (or gnurdly) an MITism? The Mac's spell corrector doesn't like it. [1] I have forgotten the word for this archaic job. This person did layout after the articles had been typeset.
SamReidHughes 12y ago
I think the followup at the end is wrong, unless I'm misreading. Originally all lines at coordinates k/2^n were drawn and the points not on those lines form an uncountable set (also, between any two points a line we drew is separating them). Then at the end the intermediate representations are counted, which is a completely different thing. An infinite binary tree has countably many nodes and uncountably many paths, yes. The article was fine the way it was.
- sukilot 12y ago
  > points not on those lines form an uncountable set What do you mean? A countable set of lines cuts the screen into a nonsensical "set of regions", you can't do it. The infinite pixel scanline is the set of all finite paths (it's all *terminating binary strings), not the set of all infinite paths. Since the set of cutlines is dense, you can actually name all regions, so the only sensible way to assign pixels is to assign a pixel to every line, not to the space between lines (since there is no nonzero space between lines)
  - SamReidHughes 12y ago
    >A countable set of lines cuts the screen into a nonsensical "set of regions", you can't do it. No, it (the set of lines in question) cuts the screen into a set of points (not regions) -- all the points without a coordinate of the form k/2^n.
- 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.
deevus 12y ago
I thought for a second that he was going to be able to prove infinite pixels to me, until his argument made no mention of diagonality. It makes me think of the paradox "all horses are brown"[0]. It was entertaining though. [0]: http://en.wikipedia.org/wiki/All_horses_are_the_same_color http://en.wikipedia.org/wiki/All_horses_are_the_same_color
ianamartin 12y ago
There's a really good book by David Foster Wallace called Everything and More: A Compact a history of Infinity that traces the origin of the concept and the numerous difficulties the idea faced before becoming more or less accepted as it is today. Highly recommended if you like reading or math. Interstingly, Wallace takes a similar attitude towards those not keen on the details of the Math. There are large swaths where he basically says, "skip this if it makes your head hurt, you won't be missing any of the story." @refrigerator, some of us come from all kinds of different backgrounds and didn't study this in school and wouldn't know anything at all about it if not for books like the one I mentioned above. Who knows? Perhaps Butterick has sparked an interest in some typographer who's never thought about the concept.
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.
malandrew 12y ago
Bijection is a simple idea. But it’s an important tool because it helps keep us out of the counterintuitive weeds when working with infinite sets. For instance, we can now figure this out: are there more positive integers {1, 2, 3, ...} or even integers {2, 4, 6, ...}? The naive answer would be that there must be more positive integers, because the set of positive integers includes both the even and odd integers. But this is wrong. Using bijection, we see that we can put the positive integers and even integers into a one-to-one correspondence like so: 1, 2, 3, 4, ... 2, 4, 6, 8, ... Couldn't you also reason that there are more even integers than positive integers if you start with the notion that you start with a number and start counting in the direction(s) of the defined set: X---> 1, 2, 3, 4, ... ..., -4, -2, 0, 2, 4, 6, 8, ... <--X--> The set of all integers progresses along two vectors with each "count" and only positive increases along a single vector with each count.
- roywiggins 12y ago
  As long as the bijection exists at all, the sets have the same cardinality. To prove two sets don't have the same cardinality, the most direct way is to prove that such a bijection is impossible. Anyway, the bijection from counting numbers to the set of all natural numbers is easy: 1, 2, 3, 4, 5, ... 0, 1, -1, 2, -2, ...
- te_platt 12y ago
  The idea is that if there is any bijection at all between the two sets then they are the same "size". So you can make all kinds of relations between two sets that are not bijections but once you find one you have satisfied the definition of same size in this sense. Note that it is a way of defining size that corresponds to what we mean with finite sets and then extends that definition in a consistent way. So yes you could define a "malandrew size" however you like and see what kind of insights you get.
- pavas 12y ago
  You have an infinite number of both since the counting never ends. In your example, if you've counted n positive integers, you've counted 2n even integers associated with those (by going both ways). But if you continue counting, eventually you will count 2n positive integers (at which point you'll have counted 4n even integers). For any number of even integers that you count, you can just keep counting the positive integers and you'll eventually reach that number. Here's another way to think about it: are there more positive integers than there are positive integers? (Any "correct" approach should say no, or at least not yes.) Using your approach, however, here is a proof that there are more positive integers than there are positive integers. Lets rearrange the positive integers in this manner: X---> 1, 2, 3, 4, ... ..., 7, 5, 3, 1, 2, 4, 6, 8, ... <--X-->
aguynamedben 12y ago
This guy is awesome. He has an online book about typography that convinced me stop typing 2 spaces after periods: http://practicaltypography.com/ http://practicaltypography.com/
- Dylan16807 12y ago
  It has a pretty weak argument for it. It allows two spaces when using a typewriter, even though the spaces are already twice as wide!
xtrumanx 12y ago
> You could take an item out of both bags until you exhausted the supply of one bag. If the other bag was simultaneously empty, then you’d know they had the same cardinality. Well, since you can't exhaust the supply of an infinite supply of integers, I don't see how using this method is acceptable when trying to find a one-to-one correspondence. I feel like I may be missing something so would appreciate if someone could chime in.
- daveFNbuck 12y ago
  This is just an analogy to explain why you would want to find a one-to-one correspondence to compare set cardinalities. Pretty much any real-world analogy will break for infinite sets, but it's fairly straightforward to generalize bijections to infinite sets once you realize it's the right thing to do.
xigency 12y ago
See the continuum hypothesis. The cardinality of the real numbers is two raised to the power of the cardinality of the natural numbers. So: given that there are a countably infinite number of divisions, each doubling the pixel count, there must be uncountably many pixels that result. This is more obvious if you simply view the "infinite screen" as a bounded region of space with coordinates denoted by pairs of real numbers.
- xrayspec 12y ago
  Ordinal and cardinal exponentiation use similar notation, but they don't work the same way. Though it's common to see statements like "ω is the same as \aleph_0," it's misleading, because 2^ω = ω, and thus has lesser cardinality than 2^\aleph_0. See also the "warning" here: http://en.wikipedia.org/wiki/Ordinal_arithmetic#Exponentiation http://en.wikipedia.org/wiki/Ordinal_arithmetic#Exponentiati...
  - xigency 12y ago
    And here we have issues of ordering and uniqueness. There are multiple sequences that correspond to any one point, and in the countably infinite construction, there are points that have no sequence. This is not to say that the first definition is invalid or that the second definition is invalid. It is possible to construct an infinite set that does not contain certain numbers. For example, if the coordinate (1/pi, 1/2) were excluded. In some ways, what is being described at the end is, instead of a fully-filled screen, something that looks like this: http://en.wikipedia.org/wiki/Algebraic_number#/media/File:Algebraicszoom.png http://en.wikipedia.org/wiki/Algebraic_number#/media/File:Al...
- deleted 12y ago
  [deleted]

36 points by lispython 12y ago

deleted 12y ago

[deleted]

What's with everyone's obsession with talking about countable and uncountable infinities? Surely everyone has already read about this stuff by now?

Leszek 12y ago
Relevant counterargument: http://xkcd.com/1053/ http://xkcd.com/1053/
- ChristianBundy 12y ago
  Let me guess – I'm one of today's 10,000? EDIT: Hell to the hell yeah.
  - dragontamer 12y ago
    Which means you weren't one of today's 10,000 (when it comes to xkcd)
arnold_palmur 12y ago
> Surely everyone has already read about this stuff by now? classic.
WhitneyLand 12y ago
What do you mean by that? First of all I'm not even sure this stuff is taught in college outside of a stem degree so I'm sure there are lots of people who have not encountered it. Even for those who have studied it it's sometimes fun to walk through some light proofs, puzzle things out, refresh your memory. It also a nice hook to get people interested in math because it one of the areas where you can use creativity to solve problems without needing many prerequisites.
sukilot 12y ago
We read it so long ago, that we forgot about it.
wetmore 12y ago
You and I are math students, and we both have this sort of reaction when we see such articles. The important thing is to realize that not everyone is a math student.

rtpg 12y ago

Just a guess, but I'm pretty sure that if you have a totally-ordered set (like in your infinite pixel screen, dictionary order on first coordinate followed by second), and all subsets S = {x/ a<=x<=b } are countably infinite, then the set is countably infinite. A constructive proof of this is probably doable by inspiring oneself off of Hilbert's hotel paradox (http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gran...)

ontario 12y ago
Even though this sounds plausible, it's actually false. The counterxample is the first uncountable ordinal ω₁ [1], viewed as a well-ordered set (and thus a fortiori totally ordered). For every a,b in ω₁, the closed interval [a,b] is countable (by definition), but ω₁ itself is not. [1] https://en.wikipedia.org/wiki/First_uncountable_ordinal https://en.wikipedia.org/wiki/First_uncountable_ordinal
- rtpg 12y ago
  ah, I remember seeing that in a set theory book I was struggling through at one point. Might be worth a second try so that I don't miss this

miduil 12y ago

Yet another article that is talking about 4k benefits. My primary (and actually biggest) screen at the moment is a laptop with ~12.5 inches 16:9 1366x768 pixels. I do miss a bigger screen, but I'm ok with this size. I'm working with a lot of 'spaces' and I'm using a tiling window manager - which makes things easier. PS: Tree style tab for firefox is really nice for 16:9 screens, since most websites are height and not width.

dragontamer 12y ago
The 4k screen thing barely plays a role here. The real discussion is about bijections and infinite sets.
- miduil 12y ago
  Thank's for pointing that out for me. :) I wasn't sure if I should post the comment, but decided for it - shit happens.
Dylan16807 12y ago
The discussion of resolution is entirely in terms of clarity, not size. Imagine if sites and GUIs and fonts no longer had to align to pixels to be crisp.

tedsanders 12y ago

I'm wondering... can't you map all infinite binary strings to all positive integers? If the rightmost digit is the 1s column, the next rightmost digit is the 2s column, and so on, you're just enumerating all possible positive integers. And each time you double (or quadruple) your pixels, you add one (or two) digits in front, getting bigger and bigger integers. But this always stays in the set of integers, which is countable. Am I missing something here? To me, this bijection makes it clear that you'll get a countable number of pixels with a countable number of doublings.

megablast 12y ago
Yes, I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? Surely the flipped bit binary string would already appear in the infinite list?
- pdonis 12y ago
  > I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? That's not quite what the diagonal argument does. Take an enumerated list of infinite binary strings, i.e., the strings are numbered as string #1, #2, #3, etc. Now construct a new infinite binary string in the following way: bit #1 of the new string is the opposite of bit #1 of string #1; bit #2 of the new string is the opposite of bit #2 of string #2; bit #3 of the new string is the opposite of bit #3 of string #3; etc. This new string cannot possibly appear in the list, because for all positive integers n, bit #n of the new string differs from bit #n of binary string #n in the list--i.e., the new string differs from every string in the list by at least one bit. In other words, if we are given any list of infinite binary strings enumerated by positive integers, we can always construct a new infinite binary string that is not in the list. So no such list can ever be complete. Hence, there must be more infinite binary strings than there are positive integers.
pdonis 12y ago
> can't you map all infinite binary strings to all positive integers? No. Positive integers are represented by finite binary strings, not infinite ones. Cantor's diagonal argument shows that there is no way to construct a one-to-one mapping between positive integers and infinite binary strings.

cooper12 12y ago

Slightly off topic but: I actually did bail out when I saw the math warning. I had enough of math and infinities in college and just am not curious right now. Still, I think it's very interesting how he tailored his blog post to two audiences: first a general tech/designer audience, and then a second math-oriented audience. Makes me thing how maybe in the future we can have dynamic content like a Wikipedia article about a computer science topic that gets more specific the more programatically/academically inclined the audience is. (As to how you could identify this, one example is adsense, but users might be able to fill in or identify their interests themselves) You can't really make something that fits everyone's purpose perfectly, but it would be a first good step.

ronyeh 12y ago
One crazy idea for implementing this would be for everyone to set a flag in their browser that indicates how academically inclined the user is. NERD=0,1,2...9 Then wikipedia paragraphs can just be labeled with the minimum NERD value as a CSS style. The browser can hide paragraphs that exceed your NERD level. If you set NERD=9, you'll see the super dense/academic wikipedia articles.
- noonespecial 12y ago
  I wholeheartedly agree so long as I can hold ctrl and spin my mouse wheel to increase my Nerd-Zoom.
gumby 12y ago
> Makes me thing how maybe in the future we can have dynamic content like a Wikipedia article about a computer science topic that gets more specific the more programatically/academically inclined the audience is. We already have a mechanism for this, which is simply to get increasingly nerdly as you go and let the reader bail out (or skip to the next section) as desired. Newspaper articles are an extreme form of this, with the first paragraph a high level summary and then decreasingly relevant paragraphs with the explicit design objective that the editor / page layer-outer [1] can cut the article pretty much at any paragraph break. So the reader reads until their interest is sated and then stops. Academic articles are (in principle) the extreme opposite of this, with a summary up front and then a largely coherent mass following. [0] is the "d" in nerdly (or gnurdly) an MITism? The Mac's spell corrector doesn't like it. [1] I have forgotten the word for this archaic job. This person did layout after the articles had been typeset.

SamReidHughes 12y ago

I think the followup at the end is wrong, unless I'm misreading. Originally all lines at coordinates k/2^n were drawn and the points not on those lines form an uncountable set (also, between any two points a line we drew is separating them). Then at the end the intermediate representations are counted, which is a completely different thing. An infinite binary tree has countably many nodes and uncountably many paths, yes. The article was fine the way it was.

sukilot 12y ago
> points not on those lines form an uncountable set What do you mean? A countable set of lines cuts the screen into a nonsensical "set of regions", you can't do it. The infinite pixel scanline is the set of all finite paths (it's all *terminating binary strings), not the set of all infinite paths. Since the set of cutlines is dense, you can actually name all regions, so the only sensible way to assign pixels is to assign a pixel to every line, not to the space between lines (since there is no nonzero space between lines)
- SamReidHughes 12y ago
  >A countable set of lines cuts the screen into a nonsensical "set of regions", you can't do it. No, it (the set of lines in question) cuts the screen into a set of points (not regions) -- all the points without a coordinate of the form k/2^n.
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.

deevus 12y ago

I thought for a second that he was going to be able to prove infinite pixels to me, until his argument made no mention of diagonality. It makes me think of the paradox "all horses are brown"[0]. It was entertaining though. [0]: http://en.wikipedia.org/wiki/All_horses_are_the_same_color http://en.wikipedia.org/wiki/All_horses_are_the_same_color

ianamartin 12y ago

There's a really good book by David Foster Wallace called Everything and More: A Compact a history of Infinity that traces the origin of the concept and the numerous difficulties the idea faced before becoming more or less accepted as it is today. Highly recommended if you like reading or math. Interstingly, Wallace takes a similar attitude towards those not keen on the details of the Math. There are large swaths where he basically says, "skip this if it makes your head hurt, you won't be missing any of the story." @refrigerator, some of us come from all kinds of different backgrounds and didn't study this in school and wouldn't know anything at all about it if not for books like the one I mentioned above. Who knows? Perhaps Butterick has sparked an interest in some typographer who's never thought about the concept.

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.

malandrew 12y ago

Bijection is a simple idea. But it’s an important tool because it helps keep us out of the counterintuitive weeds when working with infinite sets. For instance, we can now figure this out: are there more positive integers {1, 2, 3, ...} or even integers {2, 4, 6, ...}? The naive answer would be that there must be more positive integers, because the set of positive integers includes both the even and odd integers. But this is wrong. Using bijection, we see that we can put the positive integers and even integers into a one-to-one correspondence like so: 1, 2, 3, 4, ... 2, 4, 6, 8, ... Couldn't you also reason that there are more even integers than positive integers if you start with the notion that you start with a number and start counting in the direction(s) of the defined set: X---> 1, 2, 3, 4, ... ..., -4, -2, 0, 2, 4, 6, 8, ... <--X--> The set of all integers progresses along two vectors with each "count" and only positive increases along a single vector with each count.

roywiggins 12y ago
As long as the bijection exists at all, the sets have the same cardinality. To prove two sets don't have the same cardinality, the most direct way is to prove that such a bijection is impossible. Anyway, the bijection from counting numbers to the set of all natural numbers is easy: 1, 2, 3, 4, 5, ... 0, 1, -1, 2, -2, ...
te_platt 12y ago
The idea is that if there is any bijection at all between the two sets then they are the same "size". So you can make all kinds of relations between two sets that are not bijections but once you find one you have satisfied the definition of same size in this sense. Note that it is a way of defining size that corresponds to what we mean with finite sets and then extends that definition in a consistent way. So yes you could define a "malandrew size" however you like and see what kind of insights you get.
pavas 12y ago
You have an infinite number of both since the counting never ends. In your example, if you've counted n positive integers, you've counted 2n even integers associated with those (by going both ways). But if you continue counting, eventually you will count 2n positive integers (at which point you'll have counted 4n even integers). For any number of even integers that you count, you can just keep counting the positive integers and you'll eventually reach that number. Here's another way to think about it: are there more positive integers than there are positive integers? (Any "correct" approach should say no, or at least not yes.) Using your approach, however, here is a proof that there are more positive integers than there are positive integers. Lets rearrange the positive integers in this manner: X---> 1, 2, 3, 4, ... ..., 7, 5, 3, 1, 2, 4, 6, 8, ... <--X-->

aguynamedben 12y ago

This guy is awesome. He has an online book about typography that convinced me stop typing 2 spaces after periods: http://practicaltypography.com/ http://practicaltypography.com/

Dylan16807 12y ago
It has a pretty weak argument for it. It allows two spaces when using a typewriter, even though the spaces are already twice as wide!

xtrumanx 12y ago

> You could take an item out of both bags until you exhausted the supply of one bag. If the other bag was simultaneously empty, then you’d know they had the same cardinality. Well, since you can't exhaust the supply of an infinite supply of integers, I don't see how using this method is acceptable when trying to find a one-to-one correspondence. I feel like I may be missing something so would appreciate if someone could chime in.

daveFNbuck 12y ago
This is just an analogy to explain why you would want to find a one-to-one correspondence to compare set cardinalities. Pretty much any real-world analogy will break for infinite sets, but it's fairly straightforward to generalize bijections to infinite sets once you realize it's the right thing to do.

xigency 12y ago

See the continuum hypothesis. The cardinality of the real numbers is two raised to the power of the cardinality of the natural numbers. So: given that there are a countably infinite number of divisions, each doubling the pixel count, there must be uncountably many pixels that result. This is more obvious if you simply view the "infinite screen" as a bounded region of space with coordinates denoted by pairs of real numbers.

xrayspec 12y ago
Ordinal and cardinal exponentiation use similar notation, but they don't work the same way. Though it's common to see statements like "ω is the same as \aleph_0," it's misleading, because 2^ω = ω, and thus has lesser cardinality than 2^\aleph_0. See also the "warning" here: http://en.wikipedia.org/wiki/Ordinal_arithmetic#Exponentiation http://en.wikipedia.org/wiki/Ordinal_arithmetic#Exponentiati...
- xigency 12y ago
  And here we have issues of ordering and uniqueness. There are multiple sequences that correspond to any one point, and in the countably infinite construction, there are points that have no sequence. This is not to say that the first definition is invalid or that the second definition is invalid. It is possible to construct an infinite set that does not contain certain numbers. For example, if the coordinate (1/pi, 1/2) were excluded. In some ways, what is being described at the end is, instead of a fully-filled screen, something that looks like this: http://en.wikipedia.org/wiki/Algebraic_number#/media/File:Algebraicszoom.png http://en.wikipedia.org/wiki/Algebraic_number#/media/File:Al...
deleted 12y ago
[deleted]