Winstonm, on Apr 6 2009, 02:56 AM, said:
Having virtually zero math background I have to rely on whatever basic intellect I have to try to grasp this stuff - but I was of the understanding that Infinity times anything = infinity, so I(X)=I(Y) regardless.
Right, but Blackshoe was not refering to Infinity*Infinity.
Consider the set of all integers. This is the "smallest" infinite set - some might think that the set of even numbers, which is also infinite, must be smaller, but that is not true. "Smaller" here in the sense of cardinality. That concept is defined on the basis of parings between two sets:
{a,b,c} has the same cardinality as {x,y,z} because you can construct the pairing
(a,x) (b,y) (c,z)
By the same token, the set of positive integers can be "paired" with the set of positive even integers, by
(1,2)
(2,4)
(3,6)
more generally:
(x, 2*x)
However, some infinite sets have larger cardinality than the integers. Consider for example the set of all subsets of the integers - including all infinite subsets such as for example the set of even integers.
Cantor showed that the set of subsets of the integers does not have a pairing with the set of integers. (Ken gives the proof in the above post that the set of numbers in the interval [0,1] has larger cardinality than the integers - this is basically the same).
Now a question:
Is there a set that has larger cardinality than the integers but at the same time smaller cardinality than the set of integers?
The assertion that there is no such set is called the Continuum Hypothesis.
Interestingly, the continuum hypothesis can neither be proved nor disproved. When it matters (rarely!), mathematicians conventionally decree by axiom that the continuum hypothesis is false, i.e. there is such an intermediate set. Equally valid, one could decree that it is true, but that would lead to some less intuitive results.
Finally, let me give the motivation for why Blackshoe calls the cardinality of the set of subsets of the integers 2^Aleph0, where Aleph0 is the cardinality of the integers.
Consider the set {No,Yes}. That set has cardinality 2. Now consider some set, say threefruits = {Apple, Banana, Clementine}. What is the cardinality of the set of subsets of threefruits? Such a subset is specified by, for each fruit, specifying whether it belongs to the subset or not. For example, the set
{Apple,Clementine}
could also be written as the tubble
{Yes,No,Yes}
The first element in the tubble can take two values (yes or no), so can the second, so can the third. So the number of subsets becomes 2*2*2. More generally, the number of subsets of Nfruits is 2*2*...*2 (N times), i.e. 2^N. Therefore, if some infinite set has cardinality A, where A is now a transfinite number rather than an ordinary integer, we call the transfinite number of subsets of that set 2^A.
As you noted, Aleph0+Aleph0 = Aleph0 and also Aleph0*Aleph0 = Aleph0. However, 2^Aleph0 is different!
Lol, just noticed the overlap between this and Ken's post.
The world would be such a happy place, if only everyone played Acol :) --- TramTicket