This is a short post, in which I attempt to cover up for the fact that I forgot to include some important stuff in my last post.
As I said in the last post, the cardinal numbers are an extension of the natural numbers, which are used for measuring the size of sets. The extended part is the transfinite numbers, which form a sequence of ever-larger infinities.
One major problem with adding the transfinite numbers is that natural number arithmetic doesn’t work anymore with the cardinals. It still works for the natural number subset of the cardinals, but not for the transfinites.
But we *do* want to be able to talk about at least certain kinds of arithmetic on the full set of cardinals. So we need to figure out what arithmetic means for this strange sort of number.
First thing we can say for sure is that for the finite cardinals, arithmetic continues to work exactly as we expect it to: if there’s are finite cardinals a and b, then natural number addition of a+b and cardinal addition of a+b had better be the same.
Second, we need to make sure that we preserve some of the essential properties of arithmetic: both addition and multiplication need to be commutative and associative, and multiplication needs to be distributive over addition. We can also create a weakened generalization of a property of addition and multiplication over the natural numbers. For the natural numbers, we can say that if a and b are greater than 0, then a+b is larger than either a or b. Similarly, if a and b are greater than 1, then a×b is larger than a or b. For the transfinites, we can’t say larger that, but we can say not smaller than: so for any two transfinite numbers a and b, a+b is not smaller than a or b; and for any two nonzero transfinite numbers, a×b is not smaller than a or b.
With those properties in mind, we can ask what makes sense for extending arithmetic operations to work for all cardinals, including the transfinites.
What happens when you add one to infinity? You still have infinity. That’s what happens with the transfinites as well: 1+ℵ0=ℵ0. In fact, we can generalize that: if T is a transfinite number, and x is a (finite) natural number, then x+T=T. And since the relationship between a finite number x and ℵ0 is the same relationship as between ℵ0 and ℵ1; and that, in turn, is the same as the relationship between ℵn and ℵn+1 for any N, we can say that if a and b are transfinite cardinals, then a+b is the maximum of a and b.
This makes particularly clear sense if you remember that the transfinite numbers aren’t real numbers – they’re infinites that provide a measure of the size of a set. Using that, if |X| is the cardinality of set X, we can define transfinite addition in terms of sets: |X|+|Y|=|X∪Y|.
Multiplication ends up working the same way: a×T, where a is finite and T is transfinite, is always T; and if T and U are transfinite, then T×U is the maximum of T and U. In terms of sets, |X|×|Y|=|X×Y| (that is, the cardinality of the cartesian product of X and Y).
Finally, there’s exponentiation, which is pretty neat. For exponentiation, we use functions. |X||Y| = |{f : Y→X}| – that is, the cardinality of the set of all functions *from* Y to X. So, if we want to know the cardinality of the powerset of an infinite set T, it’s the cardinality of |T||T| – aka the cardinality of the powerset of T→T ⊆ the powerset of T×T= 2T. Which is exactly what we would expect. *(Note: originally I garbled this, due to confusing the cardinalities of functions from Y to X and relations from Y to X, which are subtly different, as commenter Oerjad pointed out. Unfortunately, he had to point out the error twice to try to get me to fix it properly! Hopefully, the third time is the charm. Thanks for the correction!)
Finally, does 2T make sense as a notation for the powerset? Well, for finites it does. For example, given a set of size 5, there are 25 subsets of it. What about transfinites?
Let’s work it through with an example: |{0,1}T| = |{f : T→{0,1}}|. What can we say about that set of functions? Treat “1” as “true” and “0” as “false”, and it’s a set of functions, each of which maps from members of T to either true or false. Then each function f essentially defines a subset of T – the subset including the members of T for which f is true. So it is the same as the powerset of T.
That would be the open cover, I assume?
More seriously, while I’m not so worried about addition and multiplication (perhaps because I’m used to do it with functions with potentially infinite vectorial decompositions), it is good to see the motivation for the powerset and its notations.
Without having any particular idea if it is a correct belief or why, but it seems to me exponentiation often pops up in theoretical physics in integrals (paths) over choices, which most often go over my head. Perhaps there is a connection, though…
Btw, there is the obligatory unclosed HTML clause. (‘Unclaused’ HTML? 🙂
Torbjörn: do you hang out over at The n-Category Café at all? You might find something you’re interested in there.
More generally, all of this cardinal arithmetic works because the cardinal numbers are the decategorification of the category of sets. A cardinal number can be called the “size” of a set, but what it amounts to is an isomorphism class in the category. Products and coproducts decategorify to multiplication and addition, and so on.
The physics comes in when you try to adjust the category to get different kinds of “cardinality”. Jeff Morton (under the guidance of John Baez) has some great results in explaining things like path-integrals using a category of “U(1)-graded” sets, for instance.
Greetings,
would be nice if you could close the sup – Tag please when you talk of cardinality of powerset T. The subject at hand is rather large but the font size does not reflect this 🙂
This, and your previous post have been the most lucid, intuitive and straightforward explanation of cardinality and the transfinites that I have seen – bravo!
Yes in fact, since math isn’t really my ordinary cup of tea (>_http://golem.ph.utexas.edu/category/2007/05/linear_algebra_done_right.html ).
And I probably need to get to study QFT to get these transformations. I don’t know if it’s just expressing a phase (as I assume the unitary group U(1) may be doing on an inner product space in its multiplicative wisdom) or if it is any other reason that makes exponents show up at times.
( http://golem.ph.utexas.edu/category/2007/05/this_weeks_finds_in_mathematic_13.html#c009982 )
But the “Quantum and Cohomology” course would go over my head. (“The big picture. Building a Hilbert space from a finite category C equipped with an “amplitude” functor A: C → U(1).”) I really need some physics to go through some actual examples first.
Um, I forgot the mess HTML will do with some emoticons.
No, the powerset of X×Y is the set of relations between X and Y, not functions. That set doesn’t always have the same cardinality. For example, if X are the reals while Y are the natural numbers, then |X|^|Y| = (2^aleph_0)^aleph_0 = 2^(aleph_0*aleph_0) = 2^aleph_0, but
2^(|X|*|Y|) = 2^(2^aleph_0 * aleph_0) = 2^(2^aleph_0), which is larger by Cantor’s proof.
Orjan:
Good catch. I’ve corrected the article.
Erm, sorry, the article is still wrong. |X|^|Y| should definitely be defined using the set of functions. The power set of X×Y does not enter into it.
Do the digits of pi have the same cardinality as the naturals?
Anonymous: your question is somewhat ill-posed as it stands. What set are you asking for the cardinality of?
He’s asking about the number of digits counted with multiplicity. Yes, it has the same cardinality as the naturals.
To make it formal, the set:
{(a,n) : floor( pi*(10^n) ) = a (mod 10) }
= { (3,0), (1,1), (4,2), (1,3), (5,4), (9,5), …}