Cardinal Arithmetic

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.

Tags

More like this

One of the strangest, and yet one of the most important ideas that grew out of set theory is the idea of cardinality, and the cardinal numbers. Cardinality is a measure of the size of a set. For finite sets, that's a remarkably easy concept: count up the number of elements in the set, and that's…
With ordinals, we use exponents to create really big numbers. The idea is that we can define ever-larger families of transfinite ordinals using exponentiation. Exponentiation is defined in terms of repeated multiplication, but it allows us to represent numbers that we can't express in terms of any…
Writing this blog, I get lots of email. One of the things that I get over and over again is a particular kind of cluelessness about the idea of infinity. I get the same basic kind of stupid flames in a lot of different forms: arguments about Cantor's diagonalization; arguments about calculus (…
Even though this post seems to be shifting back to axiomatic set theory, don't go thinking that we're done with type theory yet. Type theory will make its triumphant return before too long. But before that, I want to take a bit of time to go through some basic constructions using set theory. We'…

I attempt to cover

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? :-)

By Torbjörn Lars… (not verified) on 11 Jun 2007 #permalink

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!

Torbjörn: do you hang out over at The n-Category Café at all?

Yes in fact, since math isn't really my ordinary cup of tea (>_<). Usually it's more like sprightly coke.

Which doesn't stop me from commenting at times, it seems. We passed each other on a thread, btw ( 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.

But, to get the whole theory to work, we need something to describe the concept of 'phase', which is so important in quantum mechanics. Jeff got the job done by replacing sets by U(1)-sets: sets whose elements are labelled by phases. [On "This Week's Finds in Mathematical Physics (Week 252)"]

( http://golem.ph.utexas.edu/category/2007/05/this_weeks_finds_in_mathema… )

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.

By Torbjörn Lars… (not verified) on 12 Jun 2007 #permalink

Um, I forgot the mess HTML will do with some emoticons.

math isn't really my ordinary cup of tea (>_<)

By Torbjörn Lars… (not verified) on 12 Jun 2007 #permalink

|X|^|Y| = |{f : YâX}| - that is, the cardinality of the set of all functions from Y to X. Which, if you stop and think about it, is the powerset of XÃY.

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.

By Ãrjan Johansen (not verified) on 12 Jun 2007 #permalink

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.

By Ãrjan Johansen (not verified) on 12 Jun 2007 #permalink

Do the digits of pi have the same cardinality as the naturals?

By Anonymous (not verified) on 12 Jun 2007 #permalink

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), ...}

By Antendren (not verified) on 12 Jun 2007 #permalink