Set theory and physics

K. Svozil
Institut für Theoretische Physik
University of Technology Vienna
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
www:[    \tilde] svozil



In as much as physical theories are formalizable, set theory provides a framework for theoretical physics. Four speculations about the relevance of set theoretical modeling for physics are presented: the rôle of transcendental set theory (i) in chaos theory, (ii) for paradoxical decompositions of solid threedimensional objects, (iii) in the theory of effective computability (Church-Turing thesis) related to the possible ``solution of supertasks'', and (iv) for weak solutions. Several approaches to set theory and their advantages and disadvantages for physical applications are discussed: Cantorian ``naive'' (i.e., non-axiomatic) set theory, constructivism and operationalism. In the author's opinion, an attitude of ``suspended attention'' (a term borrowed from psychoanalysis) seems most promising for progress. Physical and set theoretical entities must be operationalized wherever possible. At the same time, physicists should be open to ``bizarre'' or ``mindboggling'' new formalisms, which need not be operationalizable or testable at the time of their creation, but which may successfully lead to novel fields of phenomenology and technology.

1  A short history of set theory, with emphasis on operationalism

Physicists usually do not pay much attention to the particulars of set theory. They tend to have a pragmatic attitude towards the foundations of the formal sciences, combined with the suspicion that, as has been stated by Einstein ([1], translated from German)1 ``insofar mathematical theorems refer to reality, they are not sure, and insofar they are sure, they do not refer to reality.''

Yet there are instances when foundational issues do play a rôle. It is due to a lack of expertise and experience, that the empiric researcher is then particularly vulnerable to misconceptions. Below we shall give examples where set theoretic specifications are essential to the argument. But we have to first briefly review set theory in general.

In Cantorian (i.e., non-axiomatic) set theory, the ``definition'' of the concept of a set reads ([2], translated from German [6]),2

``A set is a collection into a whole of definite distinct objects of our intuition or of our thought. The objects are called the elements (members) of the set.'' As general as it is conceived, Cantorian set theory would provide a powerful mathematical framework for theoretical physics. Per definition, hardly any conceivable object does not fall within its domain. Indeed, how gratifying and ambitious, but also how challenging this conception, one can imagine from Hilbert's emphatic declaration (cf. [3], p. 170, translated from German),3 ``From the paradise which Cantor created, no one shall be able to expel us.''

Alas, Cantorian set theory, at least its uncritical development, proved inconsistent. Both Cantor (cf. [6], p. 7 and [4], p. IV) and Hilbert were fully aware of the set theoretical antinomies such as Russell's paradox, ``The set of all sets that are not members of themselves.'' Cantor himself discovered one of the first antinomies around 1895, even before the Burali-Forti antinomy. In 1899, Cantor wrote in a letter to Dedekind ([4], p. 443, translated from German [5]),4 For a multiplicity can be so constituted that the assumption of a ``being together'' of all its elements leads to a contradiction, so that it is impossible to consider the multiplicity a a unit[y], thus ``a complete thing.'' I call such multiplicities absolutely infinite or inconsistent multiplicities. [paragraph] As one readily convinces oneself, the ``aggregate of everything thinkable'' is, for example, such a multiplicity; ''

In Hilbert's formalist view of the infinite, all proofs using non-terminating sequences of operations should be substituted by finite processes and proof methods (cf. [3], p. 162).5 For Hilbert, a typical example for this program was Weierstraß 's approach to analysis.

Others, among them Zermelo and Fraenkel [6], were less secure in the ``Cantorian heaven of set theory'' and attempted to block the paradoxes by axiomatically restricting the rules of set generation. The necessary price was a restriction of the mathematical Universe.

Rather unexpected for Hilbert, but obvious for Brouwer (cf. [7], p. 88), Gödel [8] showed that in any reasonably strong axiomatic theory (rich enough to allow for arithmetic), consistency cannot be proven. (One may quite justifiable ask whether a ``proof'' of consistency would really be of any value; after all, if a theory were inconsistent, then consistency could also be ``proved'' therein!)

Further restrictions to set generation were imposed by constructive mathematics, anticipated by the radical ``Verbotsdiktator'' Kronecker. The varieties of constructive mathematics [9] comprises the intuitionistic school around Brouwer and Heyting, the Russian school, and Bishop's constructive mathematics. For more recent developments, see Bridges [10,9]. Essentially, the existence of mathematical objects is accepted only if the objects can be constructed by an algorithm. An algorithm is a finite procedure. That is, its algorithmic information (minimal description length), as well as its execution time is finite. It can be perceived as the step-by-step execution of a deterministic computer program. Constructive mathematics is not particularly concerned with the actual size of algorithmic information and dynamic complexity (time and space), as long as they are finite (although it is acknowledged that such considerations are important for practical applications). In Russian constructive mathematics, the term ``algorithm'' is a synonym for a finite sequence of symbols in a fixed programming language.

Enter physics. Not long after Hilbert's bold statement concerning the Cantorian paradise (which was directed against the uncritical use of the ``actual infinity'' in mathematics and the natural sciences) appeared a critical essay on the methods of set theory by Bridgman [11]. (Landauer has referred to Bridgman's article at several occasions [12,13,14].) Bridgman's operationalism was directed against the uncritical use of theoretical concepts [15,16]. In particular, he demanded that the meaning of theoretical concepts should ultimately be based on concrete physical operations. That is, (cf. [17], p. V),

``the meaning of one's terms are to be found by an analysis of the operations which one performs in applying the term in concrete situations or in verifying the truth of statements or in finding the answers to questions.'' In his later writings, Bridgman clarified (and somewhat weakened) operationalism by differentiating between ``instrumental'' and ``paper-and-pencil'' operations (cf. [18], p. 8-10),

