Sunday, February 18, 2007

Arbitrarily large vs. infinite

Infinity is a subtle mathematical notion, which is logically related to -- but not synonymous with! -- the notion of "arbitrarily large". Actually, when dealing with limiting values of magnitudes, the two more or less coincide. When we say that the series
1 + 1/2 + 1/3 + 1/4 + ... = Infinity
what we mean is that no matter now big of an N you pick, I can always find enough terms in that series whose sum will exceed N. In this case, infinite really is shorthand for "increasing without bound" or becoming "arbitrarily large".

When dealing with cardinalities -- as opposed to magnitudes -- all bets are off. That was the crux of the closure under star question. [BTW, I think I've found the bug in Ivan's proof that closure under concatenation implies closure under star. The set U need not be a complete lattice. Otherwise, your argument could be used to show that the function f:Z->Z defined on the integers by f(x)=x+1 has a fixed point.] Set theory is rife with examples where some property P holds for arbitrary finite collections but not infinite ones:
  • in point-set topology, a finite (but not necessarily countable) intersection of open sets is open
  • in analysis, there are finitely (but not countably) additive measures
  • etc

There are techniques, most (all?) of them based on transfinite induction, for proving that P holds for infinite collections given that it holds for arbitrary finite ones. Knaster-Tarski is one; Hausdorff maximality principle and Zorn's lemma are other favorites. All are equivalent to the axiom of choice.

4 comments:

Victor said...

This is an interesting philosofical question. I remember an article in the late 70s by the famous mathematician Zeldovich, which questioned, whether or not there is anything "existing" in the Universe, count of which could exceed a certain finite number.

If you think "by analogy" [not terribly mathematical, I admit, but I am using the ancient "as above so below" method] than since the number of water moleculs [or even electrons] on Earth is definitely not-infinite, so should be the number of ANY particles in the Universe.

So how applicable our mathematical operations involving the infinity?

Leo said...

According the most (all?) modern theories, the number of particles in the universe is indeed finite; 10^80 is the typical bound people give.

But that's the physical world -- which, as I've argued before, has nothing to do with mathematical constructions!

Platonism notwithstanding, there are various mathematical schools of thought that limit the size of the sets they can deal with. Let's start with us "mainstream" mathematicians; we want to prove theorems about infinite-dimensional vector spaces and have no compunction about applying transfinite induction with wanton abandon. Then you have the constructivists, who rule out uncountable sets and operations. Getting nuttier (er... more restrictive!) yet, we have the finitists, who only deal with finite sets. The most extreme puritans are the ultrafinitists, who don't even allow really large finite numbers. Rather than dismiss them out of hand though, check out this amusing anecdote.

Enough with the philosophy -- do these infinities really exist, you might ask? That would be the wrong question. Axioms are chosen, among other factors, based on their ability to yield fruitful theories. In functional analysis, we can't get very far without the axiom of choice, so we sure as heck are going to use it -- finite universe be damned.

Victor said...

I used to think the way you do - play my own logical games on any chosen set of axioms as long as it feels good. Now, however, I am interested to learn the internals of the physical Universe. So, instead of assuming, e.g. that "the noise-to-signal ratio is negligible" I'd rather assume that "the noise is substantial" and try to design a compensation algorithm, say, using an independent source of information [like a second or even a third watch]. By the way, the Kabbalistic "Book of Creation" [Sefer Yetzirah] talks about the fifth dimension [in addition to the 4 we know]: "good" - "evil". That sounded rather odd until I saw a Chinese "Dao" book on how the constellations are mapped to our heads, with the Polar Star being the pole of "good" and "Vega" the pole of "evil".

Nilay said...

The post mentions that finite is not necessarily countable. I think this should be the other way round. Finite is always countable but countable need not be necessarily finite.