Page images
PDF
EPUB

the A;'s are disjoint.

Ulam considered special measures that satisfy some additional conditions:

Ci: u(A) = 0 whenever A consists of just one element of X;

C2: u(X) = 1 (that is, the measure of the whole space is 1); and

C3: N is the set of all subsets of X.

has the following property: If we multiply less than Xo cardinal numbers each of which is less than No, then the product is also less than No. Well, of course, this tells only that the product of finitely many integers is finite. Thus we can say that No is inaccessible by products. This property is also called strong inaccessibility: No is strongly inaccessible. Are there any cardinal numbers larger than Xo (such cardinals are called uncountable) that are also strongly inaccessible? It turns out that this problem cannot be solved. The axioms of set theory do not imply the existence of such cardinals, and one can only postulate their existence as an axiom, which is what Felix Hausdorff did. Indeed, a set theory in which we accept this axiom is stronger (in the sense that it gives rise to more theorems of arithmetic) than the original set theory of Cantor and Zermelo.

To explain the work of Ulam we need the concept of a measure. For a set of points on the plane, area is a measure, and for a set of points in three-dimensional space, volume is a measure. In general given any set X, a measure is a function f

that attaches to subsets of X some nonnegative numbers in such a way that the following condition is satisfied:

countably additive measure satisfying C, C2, C3, and C4 is called an Ulam cardinal. Again, we can ask whether

any

Ulam cardinals exist. Ulam's famous theorem is that if such a cardinal does exist, then it is strongly inaccessible. This result implies that if we consider two set theories, one in which we assume the existence of uncountable strongly inaccessible cardinals and the second in which we assume the existence of Ulam cardinals, then the second theory is at least as strong as the first. Today we know many interesting theorems that follow from postulating the existence of Ulam cardinals. In particular, thirty years after Ulam's paper on measurable cardinals, William Hanf and Alfred Tarski proved that the least uncountable strongly inaccessible cardinal is smaller than the least Ulam cardinal. Thus a set theory in which Ulam cardinals exist is strictly stronger than one in which only uncountable strongly inaccessible cardinals exist. Many more results of this sort have been discovered since. The theory of large cardinals has become very rich, but Ulam's paper remains one of its keystones.

Measures that satisfy Co, C1, C2, and C3 are called universal measures. Readers familiar with Lebesgue's measure may recall that it is not a universal measure since the collection N2 on which it is defined is not the set of all subsets of (0,1). On the other hand, Lebesgue's measure is invariant under translations, whereas the set X is just an abstract set without any transformations upon which y could be assumed to be invariant. Even in this abstract setting it is very difficult to construct a universal measure. For example, if X is countable, no such measure exists since condition C, plus countable additivity forces u(X) to equal 0, contrary to C2.

Ulam proved two fundamental results about universal measures. The first tells that no universal measure exists for many uncountable sets. In particular, for many consecutive cardinals larger than No (for example, 81, 82, ..., X. Xw+1,...), sets of those cardinalities do not have universal measures.

To explain Ulam's second result, we restrict the concept of universal measure still further by adding the following condition:

Ergodic Theory and Topology

Co: If A and B are disjoint subsets of X, then u(AUB) = u(A) + u(B).

There are many variants of the concept of measure. The version that is the most important for mathematical analysis says that u(A) must be defined for all subsets A of X that are in a collection N of subsets such that 12 is closed under countable unions and complementations. That is, if A; E N for i = 1,2,..., then the union of the A;'s is in 52, U-A, EN, and if A; ES2, then its complement, or X – A;, is in N. Moreover the measure u must be countably additive; that is, if A; ES2, then u (U., A;) = Lirim(A;), provided

Between 1929 and 1938 Ulam published about twenty papers. What distinguishes those from the papers of other members of the Polish school before 1939 was his interest in topological groups, especially the groups of homeomorphisms of spheres.

