Sizes of infinity fall into two broad classes: countable infinities, and uncountable infinities.
A set is uncountable if it is not countable.
Sizes of infinity fall into two broad classes: countable infinities, and uncountable infinities.
A set is uncountable if it is not countable.
This is a cool page, but I think it (esp. the last paragraph) goes too fast for many math 1 readers, even if it mostly uses things that math 1 people would be able to use. Maybe recategorizing it as math 2 would be best, or expanding things out and being a bit more handholdy, or putting tricky bits as optional hidden text?
Can the image below be cropped? The excessive whitespace is distracting.
Done!
Should be “two tile wide”, right?
Which instance of that are you referring to (there are five)?
Cantor’s argument also works in the finite case and this may serve to demonstrate the idea.
Consider 4-digit binary numbers like 1001. We can use Cantor’s argument to show that there are more than four such binary numbers. Imagine you had a list of four such numbers, say 1001, 1010, 1110 and 0011. Then I can construct a number that can’t possibly be in your list since it differs from the first number in the first digit, from the second in the second etc. In this case the number is 0100.
Nice! I’ve never seen an example like this before, and it’s actually kind of surprising. It seems to imply that 2^N is qualitatively different than N or N^2, but I’m not sure how to phrase it. (And I wonder if there is a relationship between that and P=NP problem.)
A summary of the relevant cardinal arithmetic, by the way (in the presence of choice): ℵα+ℵα=ℵα=ℵαℵα while 2ℵα>ℵα
Thanks!
A^B is the set of functions from B to A. So 2^N is powerset of N (a function f from N to {0, 1} says, for each element of N, whether or not that element is in the subset defined by f), which is isomorphic to the reals. Perhaps this should go somewhere in one or more of the versions. I don’t know any connection between this and P=NP (although I suppose it could be behind the exponential bounds on various things).