Beyond infinity

In the Disney/Pixar film Toy Story, one of the lead characters likes to use the catchphrase "To infinity and beyond!" But what is beyond infinity? As a child, we seem to believe that there are things beyond infinity, especially when we are comparing, i.e. "my toy car is infinity times faster than your car.", "no, my car is infinity plus one times faster.", etc.

In a branch of mathematics called Set Theory, an effort is made to count beyond infinity. First numbers are associated with sets. The number 5 is associated with a set of 5 items. Then a number is larger than, equal to or smaller than another number if the corresponding sets have more items, the same number of items or have less items. One of the consequences of counting this way is that we can extend it to infinite numbers. How do we count whether two sets of objects are of equal size or not? Two sets are of the same size if we can associate each member of the first set with exactly one member of the second set and every member of the second set is associated to some member of the first set. Such a mapping is called a bijection. A map which assigns to a member of a first set exactly one member of the second set is called an injection. A famous result known as the Cantor-Bernstein theorem states that a bijection between two sets exists if and only if there is an injection from the first set to the second set and an injection from the second set to the first set.

With this definition, Cantor shows that the set of even integers is the same size as the set of all integers: just assign each integer n to the number 2n. Intuitively this is strange since the set of even integers is a strict subset of the set of integers.  What is more remarkable is that the set of rational numbers p/q where p and q are integers is also the same size as the set of integers, even though there are infinitely number of rational numbers between any two integers. This infinity is denoted as Aleph-zero. So in this context the child's argument of saying "infinity plus 1" is really not any bigger than "infinity".

So are all infinite sets of the same size? Cantor showed using a diagonalization argument that the set of real numbers is strictly larger than Aleph-zero. In fact, given any set, infinite or not, the power set, i.e. the set of all subsets, is strictly larger. Thus for any infinite set, we can create one that is strictly larger. For a finite set of size n, the power set has 2ⁿ elements. For instance, the set {1,2,3} has as its power set {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} with 8 elements. Analogously, the size of the power set of Aleph-zero is denoted as 2^Aleph-zero and is the size of the set of real numbers. The Continuum Hypothesis states that the next strictly larger infinity beyond Aleph-zero is equal to 2^Aleph-zero. It was shown in 1963 by Cohen that this hypothesis is not provable using the assumptions (axioms) of standard set theory.

All this talk about infinity might seem abstract, but it did find its way into the foundation of computer science. In fact, the same diagonalization argument that Cantor used to show that the real numbers is "more infinite" than the integers is used by Turing to show that there are problems that are uncomputable, i.e. there does not exists a computer algorithm that can solve this problem. A famous uncomputable problem is the halting problem: given a computer program with a given input, determine whether it will ever end executing or not.

Palindromic merchants

When I first moved to New York, I was driving down the road and saw the car in front of me with the label: "ADZAM". I thought to myself: "That's odd. ADZAM is MAZDA spelled backwards, and the car in front of me was a Mazda. Perhaps the owner of the car feels the need to display the make of his/her car as you pass by on the opposite lane and view the back of the car in your mirrors (much the same way the word AMBULANCE is spelled in mirror image on the front of an ambulance). Only later did I figure out that Adzam Mazda is the name of a car dealership with an palindromic name, it is spelled the same forwards and backwards. This reminds me of an article on palindromes by Martin Gardner (one of my favorite authors) that I read as a youngster (the article is most recently reprinted here). He mentioned the existence of a bakery in Yreka, CA called Yreka Bakery, which is a palindrome. He also noted that this store is not longer in business, but was replaced by Yrella Gallery, also a palindrome.

The big and the small

Scientists have long studied extremes. Astronomers have long studied objects that are very large, such as galaxies and universes, whereas chemists and biologists have studied things that are very small, including atoms, molecules and microscopic organisms. The book "powers of ten" by Philip and Phylis Morrison gives an excellent visual demonstration of things at various scales.
It is no wonder that when marketers need superlatives to describe their products, they look toward scientific jargon. Apple has an mp3 player called the Nano, my son has a robot called Megatron, and there is a lottery in the USA called Mega Millions, even though as far as I know the prize money is much less than a trillion (or a billion for those of you in long scale countries).

Nano and Mega are part of a class of prefixes that are used to modify units in powers of ten. For instance a kilo-meter is 1000 meters, and a centimeter is 1/100th of a meter. According to the international systems of units (SI), the following prefixes are defined:

yocto, zepto, atto, femto, pico, nano, micro, milli, centi, deci, deca, hecto, kilo, mega, giga, tera, peta, exa, zetta and yotta.

It is interesting to note that as technology evolves, more and more of these prefixes become commonplace. Most of us are familiar with kilo as used in kilogram. Radio waves provides us familiarity with mega as the FM stations operate in the megahertz range. As computer processors increase in speed, we have for the last decade or so been working on computers with gigahertz processors. Memory density has also increased dramatically with personal computer memory, both volatile and nonvolatile, routinely in the gigabytes range today. The world's fastest computers have recently broken the petaflop (10¹⁵ flops) barrier and business and scientific computers routinely deal with terabytes and petabytes of data and will need to access exabytes in the not too distant futures. Sometimes the prefix is omitted; for instance the calorie unit we see on food packaging should more accurately be called a kilocalorie since it is the energy needed to raise the temperature of 1 kilogram of water by 1 degree Celsius.

One interesting note about measuring computer memory using the SI prefixes. Modern computer memory locations are indexed using a binary address, i.e. a series of binary digits (or bit). For instance, 1 bit can denote two locations, since it can have the value 0 or 1. On the other hand, 2 bits can denote four locations, i.e 00, 01, 10 and 11. In particular, n bits can denote 2ⁿ locations. This is why computer memory is generally arranged in chunks whose size is a power of 2. Ten bits can address 2¹⁰ = 1024 locations. If each location contains one byte of memory, then 1024 bytes is referred to a kilobyte. 16 bits can address 2¹⁶ = 64* 2¹⁰ = 64 kilobytes even though 2¹⁶ is really 65,536. This deviation from the SI usage of the prefixes can cause confusion and thus in 1998 prefixes were introduced which are powers of 2:

kibi, mebi, gibi, tebi, pebi, exbi, zebi, yobi.

For example, 1024 bytes is referred to as a kilobinarybytes or a kibibyte whereas 2⁸⁰ = 1208925819614629174706176
bytes is called a yobibyte. As of this writing, these binary prefixes are still not commonly used in the scientific literature (although I did use it here). I wonder when we will start seeing products named after these prefixes?

A related note on the subject of very small and the very big, the word quantum in common usage means a significant or sudden amount as in "a quantum leap". On the other hand, its usage in physics is almost the opposite; a quantum is the smallest indivisible unit of a physical property.