A homeomorphism of a space X is a transformation of X onto itself that is oneto-one and continuous and whose inverse is also continuous. Of course such transformations constitute a group under composition. It is not obvious how to introduce a natural topology or even metrization into such a group. The following formula was often proposed (for example, it appears in Banach's classic book Théorie des Operations Linéaires): The distance between two homeomorphisms f

C4: M(A) = 0 or u(A) = 1 for all subsets A of X.

The cardinal number of a set that has a

EFFECT OF AN ERGODIC

and g of a compact space X, Dist(f.8), is given by

TRANSFORMATION

[blocks in formation]

Fig. 2. If n is an ergodic transformation, every surface S separating the water is deflected by h from its original position.

[ocr errors]
[subsumed][ocr errors]

where dist denotes the distance in X.

The surprising property of this formula is that it converts the space of homeomorphisms of X into a complete metric space. In other words, if a sequence of homeomorphisms satisfies the condition of Cauchy, then it has a limit that is a homeomorphism. The fact that the space of homeomorphisms can be treated as a complete metric space is very important because for such spaces there exist very natural definitions of largeness or smallness of subsets. The small ones are called meager (or of the first category) and the large ones comeager (or complements of meager). These topological concepts were invented by Baire. Several brilliant applications of these notions were made by Banach and Mazur. A very famous one was made by John C. Oxtoby and Ulam around 1941. Let me try to describe it here.

Take a glass of water, gently stir its contents, and let the water stop moving. Each particle of water has an initial and final position. The operation has thus defined a transformation of the interior of the glass into itself. Since water is viscous, this transformation is continuous and its inverse is also continuous. So we have here a homeomorphism. Moreover, since water is incompressible, the homeomorphism is volume-preserving. Homeomorphisms with that property constitute a complete subspace of the space of all homeomorphisms. If our transformation had been a simple rotation, then the altitudes of the particles of water and their distances from the central axis of the glass would not have changed. Many parts of the water would have remained invariant; that is, such parts would have been mapped into themselves. Even if we had

applied the rotation many times, the water would never have been mixed. Are there any volume-preserving homeomorphisms that do mix? Such transformations, which are called ergodic, or metrically transitive, must exist if the ergodic hypothesis of statistical mechanics is correct. However, the existence of such transformations had remained an open question since the work of Poincaré and G. D. Birkhoff. Oxtoby and Ulam, in their paper entitled “Measure-Preserving Homeomorphisms and Metrical Transitivity,” showed not only that such homeomorphisms exist but also that the set of ergodic homeomorphisms is comeager, that is, large in the sense of category. More precisely, any homeomorphism of that comeager set has the property that its application to any proper part of our glass of water deflects its boundary (Fig. 2). Thus the homeomorphism mixes the water in the sense that no part returns to its initial position. The OxtobyUlam theorem remains one of the high points of the mathematical theory concerning ergodic properties of dynamical systems. The introduction to their paper, excerpted on the following page, explains the connection to the ergodic hypothesis. (These excerpts may be better understood after reading “The Ergodic Hypothesis: A Complicated Problem of Mathematics and Physics," as well as the section entitled Problem 2. Geometry, Invariant Measures, and Dynamical Systems in the article "Probability and Nonlinear Systems, all in this issue.)

We must caution, however, that application of mathematical theorems to the real world is sometimes a delicate problem. As you know, a sequence of heads and tails obtained by consecutive tosses of a fair coin has the property that the frequency of heads converges to 1/2 as the number of tosses becomes large. One can say (and prove in precise mathematical terms) that if we choose a sequence at random from the space of all such sequences, then, with probability 1, the lim

[graphic]
[graphic][subsumed][merged small]

Topics in Biology and
Some Applications of Computers

tells the following: For every continuous mapping of the spherical surface into the plane, there exist antipodes that are mapped into the same point on the plane. This theorem is equivalent to the following statement. Given three bodies (say ham, cheese, and bread), one can find a single plane that divides each body into two parts of equal volume. (Each body may consist of disjoint pieces, as does the bread in a sandwich, and the bodies may overlap, as shown in Fig. 3a.) Another equivalent statement is that at any time antipodal points can be found on the earth where the temperature and the barometric pressure are the same (Fig. 3b).

I began to collaborate with Stan Ulam in 1969 when he invited me to the University of Colorado in Boulder. We spoke frequently about the problems of the organization and function of the human brain and the structure of memory. He presented his ideas on this subject in the talk “Reflections on the Brain's Attempts to Understand Itself,” which is posthumously published in this issue.

We also talked often about the problem of accumulation of mutations in a given species. As a result of our discussions I

phisms of a cube are ergodic suggests the physically false result that almost all sequences of heads and tails lack a welldefined frequency of heads. Can we then trust the theorem of Ulam and Oxtoby as an expression of the truth of the ergodic hypothesis in physics? Stan and I often discussed this question. We thought that the answer is yes, but what is really needed is a new theorem in which almost all, in the sense of category, is replaced by some other more reliable sense. (I have outlined an idea of such a new theorem or conjecture in two papers in Journal of Symbolic Logic, one in volume 46 (1981) and the other in volume 51 (1986), but I do not know how to prove it.

Ulam and Jósef Schreier obtained another interesting result about the group of homeomorphisms of a spherical surface. They proved that there exist two special homeomorphisms such that every homeomorphism in the group can be approximated with arbitrary accuracy (relative to the distance defined above) by appropriate iterative compositions of those two homeomorphisms and their inverses.

Kuratowski and Ulam proved an extension of the theorem of Fubini to the context of Baire's category that is often very useful.

An interesting feature of Ulam's work followed from his great ability to collaborate with others. Almost all of his papers are co-authored with other mathematicians or physicists. He had many ideas, and he was very successful in stirring the imagination and enthusiasm of others. His most important collaborators were Jósef Schreier, John C. Oxtoby, and C. J. Everett. He invented a large number of original problems, some of which were solved by other mathematicians and even became famous theorems. One such conjecture was proved by K. Borsuk and is known today as the theorem on antipodes (the two points at the opposite ends of a diameter of a sphere are called antipodes of each other). It is sometimes called the ham-and-cheese sandwich theorem. It

[graphic][subsumed][subsumed][subsumed][subsumed]

The Existence and Significance

of Ergodic Transformations

Excerpts from the Introduction to Oxtoby and Ulam's Measure-Preserving Homeomorphisms

and Metrical Transitivity

[ocr errors]

in the study of dynamical systems one is led naturally to the consideration of

-measure-preserving transformations. A Hamiltonian system of 2n differential equations induces in the phase space of the system a measure-preserving flow, that is, a one-parameter group of transformations that leave invariant the 2ndimensional measure.

... If the differential equations are sufficiently regular the flow will have corresponding properties of continuity and differentiability. Thus the study of one-parameter continuous groups of measure-preserving automorphisms of finite dimensional spaces has an immediate bearing on dynamics and the theory of differential equations.

In statistical mechanics one is especially interested in time-averaging properties of a system. In the classical theory the assumption was made that the average time spent in any region of phase space is proportional to the volume of the region in terms of the invariant measure, more generally, that time-averages may be replaced by space-averages. To justify this interchange, a number of hypotheses were proposed, variously known as ergodic or quasi-ergodic hypotheses, but a rigorous discussion of the precise conditions under which the interchange is permissible was only made possible in 1931 by the ergodic theorem of Birkhoff. This established the existence of the time-averages in question, for almost all initial condi

torus, and in any pseudo-manifold of dimension at least three. Since the phase spaces of dynamical systems have the required kind of connectedness, it follows that the hypothesis of metrical transitivity in dynamics involves no topological contradiction. More precisely, in any phase space there can exist a continuous flow metrically transitive with respect to the invariant measure associated with the system.

It must be emphasized, however, that our investigation is on the topological

level. The flows we construct are contintions, and showed that if we neglect sets

uous groups of measure-preserving autoof measure zero, the interchange of time

morphisms, but not necessarily differenand space-averages is permissible if and tiable or derivable from differential equaonly if the flow in the phase space is met- tions. Thus they correspond to dynamical rically transitive. A transformation or a

systems only in a generalized sense. flow is said to be metrically transitive if

It may be recalled that the original erthere do not exist two disjoint invariant godic hypothesis of Boltzmann—that a sets both having positive measure. Thus single streamline passes through all points the effect of the ergodic theorem was to of phase space—had to be abandoned bereplace the ergodic hypothesis by the hy- cause it involved a topological impossipothesis of metrical transitivity.

bility. It was replaced by a quasi-ergodic Nevertheless, in spite of the simplifica- hypothesis—that some streamline passes tion introduced by the ergodic theorem, arbitrarily close to all points of phase the problem of deciding whether partic- space. But it is not obvious that even ular systems are metrically transitive or this weak hypothesis is topologically reanot has proved to be very difficult. sonable in general phase spaces, and in

... The known examples of metrically any case it is not sufficient to justify the transitive continuous flows are all in man- interchange of time- and space-averages. ifolds, indeed in manifolds of restricted It is therefore of some interest to know topological type, either toruses or mani- that the ergodic hypothesis in its modfolds of direction elements over surfaces ern form of metrical transitivity is at least of negative curvature. An outstanding free from any objection on topological problem in ergodic theory has been the grounds..... existence question—can a metrically transitive continuous flow exist in an arbitrary Editor's Despite the existence of ermanifold, or in any space that is not a godic transformations, the ergodicity of manifold? In the present paper we shall many familiar dynamical systems remains obtain a complete answer to this ques- an open and thought-provoking question. tion, at least on the topological level, for For details see Patrascioiu's article. "The polyhedra of dimension three or more. It Ergodic Hypothesis: A Complicated Probwill appear that the only condition that lem of Mathematics and Physics." needs to be imposed is a trivially necessary kind of connectedness. In partic

Footnotes have been omitted from these excerpts, ular, there exists a metrically transitive

which are reprinted with permission from Annals continuous flow in the cube, in the solid of Mathematics.

well-developed mathematics. Few mathematicians have the intelligence or the courage that Ulam had to think about important problems irrespective of whether their solutions are in sight. But this is the only course that can lead to outstanding achievements. I

Further Reading

W. A. Beyer, J. Mycielski, and G.-C. Rota, editors. 1974. Stanislaw Ulam: Sers, Numbers, and Universes. Cambridge, Massachusetts: The MIT Press.

A collection of declassified Los Alamos technical reports by Ulam and his collaborators is to be published soon by University of California Press.

proposed to study the “genealogical distance” d(a,b) between two individuals a and b, which is defined as follows. Count the number of ancestors of a that are not ancestors of b, and add to it the number of ancestors of b that are not ancestors of a. Assume that the size of the population is constant in time, that mating is random, and that a and b belong to the same generation. Ulam soon discovered by experimenting on a computer that under those conditions the expected value of d(a,b) is twice the size of the population. Later Joseph Kahane and Robert Marr proved this conjecture (Journal of Combinatorial Theory, Series A, volume 13 (1972)). The smallness of this expected distance suggests that all profitable mutations are soon present in all individuals of subsequent generations.

Ulam liked to invent problems that could-be studied by means of electronic computers. He was the first to realize that computers are ideal tools for watching the evolution of patterns governed by simple laws. He proposed many experiments of this type, the most famous of which is reported in the paper of Fermi, Pasta, and Ulam on dynamical evolution governed by nonlinear laws. Later he invented various simple rules to produce crystal-like growths in space. He also observed sim

ple cases of “wars” between growing populations of crystals or cells. Nowadays many such processes are being investigated; Conway's "game of life" is a popular example. It is hoped that this approach will help us to understand certain qualitative features of natural evolution. For example, one can replace the complicated rules of chemistry governing real life by simpler rules and, through numerical simulation, watch the ways in which the patterns (objects) yielded by these rules grow and compete in complicated and surprising ways. (In my own work I am trying to explain human thought and learning, which we so often discussed together, by applying local rules of interaction that may define interesting processes. It is already known that the computations going on in the cerebral cortex are local in some sense.)

I have tried to give you glimpses of certain works of Stan Ulam. Of course, in this short article I have discussed only those that seem to me the most important or with which I was the most familiar.

Every creative mathematician must allow his imagination to flow in a free way. I think that Ulam did this more than others. He was drawn to work upon problems that suggested essentially new ideas and avoided the attractive pull of

Frank R. Drake. 1974. Set Theory: An Introduction to Large Cardinals. Amsterdam: North-Holland Publishing Company.

Jan Mycielski. 1985. Can mathematics explain natural intelligence? Los Alamos National Laboratory report LA-10492-MS. Also in Physica D 22(1986): 366-375.

Jan Mycielski and S. Swierczkowski. A model of the neocortex. Los Alamos National Laboratory report. To be published.

[graphic]

Jan Mycielski was born in Poland in 1932. After receiving his Ph.D. from the University of Wroclaw, he worked at the Institute of Mathematics of the Polish Academy of Science. In 1969 he immigrated to the United States and obtained a professorship at the Universit of Colorado, a position he has retained to the present. He has held visiting positions at the Centre National de la Recherche Scientifique, Case Western Reserve University, and the University of California, Berkeley. His research has resulted in over one hundred papers pertaining to mathematical logic, set theory, game theory, geometry, algebra, and learning systems. He is a member of the American Mathematical Society, the Mathematical Association of America, the Association for Symbolic Logic, and the Polish Mathematical Society.

« PreviousContinue »