``It is often supposed that the operational criterion of meaning demands that the operations which give meaning to a physical concept must be instrumental operations. This is, I believe, palpably a mistaken point of view, for simple observation shows that physicists do profitably employ concepts the meaning of which is not to be found in the instrumental operations of the laboratory, and which cannot be reduced to such operations without residue. Nearly all the concepts of theoretical and mathematical physics are of this character, such for example as the stress inside an elastic body subject to surface forces, or the y function of wave mechanics. we may single out the sort of operations performed by the theoretical physicist in his mathematical manipulations and characterize these as `paper-and-pencil' operations. Among paper-and-pencil operations are to be included all manipulations with symbols, whether or not the symbols are the conventional symbols of mathematics. a great latitude is allowed to the verbal and the paper-and-pencil operation. I think, however, that physicists are agreed in imposing one restriction on the freedom of such operations, namely that such operations must be capable of eventually, although perhaps indirectly, making connection with instrumental operations.''

Bridgman pointed out that in Cantorian set theory there is one particularly vicious method of specifying operations. In his own words (cf. [11], p. 106), ``It is possible to set up rules which determine a non-terminating sequence of operations, as for instance, the rules by which the sequence of the natural number is engendered. But it is obviously not legitimate to specify in this way a non-terminating operation, and then to treat this non-terminating complex as itself a simpler operation which may be used as an intuitive ultimate in the specification of another operation. Such a non-terminating complex can be treated in this way only when it can be proved equivalent to some other procedure specifiable in finite terms, and which can, therefore, be actually executed. Otherwise, the non-terminating complex must be treated as the end, and no other operations be demanded after it; our ordinary experience of the order of operations as performed in time evidently requires this.'' In present-day, recursion theoretic, terminology, a ``complex operation'' would be called a ``sub-program'' or ``(sub-)algorithm,'' and the term ``non-terminating'' would be translated as ``diverging'' in the sense of ``non-recursively bound.'' In terms of recursion theory, Bridgman's claim can be re-interpreted such that no diverging algorithm should be allowed as legal input of any other (terminating) algorithm.

One may go even further than Bridgman and assume that, since infinite entities are not operational, infinities have to be abandoned altogether. The elimination of even potential infinities leaves us with merely finite objects. Finitistic arguments and physical limits have been put forward by Gandi [19,20], Mundici [21], Landauer [22] and Casti [23].

2  The ``Go-Go'' principle

The Cantorian ``permissive'' approach to the foundations of mathematics stimulated the invention, creation and investigation of the weirdest ``monsters'' of thought. Per definition, no construction or speculation could be crazy enough to be excluded from the formal sciences. While inconsistent, this attitude brought forth an undeniable advancement in the formal sciences insofar as objects were discovered which had novel, sometimes bizarre and even ``mindboggling'' features.

Take, for instance, Cantor's map of the unit line onto the unit square which is one-to-one, or Peano's continuous map from a line onto the unit square. Another example is the Cantor set (nowadays called a ``fractal'') C = { n = 1 cn3-n\mid cn {0,2} foreach n}, which has vanishing measure m(C) = limn 0(2/3)n = 0 but which can be brought into a one-to-one correspondence to the unit interval of the binary reals. Another ``mindboggling'' result concerning measure-theoretic non-preservation is the Banach-Tarski paradox discussed below.

The spirit behind all these findings seems to be that ``everything goes.'' Stated pointedly:

Every method and object should be permitted as long as it is not excluded by the rules. Or: Anything that is not forbidden is allowed.

In the following, this attitude will be called the ``Go-Go'' principle. It may be applied both to the formal and to the natural sciences.6

A few remarks are in order. As has been pointed out before, consistency cannot be proven from within the rules, at least not if the rules are strong enough to allow for arithmetic or universal computation.

The ``Go-Go'' principle collides with the axiomatic method using recursive rules of inference. It can be expressed as follows:

Every method or object is excluded which is not derivable by the rules. Or: Anything that is not allowed is forbidden.

One might jokingly call this the ``No-Go'' principle.7 Despite its rather restrictive attitude, the axiomatic method seems good enough to include analysis [10] (and, at least good enough to re-derive many important results first discovered by ``Go-Go.'') Formalist like Hilbert have even claimed that it should turn out to be all the same, finally.

One should also be aware that the ``Go-Go'' principle allows a pragmatic point of view, which most researchers practice anyway: since it is difficult to develop progressive and innovative ideas, the real problem in the sciences might not be to eliminate ill-conceived concepts and methods but to introduce novel features at all. Otherwise, one might argue, mathematicians would have just to evoke an automated proof machine, a ``perfect publicator,'' which makes its creators superfluous.

Therefore, judged from a pragmatic point of view, the ``Go-Go'' principle might prove progressive but unreliable. To put it pointedly: the ``Go-Go'' principle might be essential for producing novel results, for the discovery of undiscovered land (Hilbert's paradise), even if it is known that it yields antinomies.

Despite all positive aspects which have been mentioned so far, as liberal as it is conceived, the ``Go-Go'' principle is unable to cope with its own limitations, in particular with respect to applications to physics. Therefore, physicists are occasionally confronted with ``effects'' or ``predictions'' of physical theory which have their origin in non-constructive, non-operational features of the set theory underlying that physical theory. But even if such ``effects'' from theoretical artifacts might prove elusive most of the time, seldom enough (cf. non-Euclidean geometry) they might lead us to totally unexpected classes of phenomena.

In what follows, some speculative examples inspired by ``Go-Go'' are discussed. They correspond to paper-and-pencil operations. If they will eventually be capable of making connection, perhaps indirectly, with instrumental operations, remains to be seen.

2.1  ``Chaos'' theory

The emergence of ``chaos theory'' has highlighted the use of classical continua [31].8 There, the scenario is that the equation of motion seems to ``reveal'' the algorithmic information [32,33,34] of the initial value [35,36,37].9

Consider, for example, the logistic equation of motion f:xn xn+1 = f(xn) = axn(1-xn) for variable xn at discrete times n N0. It can, for a = 4 and after the variable transformation xn = sin2(pXn), be rewritten as f:Xn Xn+1 = 2Xn (mod1), where (mod 1) means that one has to drop the integer part of 2Xn. By assuming a starting value X0, the formal solution after n iterations is f(n)(X0) = Xn = 2nX0 (mod 1). Note that, if X0 is in binary representation, f(n) is just n times a left shift of the digits of X0, followed by a left truncation before the decimal point.

Assume now that the measurement precision is the first m bits of Xn, in the binary expansion of Xn. In a single time step, the evolution function f effectively reveals the next digit of X0, which was unobservable before. That is, in order to be able to measure the initial value for an arbitrary but finite precision m, one has to wait and measure X0 until time max(m-m,0).

The only possible ``chaotic'' feature in this scenario resides in the initial value: the theoretician has to assume that X0 (0,1) is uncomputable or even Martin-Löf/Solovay/Chaitin random. Then the computable function f(n)(X0) yields a measurable bit stream which reconstructs the binary expansion of X0, which is uncomputable or even Martin-Löf/Solovay/Chaitin random. To put it pointedly: if the input is a random real, then the output approximates a random real; in more physical terms: if unpredictability is assumed, then chaotic motion follows. (More ironically: garbage in, garbage out.) That is all there is.

It is amazing how susceptible the general public as well as many physicists are to contemplate this form of ``chaotic'' motion as a fundamental fact about the nature of (physical) reality rather than as a theoretical assumption. In the author's opinion, one of the reasons10 for this willingness of physicists to accept Martin-Löf/Solovay/Chaitin randomness as a matter of natural fact is that physicists have been trained in the domain of classical continuum mechanics [39]. The term ``classical'' here refers to both non-quantum mechanics, as well as to Cantorian set theory.

To be more precise, recall that Cantor's famous diagonalization argument [2] asserts that the set of reals in the interval [0,1] are nondenumerable: Assume that there exists an effectively computable enumeration of the decimal reals in the interval [0,1] of the form

r1 = 0.r11r12r13r14
r2 = 0.r21r22r23r24
r3 = 0.r31r32r33r34
r4 = 0.r41r42r43r44
Consider the real number formed by the diagonal elements 0.r11r22r33. Now change each of these digits, avoiding zero and nine. (This is necessary because reals with different digit sequences are identified if one of them ends with an infinite sequence of nines and the other with zeros, for example

0.0999 = 0.1000.) The result is a real r = 0.r1r2r3 with rn rnn which thus differs from each of the original numbers in at least one (i.e., the ``diagonal'') position. Therefore there exists at least one real which is not contained in the original enumeration.

Indeed, any denumerable set of numbers is of Lebesgue measure zero. Let M = { ri} be an infinite point set (i.e., M is a set of points ri) which is denumerable and which is the subset of a dense set. Then, for instance, every ri M can be enclosed in the interval

I(i,d) = [ri-2-i-1d , ri+2-i-1d]    ,
where d may be arbitrary small (we choose d to be small enough that all intervals are disjoint). Since M is denumerable, the measure m of these intervals can be summed up, yielding

m( I(i,d)) = d

i = 1 
2-i = d    .
From d 0 follows m(M) = 0. Example for denumerable point sets of reals are the rationals Q and the algebraic reals. (Algebraic reals x satisfy some equation a0xn +a1xn-1+ +an = 0, where ai N and not all ai's vanish.) Consequently, their measures vanish. The complement sets of irrationals R - Q and transcendentals (non-algebraic reals) are thus of measure one [40].

It is easy to algorithmically prove that the computable reals are denumerable.11 The range of the partial recursive function jC corresponding to an arbitrary computer C can be explicitly enumerated as follows. Begin at step zero with an empty enumeration. In the n'th step, take all legal programs (i.e., programs which are in the domain of C) of code length n and run C up to time n; add in quasi-lexicographical order all output numbers which have not yet occurred (up to time n-1) in the enumeration.12

That means that if the continuum is treated as an ``urn,'' from which the initial values are drawn, then ``almost all,'' i.e., with probability one, such initial values are not effectively computable. One can even prove that the stronger statement ``almost all'' elements of the continuum have incompressible algorithmic information; i.e., they are Martin-Löf/Solovay/Chaitin random [32,33,34].

But what does it mean to ``prove'' that ``almost all'' of them are non-recursive; stronger: random reals? It is obviously impossible to give just a single constructive example of such a non-recursive real.

What does it mean ``to pull a real number - the initial value in spe - out of the continuum urn?'' How could we conceive the process of selecting one real symbolizing the initial value over the other? We need the Axiom of Choice for that. The Axiom of Choice asserts that for any set x, there is a choice function c of x, such that c(y) y for all y dom(c) = x- in the domain of c. The Axiom of Choice is non-constructive, at least for arbitrary non-constructive subsets of R. That is, there does not exist any effectively computable, i.e., recursive, choice function which would ``sort out'' the initial value X0. Therefore, chaos theory presupposes not only Martin-Löf/Solovay/Chaitin random reals, but nonconstructive choice functions.

Moreover, what type of computation is necessary to implement the innocent-looking evolution function f of the logistic equation above? Recall that, since the initial value X0 is Martin-Löf/Solovay/Chaitin random with probability one, its description is algorithmically incompressible and infinite. Therefore, any ``computation'' rigorously implementing f should be capable of handling infinite input. In Bridgman's terms, this requirement is non-operational. (Cf. Landauer [22] and the author [57]).

The above mentioned problems of handling Martin-Löf/Solovay/Chaitin random objects become even more pressing if one realizes that, from the point of view of coding theory, an algorithm and its input are interchangeable, the difference between them being a matter of convention: consider a particular algorithm p implemented on a computer C(p,s) with a particular input s; and a second algorithm p with the empty input . Assume that the only difference between p and p is that the latter algorithm encodes the input s as a constant, whereas the former reads in (the code of) the object s. Hence, C(p,s) = C(p,). Notice that, for Martin-Löf/Solovay/Chaitin random objects s, the algorithmic information content H(p) remains finite, whereas H(p) = . In this sense, recursive functions of non-recursively enumerable variables are equivalent to non-recursive functions.

2.2  Isometric miracles

In what follows I shall shortly review non-measure preserving isometric functions; often referred to as the ``Banach-Tarski paradox.'' The ``mindboggling'' feature here is that an arbitrary solid object of Rn 3 can be partitioned into a finite number of pieces, which are then rearranged by isometries, i.e., distance preserving maps such as rotations and translations, to yield other arbitrary solid objects. This procedure could be the ideal basis of a perfect production belt: produce a single prototype and ``Banach-Tarski-clone'' an arbitrary number thereof. Or, produce an elephant from a mosquito!13

Let us briefly review another application in chaos theory. Consider all bijections of a set A. The most systematic way of doing this is to work in the context of group actions. Recall that a group G is said to act on A if to each g G there corresponds a bijective function from A to A, also denoted by g, such that for any g,h G and x A, g(h(x)) = (gh)(x) and 1(x) = x.

An isometry of a metric space is a distance-preserving bijection of the metric space onto itself. A bijection a:Rn Rn is called affine if for all x,y Rn and reals a,b with a+b = 1, a(ax+by) = aa(x)+ba(y). (Note that every isometry is affine, with a = 1.)

Let G be a group acting on A X. A is G-paradoxical (or, paradoxical with respect to G) if there are (n+m) pairwise disjoint subsets E1,,En , F1,,Fm of A, and (n+m) group actions g1,,gn,h1,,hm G such that A = i = 1ngi(Ei) = j = 1mhj(Fj). In other words, A is G-paradoxical if it has two disjoint subsets iEi and jFj, each of which can be taken apart and rearranged via G to cover all of A.

Suppose G acts on X and E,F X. Then E and F are G-equidecomposible if E and F can each be partitioned into the same number of G-congruent pieces. Formally, E = i = 1nEi and F = i = 1nFi, with EiEj = FiFj = if i < j and there are g1,,gn G such that for each i, gi(Ei) = Fi. There is a remarkable result, usually called Banach-Tarski paradox:14 If A and B are two bounded subsets of Rn,  n 3, each having nonempty interior, then A and B are equidecomposible with respect to the group of isometries.

It can be proven that only five pieces are needed to perform ball doubling in R3. One is confronted with the ``mindboggling'' result that an arbitrary solid body of Rn,  n 3 can be ``cut'' into finitely many parts, which then may be reassembled via distance-preserving procedures to give an arbitrarily shaped other solid body. Pointedly stated, one could ``produce'' the sun out of a marble; or a an arbitrary number of perfect copies from a single original (the perfect production belt!).

Obviously, the pieces needed for such types of paradoxical constructions are not measurable. They are also not recursively enumerable and non-constructive and thus non-operational in Bridgman's terminology. But does this imply that ``paradoxical'' equidecompositions are physically forbidden?

Augenstein [43] and Pitowsky [44] have given two possible applications of ``paradoxical'' equidecomposibility in physics. In what follows, another, speculative, application is proposed. It is assumed that the reader has a heuristic comprehension of the concept of ``attractors'' (see also ref. [35,45]). An attempt towards a formal definition of an attractor can be found in [46]. For the time being, it suffices to keep in mind that an attractor A is a point set embedded in a manifold X (e.g. Rn), with the following essentials.

R1) all points x A are cumulation points of f;

R2) topological undecomposibility: for arbitrary x,y A and arbitrary   diam(A) e > 0 there must be chains x = x0,x1,,xn = y and y = y0,y1,,ym = x such that   dist(xi,f(g(i))(xi-1)) < e   and   dist(yi,f(g(i))(yi-1)) < e   with   g(i),g(i) 1   for all i = 1,2,,n. This formal condition boils down to the requirement that with respect to the function f, A cannot be decomposed into more ``elementary'' attractors which are subsets of A.

The following condition of strangeness shall be imposed upon attractors.

S) AS is strange if to every d diam (AS) and e < d there exists a N(e,d) such that for arbitrary two points x,y AS, dist(x,y) < e, dist (f(N)(x),f(N)(y)) d.

The above condition guarantees that, heuristically speaking, arbitrarily close points become arbitrarily separated in time. I shall restrict further considerations to dynamical systems (f,X) for which the basin of attraction (i.e., the set of initial points from which the flow is attracted) is the entire embedding space X.

There are strong relationships between the property of strangeness and Tarski's theorem, which shall be presented next. Consider the group of automorphisms S of A(X,f); i.e., the bijections under which A(X,f) is invariant. Automorphisms can be interpreted as symmetries of (X,f). For attractors, the flow is a symmetry, i.e., f(i) S. Any subset A1 of a strange attractor AS with nonzero diameter diam(A1) > 0 can be completed to AS by application of some f(i) S such that f(i)(A1) = AS. In this sense, A1 is physically equivalent to AS. Conversely, if A is not strange, this property does not hold. In terms of paradoxical decompositions, the property of strangeness can then be alternatively defined via paradoxical equidecompositions.

S') AS is strange if it is paradoxical with respect to the time flow f.

It then follows from Tarski's theorem [47] that there is no finitely additive measure on strange attractors which is invariant with respect to the symmetries (invariants) of motion. For regular attractors such a measure exists.

The apparent question is which type of attractors are equidecomposible with respect to which kind of group actions? To put it in more physical terms: Suppose there exist two dynamical systems, represented by (X,f1) and (X,f2), with associated attractors A(f1) and A(f2), respectively (the embedding space X is unchanged, therefore we drop it as argument). Do there exist physical (parameter or other) changes corresponding to group actions G:A(f1) A(f2) ? Indeed, this is the case for period doubling solutions. There, f1 and f2 are nonlinear functions, which are in general not distance preserving. Along these lines, the notion of equidecomposibility of attractors could become a powerful tool for a systematic investigation of parameter and symmetry changes.

According to the Banach-Tarski paradox, this would allow the occurrence of strange attractors (``chaotic motion'') even for distance preserving, linear time flows. This kind of paradoxical decomposition requires the application of the Axiom of Choice (cf. the brief discussion above).

Thus it is not completely speculative to suggest testing the Axiom of Choice via the reconstruction of strange (chaotic) attractors by physical timeseries from distance preserving flows in Rn, n 3.

2.3  Oracle computing

Zeno's paradoxes [48], formulated around fifth century B.C., will probably remain with us forever; very much like an eternal Zen koan presented to us by this great greek mathematical master(s) at the beginning of scientific thought. It is the author's believe that neither Weierstraß 's ``Epsilontik'' nor modern approaches such as nonstandard analysis [49] have contributed substantially to the ``mindboggling'' feature that (in Simplicius' interpretation of Zenos's paradox of Achilles and the Tortoise, quoted from [48], p. 45) if space is infinitely divisible, and if

`` there is motion, it is possible in a finite time to traverse an infinite number of positions, making an infinite number of contacts one by one.''

I shall review here a recursion theoretic version of Zeno's paradox, which has been discussed by Weyl [50], Grünbaum ([51], p. 630), Thomson [52], Benacerraf [53], and more recently by Pitowsky [54], Hogarth [55], Earman & Norton [56] and the author [57,58].

Continuum theory, in fact any dense set, in principle allows the construction of ``infinity machines,'' which could serve as oracles for the halting problem. Their construction closely follows Zeno's paradox of Achilles and the Tortoise by squeezing the time it takes for successive steps of computation t with geometric progression:

Picture Omitted
    That is, the time necessary for the n'th step becomes t(n) = kn, 0 < k < 1. The limit of infinite computation is then reached in finite physical time

limN n = 1N t(n) = limN n = 1N kn = 1/(1-k).

It can be shown by a diagonalization argument that the application of such oracle subroutines would result in a paradox in classical physics (cf. [57], p. 24, 114). The paradox is constructed in the context of the halting problem. It is formed in a similar manner as Cantor's diagonalization argument. Consider an arbitrary algorithm B(x) whose input is a string of symbols x. Assume that there exists (wrong) a ``halting algorithm'' HALT which is able to decide whether B terminates on x or not.

Using HALT(B(x)) we shall construct another deterministic computing agent A, which has as input any effective program B and which proceeds as follows: Upon reading the program B as input, A makes a copy of it. This can be readily achieved, since the program B is presented to A in some encoded form # (B), i.e., as a string of symbols. In the next step, the agent uses the code # (B) as input string for B itself; i.e., A forms B(#(B)), henceforth denoted by B(B). The agent now hands B(B) over to its subroutine HALT. Then, A proceeds as follows: if HALT(B(B)) decides that B(B) halts, then the agent A does not halt; this can for instance be realized by an infinite DO-loop; if HALT(B(B)) decides that B(B) does not halt, then A halts.

We shall now confront the agent A with a paradoxical task by choosing A's own code as input for itself. - Notice that B is arbitrary and has not yet been specified and we are totally justified to do that: The deterministic agent A is representable by an algorithm with code # (A). Therefore, we are free to substitute A for B.

Assume that classically A is restricted to classical bits of information. Then, whenever A(A) halts, HALT(A(A)) forces A(A) not to halt. Conversely, whenever A(A) does not halt, then HALT(A(A)) steers A(A) into the halting mode. In both cases one arrives at a complete contradiction.

Therefore, at least in this example, too powerful physical models (of computation) are inconsistent. It almost goes without saying that the concept of infinity machines is neither constructive nor operational in the current physical framework.

2.4  Weak solutions

Consider an ordinary differential equation (of one variable t) of the form

Lx = n = 0 cn(t) dn x/dtn = t(t) , where t(t) is an arbitrary known distribution [e.g., t(t) = d(t)]. x is a weak solution if Lx = t(t) is satisfied as a distribution, yet x is not sufficiently smooth so that the operations in L (i.e., differentiations) cannot be performed. How relevant are weak solutions for physical applications?

In electrodynamics, for instance, point charges are modeled by Dirac delta functions d. The wave equation can therefore give rise to weak, discontinuous solutions. Are discontinuities mere theoretical abstractions, which indicate ``sharp'' changes of the physical parameter, or should they be taken more seriously? These questions connect to the quantum field theoretic program of renormalization and regularization.

3  The alternatives

The above speculations suggest that the theoretical physicist is occasionally confronted with set theoretical consequences which cannot be straightforwardly abandoned as ``artificial'' or ``irrelevant.'' They bear important, even technological, consequences. In what follows, two extreme alternatives will be discussed to cope with them. (No claim of completeness is made.)

3.1  Abandon non-operational entities altogether

In view of the problems of Cantorian, transfinite set theory, one may take the radical step and abolish non-constructive and non-operational objects altogether. This was Bridgman's goal. Related epistemological approaches had been anticipated by Boskovich, and have more recently been put forward by Zeilinger and Svozil [59,62], among others. Rössler's [60] endo-/exophysics approach and the author's [61] intrinsic-extrinsic distinction differ only insofar, as the operational mode of perception is contrasted with a hierarchical mode of perception of an observer outside of the system.

It should be noted that operationalism is not directed primarily towards the elimination of antinomies. The elimination of metaphysical concepts, such as absolute space and time, and their substitution by physically operationalizable concepts, is at the core of operationalism, and more specifically, of Einstein's theory of relativity (cf. [11], p. 103), `` the meaning of length is to be sought in those operations by which the length of physical objects is determined, and the meaning of simultaneity is sought in those physical operations by which it is determined whether two physical events are simultaneous or not.'' More recently, it has been applied for a definition of the dimension of space-time [62,63], for complementarity [57,64] and undecidability [57].

The elimination of set theoretical antinomies, as discussed by Bridgman, is a bonus of, and a clear argument for the approach. Indeed, it is quite justifiable to consider operationalism as the consequential persuasion of Descartes' [65] sketch of the scientific method. Its goal is the substitution of metaphysical concepts by purely physical correspondents.

The drawback of operationalism might lie in its too rigid, dogmatic interpretation. Whatever is operational depends on the particular period of scientific investigation. Therefore, the entities allowed by operationalism constantly change with time and are no fixed kanon. To kanonize them means to cripple scientific progress.

To give an example: in ancient Greece, supersonic air travel or radio-wave transmission were not feasible; therefore, any methods employing these operations to test whether the earth is ball-shaped were not allowed. But that, of course, does not imply that supersonic air travel or radio-wave transmission is impossible in principle!15

Nevertheless, one may quite justifiable argue that, if executed carefully, the necessity to operationalize physics will push science forward.

3.2  ``Go-Go'' science

Another possibility would be not to care about set theory at all and pursue a ``Go-Go'' strategy. The advantage of such a method of progression would be its open-mindedness. A disadvantage would be the vulnerability to unreliable conclusions and claims, which are either incorrect or have no counterpart in physics. 16

3.3  Synthesis

In view of the advantages and drawbacks of the two extreme positions outlined above, an attitude of ``suspended attention'' (a term borrowed from psychoanalysis) seems most promising.

This means that the theorist should be ``on the lookout'' for innovative, new formal objects, while not loosing sight of operational tests and practical implementations of such findings.

4  Epilogue: mathematical versus physical universe

From the time of ancient civilizations until today, the development of mathematics seems to be strongly connected to the advancements in the physical sciences. Mathematical concepts were introduced on the demand to explain natural phenomena. Conversely, physical theories were created with whatever mathematical formalism was available. This observation might suggest a rather obvious explanation for ``the unreasonable effectiveness of mathematics in the natural sciences'' (cf. Wigner [67] and Einstein [1], among others). Yet, there remains an amazement that the mathematical belief system can be implemented at all! There seems no a priori reason for this remarkable coincidence.

One of the most radical metaphysical speculations concerning the interrelation between mathematics and physics is that they are the same, that they are equivalent. In other words: the only ``reasonable'' mathematical universe is the physical universe we are living in! As a consequence, every mathematical statement would translate into physics and vice versa.

As is suggested by their allegedly esoteric, almost ``occult,'' practice of mathematical knowledge, the Pythagoreans might have been the first to believe in this equivalence (cf. Aristotle's Metaphysics, Book I, 5; Book XIII, 6; translated into English [68]): `` -since, then, all other things seemed in their whole nature to be modeled on numbers, and numbers seemed to be the first things in the whole of nature, they [[the Pythagoreans]] supposed the elements of numbers to be the elements of all things, and the whole heaven to be a musical scale and a number.'' ``And the Pythagoreans, also, believe in one kind of number-the mathematical; only they say it is not separate but sensible substances are formed out of it. For they construct the whole universe out of numbers ''17

It has to be admitted that, from a contemporary point of view, such an equivalence between mathematics and physics appears implausible and excessively speculative. Even in the framework of axiomatic set theory, there seem to be many (possibly an infinite number of) conceivable mathematical universes but only one physical universe.18 For example, Zermelo-Fraenkel set theory can be developed with or without the axiom of choice, with or without the continuum hypothesis. Axioms for Euclidean as well as for non-Euclidean geometries have been given.

Are there criteria such as ``reasonableness'' which may single out one mathematical universe from the others? That turns out to be difficult. Let us for instance agree that the least requirement one should impose upon a ``reasonable'' mathematical formalism is its consistency. As appealing as this identification sounds, it is of no practical help. As has been pointed out by Gödel [8], for strong enough mathematical formalisms19 consistency is no constructive notion. For this reason, mathematicians do not know whether axiomatic Zermelo-Fraenkel set theory is consistent.20

Let us finally take the opposite standpoint and reject the assumption of an equivalence between mathematical and physical entities. Even then, there appears to be a straightforward coincidence between mathematics and ``virtual'' physics [69]: Any axiomatizable mathematical formalism is constructive per definition, since any derivation within a formal system is equivalent to an effective computation. Therefore, any such mathematical model can be implemented on a universal computer. The resulting universe can then be investigated by means and methods which are operational from within that universe. - A metaphysical speculation which brings us back to Bridgman's perception of Cantorian set theory, the greatest attempt so far to reach out and encompass all of (meta-)physics into the domain of the formal sciences.


A. Einstein, Sitzungsberichte der Preuß ischen Akademie der Wissenschaften 1, 123 (1921); reprinted in A. Einstein, Mein Weltbild (Ullstein, 1988); p. 119-120.

G. Cantor, Beiträge zur Begründung der transfiniten Mengenlehre, Math. Annalen 46, 481-512 (1895); ibid. 49, 207-246 (1897); reprinted in [4].

D. Hilbert, Über das Unendliche, Math. Annalen 95, 161-190 (1926).

G. Cantor, Gesammelte Abhandlungen , eds. A. Fraenkel and E. Zermelo (Springer, Berlin, 1932).

W. Boos, Consistency and Konsistenz, Erkenntnis 26, 1-43 (1987).

A. A. Fraenkel, Y. Bar-Hillel and A. Levy, Foundations of Set Theory, Second Revised Edition (North Holland, Amsterdam, 1984).

H. Wang, Reflections on Kurt Gödel (MIT Press, Cambridge, MA, 1991).

K. Gödel, Monatshefte für Mathematik und Physik 38, 173 (1931).

D. Bridges and F. Richman, Varieties of Constructive Mathematics (Cambridge University Press, Cambridge, 1987).

E. Bishop and D. S. Bridges, Constructive Analysis (Springer, Berlin, 1985).

P. W. Bridgman, A Physicists Second Reaction to Mengenlehre, Scripta Mathematica 2, 101-117; 224-234 (1934).

R. Landauer, Wanted: a physically possible theory of physics, in IEEE Spectrum 4, 105-109 (1967).

R. Landauer, Fundamental Physical Limitations of the Computational Process; an Informal Commentary, in Cybernetics Machine Group Newssheet 1/1/87.

R. Landauer, Advertisement For a Paper I Like, in On Limits, ed. by J. L. Casti and J. F. Traub (Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994), p.39.

P. W. Bridgman, The Logic of Modern Physics (New York, 1927).

P. W. Bridgman, The Nature of Physical Theory (Princeton, 1936).

P. W. Bridgman, Reflections of a Physicist (Philosophical Library, New York, 1950).

P. W. Bridgman, The Nature of Some of Our Physical Concepts (Philosophical Library, New York, 1952).

R. O. Gandy. Limitations to mathematical knowledge, in D. van Dalen, D. Lascar, and J. Smiley (eds.). Logic Colloquium '82, North Holland, Amsterdam, 1982, 129-146.

R. O. Gandy. Church's Thesis and principles for mechanics, in J. Barwise, H. J. Kreisler and K. Kunen (eds.). The Kleene Symposium, North Holland, Amsterdam, 1980, 123-148.

D. Mundici, Irreversibility, uncertainty, relativity and computer limitations, Il Nuovo Cimento 61, 297-305 (1981).

R. Landauer, John Casti's page on ``Finiteness and Real-World Limits'', in On Limits, ed. by J. L. Casti and J. F. Traub (Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994), p.34.

J. L. Casti, Finiteness and Real-World Limits, in On Limits, ed. by J. L. Casti and J. F. Traub (Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994), p.34.

E. Specker, Selecta (Birkhäuser Verlag, Basel, 1990).

P. S. Wang, The undecidability of the existence of zeros of real elementary functions, J. Assoc. Comput. Mach. 21 (1974), 586-589.

G. Kreisel, A notion of mechanistic theory, Synthese 29(1974), 11-26.

D. Stef anescu, Mathematical Models in Physics, University of Bucharest Press, 1984. (in Romanian)

M. Pour-El, I. Richards, Computability in Analysis and Physics, Springer-Verlag, Berlin, 1989.

R. Penrose. The Emperor's New Mind. Concerning Computers, Minds, and the Laws of Physics, Vintage, London, 1990. (First published by Oxford University Press, Oxford, 1989.)

D. S. Bridges, Constructive mathematics and unbounded operators-a reply to Hellman, J. Phil. Logic. (in press)

C. Calude, D. I. Campbell, K. Svozil and D. tef anescu, Strong Determinism vs. Computability, e-print quant-ph/9412004.

G. J. Chaitin, Information, Randomness and Incompleteness, Second edition (World Scientific, Singapore, 1987, 1990); Algorithmic Information Theory (Cambridge University Press, Cambridge, 1987); Information-Theoretic Incompleteness (World Scientific, Singapore, 1992).

C. Calude, Information and Randomness - An Algorithmic Perspective (Springer, Berlin, 1994).

M. Li and P. M. B. Vitányi, Kolmogorov Complexity and its Applications, in Handbook of Theoretical Computer Sciences, Algorithms and Complexity, Volume A (Elsevier, Amsterdam and MIT Press, Cambridge, MA., 1990).

R. Shaw, Z. Naturforsch. 36a, 80 (1981).

St. Smale, The Mathematics of Time (Springer, New York, 1980).

J. Ford, Physics Today 40 (4), 1 (April 1983).

F. Chaitin-Chatelin and V. Fraysseé, Lectures on Finite Precision Computations (SIAM, 1955).

H. Goldstein, Classical Mechanics, Second Edition (Addison-Wesley Publishing Company, Reading, MA, 1980).

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (3rd edition) (Cambridge University Press, London, 1954).

E. M. Gold, Information and Control 10, 447 (1967).

St. Wagon, The Banach-Tarski paradox (2nd printing) (Cambridge University Press, Cambridge 1986)

B. W. Augenstein, International Journal of Theoretical Physics 23, 1197 (1984); Conceiving Nature-Discovering Reality, Journal of Scientific Exploration 8, 279-282 (1994).

I. Pitowsky, Phys. Rev. Lett. 48, 1299 (1982); Phys. Rev. D27, 2316 (1983); N. D. Mermin, Phys. Rev. Lett. 49, 1214 (1982); A. L. Macdonald, Ibid., 1215 (1982); I. Pitowsky, Ibid., 1216 (1982); Quantum Probability - Quantum Logic (Springer, Berlin, 1989).

H. G. Schuster, Deterministic Chaos (Physik Verlag, Weinheim 1984).

J.-P. Eckmann and D. Ruelle, Rev. Mod. Phys. 57, 617 (1985)

Tarski's theorem can be stated as follows [42]: Suppose a group G acts on A X. Then there exists a finitely-additive, G-invariant measure m:P(x) [0,) with m(A) = 1 if and only if A is not G-paradoxical.

H. D. P. Lee, Zeno of Elea (Cambridge University Press, Cambridge, 1936; reprinted by Adolf M. Hakkert, Amsterdam, 1967).

W. McLaughlin and S. L. Miller, An epistemological use of nonstandard analysis to answer Zeno's objections against motion, Synthese 92, 371-384 (1992).

H. Weyl, Philosophy of Mathematics and Natural Science (Princeton University Press, Princeton, 1949).

A. Grünbaum, Modern Science and Zeno's paradoxes, Second edition (Allen and Unwin, London, 1968); Philosophical Problems of Space of Time, Second, enlarged edition (D. Reidel, Dordrecht, 1973).

J. F. Thomson, Tasks and super-tasks, Analysis 15, 1-13 (1954).

P. Benacerraf, Tasks, super-tasks, and the modern eleatics, The Journal of Philosophy 59, 765-784 (1962).

I. Pitowsky, The physical Church-Turing thesis and physical complexity theory, Iyyun, A Jerusalem Philosophical Quarterly 39, 81-99 (1990).

M. Hogarth, Non-Turing computers and non-turing computability, PSA 1994, 1, 126-138 (1994).

J. Earman and J. D. Norton, Forever is a day: supertasks in Pitowsky and Malament-Hogarth spacetimes, Philosophy of Science 60, 22-42 (1993).

K. Svozil, Randomness and Undecidability in Physics (World Scientific, Singapore, 1993).

K. Svozil, On the computational power of physical systems, undecidability, the consistency of phenomena and the practical uses of paradoxes, in Fundamental Problems in Quantum Theory: A Conference Held in Honor of Professor John A. Wheeler, ed. by D. M. Greenberger and A. Zeilinger, Annals of the New York Academy of Sciences 755, 834-842 (1995).

A. Zeilinger, private communication.

O. E. Rössler, Endophysics, in Real Brains, Artificial Minds, ed. by J. L. Casti and A. Karlquist (North-Holland, New York, 1987), p. 25; Endophysics, Die Welt des inneren Beobachters, ed. by P. Weibel (Merwe Verlag, Berlin, 1992).

K. Svozil, On the setting of scales for space and time in arbitrary quantized media (Lawrence Berkeley Laboratory preprint LBL-16097, May 1983); Europhysics Letters 2, 83 (1986); Il Nuovo Cimento 96B, 127 (1986); see also [57].

A. Zeilinger and K. Svozil, Phys. Rev. Lett. 54, 2553 (1985); K. Svozil and A. Zeilinger, International Journal of Modern Physics A1, 971 (1986); K. Svozil and A. Zeilinger, Physica Scripta T21, 122 (1988).

K. Svozil, J. Phys. A19, L1125 (1986); K. Svozil, J. Phys. A20, 3861 (1987).

M. Schaller and K. Svozil, Il Nuovo Cimento 109 B, 167 (1994); International Journal of Theoretical Physics, in press.

R. Descartes, Discours de la mèthode pour bien conduire sa raison et chercher la vérité dans les sciences [English translation: Discourse on the method of rightly conducting the reason, and seeking truth in the sciences] (1637).

A. Jaffe and F. Quinn, ``Theoretical mathematics'': toward a cultural synthesis of mathematics and theoretical physics, Bulletin (New Series) of the American Mathematical Society 29, 1-13 (1993).

E. P. Wigner, ``The unreasonable effectiveness of mathematics in the natural sciences'', Richard Courant Lecture delivered at New York University, May 11, 1959 and published in Communications on Pure and Applied Mathematics 13, 1 (1960).

Aristotle, Metaphysics, around 350 B.C., translated by W. D. Ross, e-print

K. Svozil, How real are virtual realities, how virtual is reality? The constructive re-interpretation of physical undecidability, in Complexity, in press.


1  A short history of set theory, with emphasis on operationalism
2  The ``Go-Go'' principle
    2.1  ``Chaos'' theory
    2.2  Isometric miracles
    2.3  Oracle computing
    2.4  Weak solutions
3  The alternatives
    3.1  Abandon non-operational entities altogether
    3.2  ``Go-Go'' science
    3.3  Synthesis
4  Epilogue: mathematical versus physical universe



``Insofern sich die Sätze der Mathematik auf die Wirklichkeit beziehen, sind sie nicht sicher, und insofern sie sicher sind, beziehen sie sich nicht auf die Wirklichkeit.''

2 ``Unter einer ``Menge'' verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unsrer Anschauung oder unseres Denkens (welche die ``Elemente'' von M genannt werden) zu einem Ganzen.''

3 ``Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können.''

4 ``Eine Vielheit kann nämlich so beschaffen sein, daß   die Annahme eines ``Zusammenseins'' aller ihrer Elemente auf einen Widerspruch führt, so daß   es unmöglich ist, die Vielheit als eine Einheit, als ``ein fertiges Ding'' aufzufassen. Solche Vielheiten nenne ich absolut unendliche oder inkonsistente Vielheiten. [Absatz] Wie man sich leicht überzeugt, ist z. B. der ``Inbegriff alles Denkbaren'' eine solche Vielheit; ''

5 ``Und so wie das Operieren mit dem Unendlichkleinen durch Prozesse im Endlichen ersetzt wurde, welche ganz dasselbe leisten und zu ganz denselben eleganten Beziehungen führen, so müssen überhaupt die Schluß weisen mit dem Unendlichen durch endliche Prozesse ersetzt werden, die gerade dasselbe leisten, d.h. dieselben Beweisgänge und dieselben Methoden der Gewinnung von Formeln und Sätzen ermöglichen.''

6 The author wants to make it quite clear that he neither rejects nor supports the ``Go-Go'' principle for reasons which are discussed below.

7 My first denomination of this style was ``No-No.'' The present term ``No-Go'' is due to a Freudian slip by Professor Joseph F. Traub.

8 I would also like to point the reader's attention to the question of the preservation of computability in classical analysis; in particular to older attempts by Specker [], Wang [], Kreisel [] and Stef anescu [], as well as to the more recent ones by Pour-El and Richards [] (cf. objections raised by Penrose [] and Bridges []) and Calude, Campbell, Svozil and tef anescu [].

9 In a very recent book on finite precision computations by Chaitin-Chatelin and Fraysseé [] point out that, in a certain, well-defined way, exact absolute information is too unstable and does not give rise to the full richness of physical solutions. In particular, finite-precision arithmetic is more suitable to model physical systems that fluctuate.

10 There seem to be powerful counter-rationalistic forces, not to mention wishful thinking, which seduce people into believe systems that physics has ``finally re-discovered'' ever-to-remain obscure phenomena, that we are even on the verge of the ``end of the age of the natural sciences;'' forces which seem to be directed against the scientific research program of the Enlightenment put forward by Descartes, Hume, Humboldt and others.

11 For the remainder of this paper we fix a finite alphabet A and denote by A* the set of all strings over A; |x| is the length of the string x. A (Chaitin) computer C is a partial recursive function carrying strings (on A) into strings such that the domain of C is prefix-free, i.e. no admissible program can be a prefix of another admissible program. If C is a computer, then C(x) = y denotes that C terminates on program x and outputs y. denotes empty input or output. TC denotes the time complexity, i.e. TC(x) is the running time of C on the entry x, if x is in the domain of C; TC(x) is undefined in the opposite case.

12 Notice that this scenario remains true for any (infinite) dense set such as the rationals or the computable numbers (cf. recursive unsolvability of the rule inference problem []). The time necessary to exactly specify an arbitrary initial value can only be finitely bounded for discrete, finite models such as ones involving a fundamental cut-off parameter which would essentially truncate the reals at some final decimal place M after the comma (or, equivalently, an equivalence relation identifying all reals in the interval [i = 1M ri,i = 1M ri+10-M).

13 In German, ``aus einer Mücke einen Elefanten machen.''

14 Suppose a group G acts on A X. Then Tarski's theorem states that there exists a finitely-additive, G-invariant measure m:P(x) [0,) with m(A) = 1 if and only if A is not G-paradoxical. For more results and questions see Wagon's book [].

15 Every time claims that the means at hand are final. Nowadays, for example, faster-than-light travel or superluminal signalling is not feasible. But does that mean that faster-than-light travel or superluminal signalling is impossible?

16 See Jaffe and Quinn [] for a discussion of a related aspect.

17 Aristotle proceeds, ``-only not numbers consisting of abstract units; they suppose the units to have spatial magnitude. But how the first 1 was constructed so as to have magnitude, they seem unable to say.''

18 No attempt is made here to review the many-worlds interpretation of quantum mechanic, or other exotic speculations such as parallel universes in cosmology.

19 Here, only strong enough formalisms, in which arithmetic and universal computation can be implemented, will be considered. Weaker mathematical universes would be monotonous.

20 As has been noticed before, naive (i.e., non-axiomatic) approaches are unreliable and plagued by inconsistencies.

File translated from TEX by TTH, version 1.94.
On 9 Sep 1999, 13:49.