I am trying to get an understanding, in layman's terms / on an intuitive level, why some arguments about the countability of infinite sets are valid, and some arguments which seem almost identical on the surface are nevertheless invalid. Consider, for example, the following:

1) This way of counting rationals (see link), where they arrange the rationals in a grid and come up with an algorithm of traversing all of them in diagonal lines. Clearly, every rational number will be reached using this method.

2) The following way of counting the members of the power set of natural numbers: Map the Nth natural number to the Nth digit of a binary number X, and start counting from X=0 upwards. So X=...000000 represents the empty set, X=...000001 represents {1}, X=...000010 represents {2}, X=...000011 represents {1,2}, and so on. Clearly, every subset of the natural numbers N will be reached using this method (except perhaps the full set of all natural numbers, but we can just count it at the beginning and shift everything by one).

I am trying to understand why (1) above is a valid explanation for the countability of rationals (the page I linked to even calls it a "proof"), while (2) above clearly doesn't work because the power set of the naturals is uncountable. The two arguments seem very similar to me, so I can't quite understand why one works and the other doesn't. Again, an intuitive-level explanation would be really appreciated.

  • $\begingroup$ There is no way to arrange your binary sequences so that there is a first sequence, a second, and so on, with none left over. $\endgroup$ – Brian M. Scott Apr 24 '16 at 1:20
  • 1
    $\begingroup$ I think the OP is planning on arranging them in binary number order, the problem being that this ignores infinite sequences. $\endgroup$ – Davey Apr 24 '16 at 1:23
  • $\begingroup$ Beware the argument that hinges upon ... in unfamiliar contexts. Many errors can be swept beneath that rug. $\endgroup$ – hardmath Apr 24 '16 at 1:34

Neither argument is complete. In each case, it's not enough to provide a listing of some of the set you want to show is countable; you also need to show that this list contains all the elements of that set.

In the former case (the rationals), this isn't too hard; but technically it takes an argument. In the latter case (sets of naturals), this is in fact false: for example, in the list you suggest, the set $\{$evens$\}$ will never occur.

So that's the difference. Each argument has provided a list of some elements of a set; the issue is when we try to finish the argument by showing that that list contains the whole set. In the former case we can do this, in the latter we can't.

You might object: "But I did argue that every element of the set appeared on the list!" Well, not really - you said "Clearly ..." without any further justification. Always beware of "clearly," "obviously," "trivially," and the like - just asserting something isn't the same as proving it, and chances are the point your argument breaks down is exactly where you thought it was so airtight you didn't even need to write it. (By the way, this goes for the rest of us too - almost every time I think I've proved something but failed, it turns out the error was where I wrote "Proof: trivial" or the like in my notes. You'd think I'd learn, but . . .)

  • $\begingroup$ Thanks, this is helpful. So to continue the thought, let me know if the following is true: In case (1), the rationals, for any given rational "r" the arrows algorithm tells you how to reach "r" in a finite number of steps. In case (2), given a set "s", the binary number approach sometimes fails to produce the set "s" in a finite number of steps (e.g. for "s"={evens}). Is this ability to reach any given value in a finite number of steps what's crucial to proving countability, or am I on the wrong track here? $\endgroup$ – Eugene Osovetsky Apr 24 '16 at 1:38
  • $\begingroup$ @EugeneOsovetsky Well, it depends what you mean by "reach in a finite number of steps" - but I think you're on the right track. To show an infinite set $A$ is countable, you need to provide a bijection $f$ from $\mathbb{N}$ to $A$, and then verify that it is in fact a bijection. Specifically, you need to show "For each $x\in A$, there is some finite number $n$ such that $f(n)=x$." I don't necessarily think of this as "reaching each $x\in A$ in finitely many steps", but if this is what you're thinking, then that's right. $\endgroup$ – Noah Schweber Apr 24 '16 at 1:45

The first argument is perfectly valid. The second ignores infinite subsets of the natural numbers: any infinite subset (e.g., the set of all odd natural numbers) doesn't correspond to the binary expansion of any natural number, so all the argument shows is that there are countably infinitely many finite subsets of the natural numbers.

  • $\begingroup$ The second argument only counts the finite subsets of N. We can also count the subsets of N whose complements are finite. But this still leaves out uncountably many others .+1 $\endgroup$ – DanielWainfleet Apr 24 '16 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.