When algorithms collide: An infinite sum that isn't (or is it?)

This page went online Dec. 26, 2001

Peano, Hilbert and others devised space-filling curves about a century ago, helping to initiate the field of topology. So, from a topological standpoint, the result below is unremarkable.

Yet, philosophically it seems curious that the same structure can yield two different values.

---

It seems quite reasonable that an area under a curve is ever better approximated by summing areas defined by rectangular strips that fit the area ever more closely. At the limit of width w = 0, the area is defined as the infinite sum of vertical heights f(x) between x=a and x=b. This calculus approximation algorithm is standard.

Yet it is possible to devise an algorithm which seems to yield a sum of y heights that clashes with the area algorithm.

We create a sawtooth path between some curve f(x) and a finite x axis interval by this means: Divide the interval by h, keeping h a positive odd integer. Then trace the path a to f(a) to f(a+1/h) to f(a+2/h) to a+2/h to a+3/h to f(a+3/h) ... to f(a+n/h) to a+n/h = b. The length of this path is always longer than the path connecting the discrete points of f(x). [There are more than two points between f(a) and f(a+1/h) for the sawtooth path but only two points for the other path.]

As h approaches infinity, the number of sawteeth approaches infinity. At the limit of h=infinity, the sawteeth have narrowed to the infinitesimal area f(x), where the route is presumably twice f(x). But the infinite sum of f(x) cannot be infinite if the area is finite (fits inside a finite square). Quite often, the infinite sum (the integral) is less than the continuous arc length for f(x).

So this would seem to indicate that the sawtooth function must be considered undefined at h = infinity.

The special case of the unit square makes this plain:

Use the unit square lying on the positive x axis between origin and x=1. Divide 1 by the odd (for convenience) positive integer h. Trace a sawtooth path from 0,0 to 0,1 to 1/h,1 to 1/h,0 to 2/h,0 to 2/h,1 and so on to 1,0. The sawtooth path length is h+2. As h approaches infinity, the sawtooth path length also nears infinity.

It would seem that at the limit, the 'infinitesimal entity' is twice the height f(x). The sum is the integral of f(x), which, by the fundamental theorem of calculus, is the area quantified as 1.

So that at infinity, if the sawtooth function exists, the sawtooth route length collapses to distance 1.

But would a long-lived or very speedy salesman traveling through all the points of a sawtooth curve find that the sawtooth route is optimal at infinity?

The area is rarely directly proportional to some x interval or radius. For example, take any finite radius circle and define its radius as 1. Then the area is less than the circumference. But take exactly the same circle and define its radius as 3, and now the area is greater than the circumference. Now make a sawtooth path through half of the same circle.

The salesman will find, as h increases, that his path length exceeds the area quantity for every h after some h=k. If the sawtooth algorithm is completable (an 'actual infinity' is agreed), then he would appear to find that the optimal route is the sawtooth route.

But, there is an infinity of areas that can be assigned to the semicircle. For every area quantity there exists a k after which h means that the sawtooth path length is longer.

This observation can be generalized.

So we conclude that the sawtooth function is either unbounded or undefined at h's infinite limit.

If we say it is unbounded, however, we would need to explain why we are forbidden to sum the f(x) heights.

As my son Jim, a Cornell topologist, points out, sawtooth functions are well-known for producing curves with infinite perimeters that contain a finite area, the Koch snowflake being a famous example.

Of course the issue here is not that such functions occur but that the logical conclusion of this particular sawtooth algorithm yields an anomolous result.

Disjoint nondenumerable sets of irrationals

[This page went online Feb. 28, 2002.]

I wish to thank Amherst logician Dan Velleman, author of 'How to Prove It,' for not permitting any slack or insecure arguments. He has not vouched for the final version of this theorem and proof. The theorem itself is nothing special. But the proof is amusing in that it gives an inkling of how vast is the sea of irrationals with respect to the rationals.

Theorem: There exists a denumerable infinite family of sets such that each family member is a nondenumerable set of irrationals that is disjoint from every other member.

Proof:

We establish a monotonically climbing differentiable real function h(x), where x is continuous, and where the first derivative exists and is neither a constant nor a periodic (as in cos(ax)). We use only the integer values h(n) in our proof.

We denote a rational q's infinite decimal digit string by S_0 and its recurring finite substring by s. We see that the first digit of s, which has k digit places, recurs every (nk)th digit place. We denote the initial digit place of s by p. We pair p with d_2, which symbolizes a specific numeral digit. Initially, we are assuming a base 10 system.

We then establish the erase-and-replace function f by locating the h(n)th (p, d_2) and replacing d_2 with d_3.

The altered string, S_x, is forever aperiodic.

Example:

s = (01), k = 2, h = n^2

S_0 = 0.010101010101010101...

S_x = 0.210101210101010121...

We know the set of h functions is infinite and we presume that that set, and hence the set of f functions, is denumerable. So we form the indexed set U f_i.

However, this permits us to form a 'diagonal' function g, such that g is formed by the sequence f_1(1), f_2(2), f_3(3) ... ad infinitum. We then alter the g(n)th (p,d_1) by use of a third digit symbol, writing (p,d_3).

Since g is aperiodic and cannot be indexed, we have established a nondenumerable set of irrationals, which we denote R.

In general, we will write R_a to mean the set R derived from the rational q_a.

Indexing the denumerable set of rationals by j, we question whether R_1 intersection R_2 is nonempty. If empty, we proceed consecutively until we find -- if ever -- R_1 intersection R_j is nonempty.

In that event, we form a new function t_i and require use of (p, d_4) on the subset of R_j strings, denoted R'_j, that are identical to R_1 strings. R_j U R'_j we call T_j (which still holds if R_j U R'_j = R_j). We then proceed to the next instance where R_j intersection R_(j+n) is nonempty. Again, we insert digit d_5, obtaining T_(j+n).

Obviously, with a base 10 system, this procedure can be repeated 9 times.

As the number of digit places in s is irrelevant, we can increase our set of available digits with a higher base number system. In that case, we apply induction: If a base m system yields m-1 replacement digits, then a base m+1 system, yields m replacement digits.

With m e M = N, and N denumerable, we find that the family U( T_j) exists, where J = N, requiring that U( T) is denumerable and that for all j e J, n e N(T_j is disjoint from T_(j+n).

Proof concluded.

Remark: It is curious that the set of writable functions is considered denumerable because each expression is composed of a finite string of symbols. For example, 2 + log x, contains 9 symbols, including spaces. Hence, each such expression can be counted, and the entire set of such expressions must also be countable. Since our diagonal function is writable as g(n) = f_n(n), we have shown a nondenumerable subset of writable functions.

A geometric note on Russell's paradox

A lengthier discussion of Russell's paradox was found on my web page on vacuous truth before it vanished into the vacuum left by the demise of Geocities. It is there that I discuss banishing 'actual infinity' and replacing it with construction algorithms. However, such an approach, though countering other paradoxes, does not rid us of Russell's, which is summed up with the question: If sets are sorted into two types: those that are elements of themselves ('S is the name of a set that contains sets named for letters of the alphabet' is an example) and those that are not, then what type of set is the set that contains sets that are elements of themselves?

---

Here we regard the null set as the initial set and build sets from there, as in:

Step 0: { }

Step 1: { { { } },{ } }

Using an axiom of infinity, we can continue this process indefinitely, leading directly to a procedure for building an abstraction of all countable sets; indirectly, noncountable sets can also be justified.

In Russell's conundrum, some sets are elements of themselves.

So let us regard a plane as pre-existent (null space or some such) and regard Set sub 0, the empty set, as a circle surrounding nothing. Set sub 1 we picture as a concentric circle around set 0. Now those two circles express the element represented as {{ }}.

We might also say the two circles express the set that contains the element { }.

In that case, we may wish to say that the set {{ }} = the element {{ }}.

Suppose we establish two construction algorithms for sets of concentric circles. In algorithm A, the outer circle is a solid line, so that the null space container is not construed to be part of the set. In algorithm B, the outer circle is a dashed line, so that the null space container is construed to be part of the set.

At each step we add a new enclosing circle and require that it be either solid or dashed.

So as step n is taken to infinity, we find that the null space container vanishes. That is, the circles fill the plane.

In that case, the container is non-existent or undefined, so that the rule that requires that it be either part of the set or not part of the set is not applicable.

We have assumed that the initial circle surrounds something that is not an element -- as with { }. But we really must give a rule that says the inmost area is not an element. We could have a rule that permits not only the outmost but the inmost circle to be dashed. In that case the inner void would be considered a part (element) of the set. Though the void in a null set is, for sound reasons, not permitted to be construed as an element, it is still useful to see the relationship of admitting the inner void to Russell's paradox.

---

Russell's paradox is usually disposed of by resort to an axiom prohibiting a set from being an element of itself. But we can see that sets and elements can be identical except for the rule prohibiting a set belonging to itself.

For example, element {{ }} in a set-building algorithm X is identical to the set containing the element { } in set-building algorithm Y.

It seems that the axiom while necessary remains questionable from the standpoint of logical consistency.

---

First published ca. 2000

An algorithm to imply the set of reals

I have reconsidered my initial idea that the algorithm I give proves non-denumerability of the reals, an idea which I based on the fact that there is no n for which a cellular diagonal exists that intercepts every row of cells. However, despite intuition, it does not immediately follow that no such diagonal exists for the infinite set.

---

An algorithm to imply the set of reals

We present an algorithm for "constructing" the entire set of reals and find that our intuition suggests that no diagonal can exist, which accords with Cantor's proof.

Cantor's diagonalization proof says that if it were possible that all reals were listed, then one could create an anti-diagonal number from the diagonal that intersects all the listed numbers. Hence, no such diagonal exists and the set of reals is not 1-to-1 with the set of naturals.

However, we are assuming that there is a set N containing all naturals. We are also assuming that because a finite n x n square always has a (non-Pythagorean diagonal of n cells) that intersects every row, then the same holds for the tiled quarter-plane.

However, the infinity axiom says that N exists, in which case we may say that the set of X axis integers is 1-to-1 with the set of Y axis integers, and further that the cellular diagonal with a cell vertex at (0,0) has cardN and intersects every horizontal string of cells bounded by y and y+1. In that case, we may use Cantor's argument to say that the reals can't be mapped 1-to-1 onto this tiling.

Interestingly, our algorithm for constructing all the reals intuitively says that such a set has no diagonal. But, that intuition is simply an intuition until we apply Cantor's proof and the infinity axiom.

We write an algorithm for determining the set of reals, thus:

We have the set of 1x1 square cells in a quadrant of the Cartesian grid. Each square is eligible to contain a digit. We consider only the horizontal strings of cells.

Suppose we use a base 2 system. We begin at step 0 using 2 consecutive spaces and obtaining 4 possible combinations, to wit: 00, 11, 10, 01. For step 1 (3 spaces), the number of combinations is 2*4 and for step n the number of combinations is 2ⁿ⁺².

At lim_n->inf. 2ⁿ⁺², we have established all base 2 infinite digit strings, expressing the entire set of reals greater than an arbitrary j e Z and less than or equal to j+1.

Remark: Our algorithm does not compute reals sequentially. It only computes 'pre-reals,' since a real is defined here as an infinite digit string. No element "materializes" prior to the entire set's establishment at (denumerable) infinity.

The algorithm above requires that for any step n, the set of digit strings is a rectangle n2ⁿ⁺².

But lim_n->inf. n/2ⁿ = 0, meaning the rectangle elongates and narrows toward a limiting form of a half-line.

For an integer diagonal to include an element of all horizontal digit strings, we must have a square of n columns and n rows. But such a square of the reals is never attainable. It would then seem safe to say that the set of reals, expressed as infinite digit strings, has no diagonal, which is equivalent to saying the set of reals is non-denumerable.

However, our intuition that the set of reals so constructed should have no diagonal is provable by agreement to the infinity axiom, which permits the cardN diagonal, and by Cantor's anti-diagonal result.

It also follows that no exponentially defined set of tiles n x kⁿ has a cellular diagonal at the tiling algorithm's infinite limit.

On the other hand, a tiling defined by n^k can be said to have k cellular diagonals, such that collectively the k diagonals intersect every horizontal cellular string. It then can be shown that such a tiling is one-to-one with N.

Interestingly, the power set of any n e N has card2ⁿ, which corresponds to step n of our algorithm, in which we have a set of 2ⁿ⁺² pre-reals.

Additional remark:

Lemma: Any set with lim_n->inf kⁿ elements has the cardinality of the reals, with k =/= 0, -1, 1 and k e Z.

Proof:

The set of reals is 1-to-1 with a set that has lim_n->inf 2ⁿ elements. Hence the cardinality of each set is identical. Similarly, the algorithm above can be rewritten as ckⁿ, with c a nonzero integer constant, meaning that all real digit strings are established at lim_n->inf ckⁿ.

Theorem: Some non-enumerable reals can be approximated with explicit rationals to any degree of accuracy in a finite number of steps.

Proof:

Construct n Turing machines consecutively, truncating the initial integer, and compute each one's output as a digit string n digits long. Use some formula to change each diagonal digit.

The infinite diagonal cannot be encoded as a Turing machine number, so it is not enumerable. Yet a computer can compute its approximation as a rational up to n. (The accuracy of this approximation is the same as the accuracy obtainable, in principle, for an enumerable irrational.)

Comment: The denumerable set of computables implies an extension of the concept of denumerability.

Justification:

We give these instructions for diagonalizing Turing computables:

Up to and including the nth diagonal space, follow this rule: if a digit is not 0, replace it with 0; if 0, replace it with 1. After the nth diagonal space, follow this rule: if a digit is not 2, replace it with 2; if it is 2, replace it with 3.

None of these diagonals is enumerable with respect to the Turing numbers. Yet we have a countably infinite set of diagonals. Hence, non-denumerability implies the existence of two denumerable sets of reals which are not denumerable with respect to each other.

If we diagonalize the diagonals, it is not apparent to me that this real is not a member of the computables.

Definition of choice sequence:

If f(n) gives a_n of cauchy sequence {a_n}, then {a_n} is a choice sequence if f(n) --> a_on+1 or a_1n+1 or . . . or a_mn+1.

Note i.Since a choice sequence is cauchy |a_m - a_n| <= 1/k for all m and n after some n_o. However, the rule for determining step n+1 means that more than one choice sequence is possible for every n after some n_o. That is, a choice sequence's limiting value must fall within an upper and lower bound.

Note ii: It may be that a_xn+1 is non-randomly determined. Yet, there exists an infinity of choice sequences such that the limiting value of {a_n} is an effectively random element of some infinite subset of reals (known as a 'spread') bounded by a least upper bound and a greatest lower bound.

Remark: Though choice sequences are primarily of interest to intuitionists, here we require that they be governed by ZFC.

Theorem: The question of whether the set of choice sequences contains an element with a non-enumerable limiting value is not decidable.

Proof:

We first prove (Lemma i) that within a spread (x,y), with x the GLB and y the LUB, a non-enumerable exists.

Use a diagonalization formula on the digit string outputs from the set of Turing machines, obtaining one non-enumerable real. Prefix, in turn, every rational digit string to this real and then move the decimal point to the front of each new string. Lemma i is proved.

So then suppose x and y are irrational enumerables. Rationals arbitrarily close to x from above and to y from below can be found.

Let x < p and q < y. So calling the choice sequence limit L, we have

Case i: (x < p < L < q < y).

Case ii: The possibility x < L < p exists, but then a smaller rational can be found between x and L.

Case iii: Likewise for the possibility q < L < y.

It is now straightforward that if L is a choice function limit, there is an effectively random possibility that L is enumerable or non-enumerable. This possibility is in principle undecidable.

Though probability laws suggest that the set of choice sequences includes a sequence with a non-enumerable limit, this suggestion is undecidable.

The cosmos cannot be fully modeled as a Turing machine or Turing computation

Dave Selke, an electrical engineer with a computer background, has made a number of interesting comments concerning this page, spurring me to redo the argument in another form. The new essay is entitled "On Hilbert's sixth problem" and may be found at

http://paulpages.blogspot.com/2011/11/first-published-tuesday-june-26-2007-on.html

Draft 3 (Includes discussion of Wolfram cellular automata)
Comments and suggestions welcome  

---

Note: The word "or" is usually used in the following discussion in the inclusive sense.

---

Many subscribe to the view that the cosmos is essentially a big machine which can be analyzed and understood in terms of other machines.

A well-known machine is the general Turing machine, which is a logic system that can be modified to obtain any discrete-input computation. Richard Feynman, the brilliant physicist, is said to have been fascinated by the question of whether the cosmos is a computer -- originally saying no but later insisting the opposite. As a quantum physicist, Feynmen would have realized that the question was difficult. If the cosmos is a computer, it certainly must be a quantum computer. But what does that certainty mean? Feynmen, one assumes, would also have concluded that the cosmos cannot be modeled as a classical computer, or Turing machine [see footnote below].

Let's entertain the idea that the cosmos can be represented as a Turing machine or Turing computation. This notion is equivalent to the idea that neo-classical science (including relativity theory) can explain the cosmos. That is, we could conceive of every "neo-classical action" in the cosmos to date -- using absolute cosmic time, if such exists -- as being represented by a huge logic circuit, which in turn can be reduced to some instance (computation) of a Turing algorithm. God wouldn't be playing dice.

A logic circuit always follows if-then rules, which we interpret as causation. But, as we know, at the quantum level, if-then rules only work (with respect to the observer) within constraints, so we might very well argue that QM rules out the cosmos being a "classical" computer.

On the other hand, some would respond by arguing that quantum fuzziness is so miniscule on a macroscopic (human) scale, that the cosmos can be quite well represented as a classical machine. That is, the fuzziness cancels out on average. They might also note that quantum fluctuations in electrons do not have any significant effect on the accuracy of computers -- though this may not be true as computer parts head toward the nanometer scale. (My personal position is that there are numerous examples of the scaling up or amplification of quantum effects. "Schrodinger's cat" is the archetypal example.)

Of course, another issue is that the cosmos should itself have a wave function that is a superposition of all possible states -- until observed by someone (who?). (I will not proceed any further on the measurement problem of quantum physics, despite its many fascinating aspects.)

Before going any further on the subject at hand, we note that a Turing machine is finite (although the set of such machines is denumerably infinite). So if one takes the position that the cosmos -- or specifically, the cosmic initial conditions (or "singularity") -- are effectively infinite, then no Turing algorithm can model the cosmos.

So let us consider a mechanical computer-robot, A, whose program is a general Turing machine. A is given a program that instructs the robotic part of A to select a specific Turing machine, and to select the finite set of initial values (perhaps the "constants of nature"), that models the cosmos.

What algorithm is used to instruct A to choose a specific cosmos-outcome algorithm and computation? This is a typical chicken-or-the-egg self-referencing question and as such is related to Turing's halting problem, Godel's incompleteness theorem and Russell's paradox.

If there is an algorithm B to select an algorithm A, what algorithm selected B? -- leading us to an infinite regression.

Well, suppose that A has the specific cosmic algorithm, with a set of discrete initial input numbers, a priori? That algorithm, call it T_c, and its instance (the finite set of initial input numbers and the computation, which we regard as still running), imply the general Turing algorithm T_g. We know this from the fact that, by assumption, a formalistic description of Alan Turing and his mathematical logic result were implied by T_c. On the other hand, we know that every computable result is programable by modifying T_g. All computable results can be cast in the form of "if-then" logic circuits, as is evident from Turing's result.

So we have

Tc <--> Tg

Though this result isn't clearly paradoxical, it is a bit disquieting in that we have no way of explaining why Turing's result didn't "cause" the universe. That is, why didn't it happen that T_g implied Turing who (which) in turn implied the Big Bang? That is, wouldn't it be just as probable that the universe kicked off as Alan Turing's result, with the Big Bang to follow? (This is not a philisophical question so much as a question of logic.)

Be that as it may, the point is that we have not succeeded in fully modeling the universe as a Turing machine.

The issue in a nutshell: how did the cosmos instruct itself to unfold? Since the universe contains everything, it must contain the instructions for its unfoldment. Hence, we have the T_c instructing its program to be formed.

Another way to say this: If the universe can be modeled as a Turing computation, can it also be modeled as a program? If it can be modeled as a program, can it then be modeled as a robot forming a program and then carrying it out?

In fact, by Godel's incompleteness theorem, we know that the issue of T_c "choosing" itself to run implies that the T_c is a model (mathematically formal theory) that is inconsistent or incomplete. This assertion follows from the fact that the T_c requires a set of axioms in order to exist (and hence "run"). That is, there must be a set of instructions that orders the layout of the logic circuit. However, by Godel's result, the Turing machine is unable to determine a truth value for some statements relating to the axioms without extending the theory ("rewiring the logic circuit") to include a new axiom.

This holds even if T_c = T_g (though such an equality implies a continuity between the program and the computation which perforce bars an accurate model using any Turing machines).

So then, any model of the cosmos as a Boolean logic circuit is inconsistent or incomplete. In other words, a Turing machine cannot fully describe the cosmos.

If by "Theory of Everything" is meant a formal logico-mathematical system built from a finite set of axioms [though, in fact, Zermelo-Frankel set theory includes an infinite subset of axioms], then that TOE is either incomplete or inconsistent. Previously, one might have argued that no one has formally established that a TOE is necessarily rich enough for Godel's incompleteness theorem to be known to apply. Or, as is common, the self-referencing issue is brushed aside as a minor technicality.

Of course, the Church thesis essentially tells us that any logico-mathematical system can be represented as a Turing machine or set of machines and that any logico-mathematical value that can be expressed from such a system can be expressed as a Turing machine output. (Again, Godel puts limits on what a Turing machine can do.)

So, if we accept the Church thesis -- as most logicians do -- then our result says that there is always "something" about the cosmos that Boolean logic -- and hence the standard "scientific method" -- cannot explain.

Even if we try representing "parallel" universes as a denumerable family of computations of one or more Turing algorithms, with the computational instance varying by input values, we face the issue of what would be used to model the master programer.

Similarly, one might imagine a larger "container" universe in which a full model of "our" universe is embedded. Then it might seem that "our" universe could be modeled in principle, even if not modeled by a machine or computation modeled in "our" universe. Of course, then we apply our argument to the container universe, reminding us of the necessity of an infinity of extensions of every sufficiently rich theory in order to incorporate the next stage of axioms and also reminding us that in order to avoid the paradox inherent in the set of all universes, we would have to resort to a Zermelo-Frankel-type axiomatic ban on such a set.

Now we arrive at another point: If the universe is modeled as a quantum computation, would not such a framework possibly resolve our difficulty?

If we use a quantum computer and computation to model the universe, we will not be able to use a formal logical system to answer all questions about it, including what we loosely call the "frame" question -- unless we come up with new methods and standards of mathematical proof that go beyond traditional Boolean analysis.

Let us examine the hope expressed in Stephen Wolfram's New Kind of Science that the cosmos can be summarized in some basic rule of the type found in his cellular automata graphs.

We have no reason to dispute Wolfram's claim that his cellular automata rules can be tweaked to mimic any Turing machine. (And it is of considerable interest that he finds specific CA/TM that can be used for a universal machine.)

So if the cosmos can be modeled as a Turing machine then it can be modeled as a cellular automaton. However, a CA always has a first row, where the algorithm starts. So the algorithm's design -- the Turing machine -- must be axiomatic. In that case, the TM has not modeled the design of the TM nor the specific initial conditions, which are both parts of a universe (with that word used in the sense of totality of material existence).

We could of course think of a CA in which the first row is attached to the last row and a cylinder formed. There would be no specific start row. Still, we would need a CA whereby the rule applied with aribitrary row n as a start yields the same total output as the rule applied at arbitrary row m. This might resolve the time problem, but it is yet to be demonstrated that such a CA -- with an extraordinarily complex output -- exists. (Forgive the qualitative term extraordinarily complex. I hope to address this matter elsewhere soon.)

However, even with time out of the way, we still have the problem of the specific rule to be used. What mechanism selects that? Obviously it cannot be something from within the universe. (Shades of Russell's paradox.)

---

Footnote

Informally, one can think of a general Turing machine as a set of logic gates that can compose any Boolean network. That is, we have a set of gates such as "not", "and," "or," "exclusive or," "copy," and so forth. If-then is set up as "not-P or Q," where P and Q themselves are networks constructed from such gates. A specific Turing machine will then yield the same computation as a specific logic circuit composed of the sequence of gates.

By this, we can number any computable output by its gates. Assuming we have less than 10 gates (which is more than necessary), we can assign a base-10 digit to each gate. In that case, the code number of the circuit is simply the digit string representing the sequence of gates.

Note that circuit A and circuit B may yield the same computation. Still, there is a countable infinity of such programs, though, if we use any real for an input value, we would have an uncountable infinity of outputs. But this cannot be, because an algorithm for producing a real number in a finite number of steps can only produce a rational approximation of an irrational. Hence, there is only a countable number of outputs.

---

*************************

Thanks to Josh Mitteldorf, a mathematician and physicist, for his incisive and helpful comments. Based upon a previous draft, Dr. Mitteldorf said he believes I have shown that, if the universe is finite, it cannot be modeled by a subset of itself but he expressed wariness over the merit of this point.

Alternate proof

of the Schroeder-Bernstein theorem

PlanetMath's standard proof

Wikipedia's standard proof

Draft 2   The following proof of the Schroeder-Bernstein theorem is, as far as I know, new as of April 2006. The standard proof can be found at the links above.   Notation:  "cardA" denotes the cardinal number of a set A. "<=" means "less than or equal to." "~" means "equinumerous to." 

Schroeder-Bernstein theorem: If, and only if, A and B are sets such that card A <= cardB and card B <= card A, then cardA = cardB.

Proof:

Remark: We grant that the transitivity of subsets is established from axioms. That is, A Í B Í C implies A Í C. Further, for nonempty sets, we accept that if A Ì B, then B Ì A is false. This follows from the definition of subset: for all x, x element of X implies x element of Y. But, if A is a proper subset of A, then, for some b, b element of B implies b is not an element of A. Hence B does not fit the definition of subset of A.

We rewrite cardA <= cardB and card B <= card A, thus:

A ~ C Í B and B ~ D Í A

If

Suppose A ~ C = B. Then we are done. Likewise for B ~ D = A. So we test the situation for nonempty sets with: A ~ C Ì B and B ~ D Ì A. (We note that if C ~ D, then A ~ B, spoiling our interim hypothesis. So we assume C is not equinumerous to D.)

We now form the sets A U C and B U D, permitting us to write (A U C) Ì (A U B) and (B U D) Ì (A U B).

We now have two options:

i) (A U C) Ì (A U B) Ì (B U D) Ì (A U B)

This is a contradiction since A U B cannot be a proper subset of itself.

ii) (A U C) Ì (A U B) É (B U D) Ì (A U B)

Also a contradiction, since B U D cannot be a proper subset of A U B and also properly contain A U B.

Only if

We let B = C and D = A.

---

This proof, like the standard modern proof, does not rely on the Axiom of Choice.

---

In search of a blind watchmaker

Richard Dawkins' web site
Wikipedia article on Dawkins
Wikipedia article on Francis Crick
Abstract of David Layzer's two-tiered adaptation
Joshua Mitteldorf's home page
Do dice play God? A book review

A discussion of The Blind Watchmaker: Why the Evidence of Evolution Reveals a Universe without Design by Richard Dawkins  First posted Oct. 5, 2010 and revised as of Oct. 8, 2010  Please notify me of errors or other matters at "krypto78...at...gmail...dot...com"   

By PAUL CONANT

Surely it is quite unfair to review a popular science book published years ago. Writers are wont to have their views evolve over time.¹ Yet in the case of Richard Dawkins' The Blind Watchmaker: Why the Evidence of Evolution Reveals a Universe without Design (W.W. Norton 1986), a discussion of the mathematical concepts seems warranted, because books by this eminent biologist have been so influential and the "blind watchmaker" paradigm is accepted by a great many people, including a number of scientists.

Dawkins' continuing importance can be gauged by the fact that his most recent book, The God Delusion (Houghton Mifflin 2006), was a best seller, and by the links above. In fact, Watchmaker, also a best seller, was re-issued in 2006.

I do not wish to disparage anyone's religious or irreligious beliefs, but I do think it important to point out that non-mathematical readers should beware the idea that Dawkins has made a strong case that the "evidence of evolution reveals a universe without design."

There is little doubt that some of Dawkins' conjectures and ideas in Watchmaker are quite reasonable. However, many readers are likely to think that he has made a mathematical case that justifies the theory(ies) of evolution, in particular the "modern synthesis" that combines the concepts of passive natural selection and genetic mutation.

Dawkins wrote his apologia back in the eighties when computers were becoming more powerful and accessible, and when PCs were beginning to capture the public fancy. So it is understandable that, in this period of burgeoning interest in computer-driven chaos, fractals and cellular automata, he might have been quite enthusiastic about his algorithmic discoveries.

However, interesting computer programs may not be quite as enlightening as at first they seem.

Cumulative selection

Let us take Dawkins' argument about "cumulative selection," in which he uses computer programs as analogs of evolution. In the case of the phrase, "METHINKS IT IS LIKE A WEASEL," the probability -- using 26 capital letters and a space -- of coming up with such a sequence randomly is 27^-28 (the astonishingly remote 8.3 x 10^-41). However, that is also the probability for any random string of that length, he notes, and we might add that for most probability distributions. when n is large, any distinct probability approaches 0.

Such a string would be fantastically unlikely to occur in "single step evolution," he writes. Instead, Dawkins employs cumulative selection, which begins with a random 28-character string and then "breeds from" this phrase. "It duplicates it repeatedly, but with a certain chance of random error -- 'mutation' -- in the copying. The computer examines the mutant nonsense phrases, the 'progeny' of the original phrase, and chooses the one which, however slightly most resembles the target phrase, METHINKS IT IS LIKE A WEASEL."

Three experiments evolved the precise sentence in 43, 64 and 41 steps, he wrote.

Dawkins' basic point is that an extraordinarily unlikely string is not so unlikely via "cumulative selection."

Once he has the readers' attention, he concedes that his notion of natural selection precludes a long-range target and then goes on to talk about "biomorph" computer visualizations (to be discussed below).

Yet it should be obvious that Dawkins' "methinks" argument applies specifically to evolution once the mechanisms of evolution are at hand. So the fact that he has been able to design a program which behaves like a neural network, really doesn't say much about anything. He has achieved a proof of principle that was not all that interesting, although I suppose it would answer a strict creationist, which was perhaps his basic aim.

But which types of string are closer to the mean? Which ones occur most often? If we were to subdivide chemical constructs into various sets, the most complex ones -- which as far as we know are lifeforms -- would be farthest from the mean.(Dawkins, in his desire to appeal to the lay reader, avoids statistics theory other than by supplying an occasional quote from R.A. Fisher.)

Let us, like Dawkins, use a heuristic analog². Suppose we take the set of all grammatical English sentences of 28 characters. The variable is an English word rather than a Latin letter or space. What would be the probability of any 28-character English sentence appearing randomly?

My own sampling of a dictionary found that words with eight letters appear with the highest probability of 21%. So assuming the English lexicon to contain 500,000 words, we obtain about 105,000 words of length 8.

Now let us do a Fermi-style rough estimate. For the moment ignoring spaces, we'll posit average word length of 2 to 9 as covering virtually all combinations. That is, we'll pretend there are sentences composed of only two-letter words, only three-letter and so on up to nine letters. Further, we shall put an upper bound of 10⁵ on the set of words of any relevant length (dropping the extra 5,000 for eight-letter words as negligible for our purposes).

This leads to a total number of combinations of (10⁵)² + 10⁸ + ... + 10¹⁴, which approximates 10¹⁴.

We have not considered spaces nor (directly) combinations of words of various lengths. It seems overwhelmingly likely that any increases would be canceled by the stricture that sentences be grammatical, something we haven't modeled. But, even if the number of combinations were an absurd 10 orders of magnitude higher, the area under the part of some typical probability curve that covers all grammatical English sentences of length 28 would take up a miniscule percentage of a tail.

Analogously, to follow Dawkins, we would suspect that the probability is likewise remote for random occurrence of any information structure as complex as a lifeform.

To reiterate, the entire set of English sentences of 28 characters is to be found far out in the tail of some probability distribution. Of course, we haven't specified which distribution because we have not precisely defined what is meant by "level of complexity." This is also an important omission by Dawkins.

We haven't really done much other than to underscore the lack of precision of Dawkins' analogy.

Dawkins then goes on to talk about his "biomorph" program, in which his algorithm recursively alters the pixel set, aided by his occasional selecting out of unwanted forms. He found that some algorithms eventually evolved insect-like forms, and thought this a better analogy to evolution, there having been no long-term goal. However, the fact that "visually interesting" forms show up with certain algorithms again says little. In fact, the remoteness of the probability of insect-like forms evolving was disclosed when he spent much labor trying to repeat the experiment because he had lost the exact initial conditions and parameters for his algorithm. (And, as a matter of fact, he had become an intelligent designer with a goal of finding a particular set of results.)

Again, what Dawkins has really done is use a computer to give his claims some razzle dazzle. But on inspection, the math is not terribly significant.

It is evident, however, that he hoped to counter Fred Hoyle's point that the probability of life organizing itself was equivalent to a tornado blowing through a junkyard and assembling from the scraps a fully functioning 747 jetliner, Hoyle having made this point not only with respect to the origin of life, but also with respect to evolution by natural selection.

So before discussing the origin issue, let us turn to the modern synthesis.

The modern synthesis

I have not read the work of R.A. Fisher and others who established the modern synthesis merging natural selection with genetic mutation, and so my comments should be read in this light.

Dawkins argues that, although most mutations are either neutral or harmful, there are enough progeny per generation to ensure that an adaptive mutation proliferates. And it is certainly true that, if we look at artificial selection -- as with dog breeding -- a desirable trait can proliferate in very short time periods, and there is no particular reason to doubt that if a population of dogs remained isolated on some island for tens of thousands of years that it would diverge into a new species, distinct from the many wolf sub-species.

But Dawkins is of the opinion that neutral mutations that persist because they do no harm are likely to be responsible for increased complexity. After all, relatively simple life forms are enormously successful at persisting.

And, as Stephen Wolfram points out (A New Kind of Science, Wolfram Media 2006), any realistic population size at a particular generation is extremely unlikely to produce a useful mutation because the ratio of possible mutations to the number of useful ones is some very low number. So Wolfram also believes neutral mutations drive complexity.

We have here two issues:

1. If complexity is indeed a result of neutral mutations alone, increases in complexity aren't driven by selection and don't tend to proliferate.

2. Why is any species at all extant? It is generally assumed that natural selection winnows out the lucky few, but does this idea suffice for passive filtering?

Though Dawkins is correct when he says that a particular mutation may be rather probable by being conditioned by the state of the organism (previous mutation), we must consider the entire chain of mutations represented by a species.

If we consider each species as representing a chain of mutations from the primeval organism, then we have a chain of conditional probability. A few probabilities may be high, but most are extremely low. Conditional probabilities can be graphed as trees of branching probabilities, so that a chain of mutation would be represented by one of these paths. We simply multiply each branch probability to get the total probability per path.

As a simple example, a 100-step conditional probability path with 10 probabilities of 0.9 and 60 with 0.7 and 30 with 0.5 yields a cumulative probability of 1.65 x 10^-19.

In other words, the more mutations and ancestral species attributed to an extanct species, the less likely it is to exist via passive natural selection. The actual numbers are so remote as to make natural selection by passive filtering virtually impossible, though perhaps we might conjecture some nonlinear effect going on among species that tends to overcome this problem.

Dawkins' algorithm demonstrating cumulative evolution fails to account for this difficulty. Though he realizes a better computer program would have modeled lifeform competition and adaptation to environmental factors, Dawkins says such a feat was beyond his capacities. However, had he programed in low probabilities for "positive mutations," cumulative evolution would have been very hard to demonstrate.

Our second problem is what led Hoyle to revive the panspermia conjecture, in which life and proto-life forms are thought to travel through space and spark earth's biosphere. His thinking was that spaceborne lifeforms rain down through the atmosphere and give new jolts to the degrading information structures of earth life. (The panspermia notion has received much serious attention in recent years, though Hoyle's conjectures remain outside the mainstream.)

From what I can gather, one of Dawkins' aims was to counter Hoyle's sharp criticisms. But Dawkins' vigorous defense of passive natural selection does not seem to square with the probabilities, a point made decades previously by J.B.S. Haldane.

Without entering into the intelligent design argument, we can suggest that the implausible probabilities might be addressed by a neo-Lamarkian mechanism of negative feedback adaptations. Perhaps a stress signal on a particular organ is received by a parent and the signal transmitted to the next generation. But the offspring's genes are only acted upon if the other parent transmits the signal. In other words, the offspring embryo would not strengthen an organ unless a particular stress signal reached a threshold.

If that be so, passive natural selection would still play a role, particularly with respect to body parts that lose their role as essential for survival.

Dawkins said Lamarkianism had been roundly disproved, but since the time he wrote the book molecular biology has shown the possibility of reversal of genetic information (retroviruses and reverse transcription). However, my real point here is not about Lamarkianism but about Dawkins' misleading mathematics and reasoning.

---

Joshua Mitteldorf, an evolutionary biologist with a physics background and a Dawkins critic, points out that an idea proposed more than 30 years ago by David Layzer is just recently beginning to gain ground as a response to the cumulative probabilities issue. Roughly I would style Layzer's proposal a form of neo-Lamarckianism. The citation3 is found at the bottom of this essay and the link is posted above.

---

On origins

Dawkins concedes that the primeval cell presents a difficult problem, the problem of the arch. If one is building an arch, one cannot build it incrementally stone by stone because at some point, a keystone must be inserted and this requires that the proto-arch be supported until the keystone is inserted. The complete arch cannot evolve incrementally. This of course is the essential point made by the few scientists who support intelligent design.

Dawkins essentially has no answer. He says that a previous lifeform, possibly silicon-based, could have acted as "scaffolding" for current lifeforms, the scaffolding having since vanished. Clearly, this simply pushes the problem back. Is he saying that the problem of the arch wouldn't apply to the previous incarnation of "life" (or something lifelike)?

Some might argue that there is a possible answer in the concept of phase shift, in which, at a threshold energy, a disorderly system suddenly becomes more orderly. However, this idea is left unaddressed in Watchmaker. I would suggest that we would need a sequence of phase shifts that would have a very low cumulative probability, though I hasten to add that I have insufficient data for a well-informed assessment.

Cosmic probabilities

Is the probability of life in the cosmos very high, as some think? Dawkins argues that it can't be all that high, at least for intelligent life, otherwise we would have picked up signals. I'm not sure this is valid reasoning, but I do accept his notion that if there are a billion life-prone planets in the cosmos and the probability of life emerging is a billion to one, then it is virtually certain to have originated somewhere in the cosmos.

Though Dawkins seems to have not accounted for the fact that much of the cosmos is forever beyond the range of any possible detection as well as the fact that time gets to be a tricky issue on cosmic scales, let us, for the sake of argument, grant that the population of planets extends to any time and anywhere, meaning it is possible life came and went elsewhere or hasn't arisen yet, but will, elsewhere.

Such a situation might answer the point made by Peter Ward and Donald Brownlee in Rare Earth: Why Complex Life Is Uncommon in the Universe (Springer 2000) that the geophysics undergirding the biosphere represents a highly complex system (and the authors make efforts to quantify the level of complexity), meaning that the probability of another such system is extremely remote. (Though the book was written before numerous discoveries concerning extrasolar planets, thus far their essential point has not been disproved. And the possibility of non-carbon-based life is not terribly likely because carbon valences permit high levels of complexity in their compounds.)

Now some may respond that it seems terrifically implausible that our planet just happens to be the one where the, say, one-in-a-billion event occurred. However, the fact that we are here to ask the question is perhaps sufficient answer to that worry. If it had to happen somewhere, here is as good a place as any. A more serious concern is the probability that intelligent life arises in the cosmos.

The formation of multicellular organisms is perhaps the essential "phase shift" required, in that central processors are needed to organize their activities. But what is the probability of this level of complexity? Obviously, in our case, the probability is one, but, otherwise, the numbers are unavailable, mostly because of the lack of a mathematically precise definition of "level of complexity" as applied to lifeforms.

Nevertheless, probabilities tend to point in the direction of cosmically absurd: there aren't anywhere near enough atoms -- let alone planets -- to make such probabilities workable. Supposing complexity to result from neutral mutations, probability of multicellular life would be far, far lower than for unicellular forms whose speciation is driven by natural selection. Also, what is the survival advantage of self-awareness, which most would consider an essential component of human-like intelligence?

Hoyle's most recent idea was that probabilities were increased by proto-life in comets that eventually reached earth. But, despite enormous efforts to resolve the arch problem (or the "jumbo jet problem"), in my estimate he did not do so.

(Interestingly, Dawkins argues that people are attracted to the idea of intelligent design because modern engineers continually improve machinery designs, giving a seemingly striking analogy to evolution. Something that he doesn't seem to really appreciate is that every lifeform may be characterized as a negative-feedback controlled machine, which converts energy into work and obeys the second law of thermodynamics. That's quite an "arch.")

The intelligent design proponents, however, face a difficulty when relying on the arch analogy: the possibility of undecidability. As the work of Godel, Church, Turing and Post shows, some theorems cannot be proved by tracking back to axioms. They are undecidable. If we had a complete physical description of the primeval cell, we could encode that description as a "theorem." But, that doesn't mean we could track back to the axioms to determine how it emerged. If the "theorem" were undecidable, we would know it to be "true" (having the cell description in all detail), but we might be forever frustrated in trying to determine how it came to exist.

In other words, a probabilistic argument is not necessarily applicable.

The problem of sentience

Watchmaker does not examine the issue of emergence of human intelligence, other than as a matter of level of complexity.

Hoyle noted in The Intelligent Universe (Holt, Rhinehart and Winston 1984) that over a century ago, Alfred Russel Wallace was perplexed by the observation that "the outstanding talents of man... simply cannot be explained in terms of natural selection."

Hoyle quotes the Japanese biologist S. Ohno:

"Did the genome (genetic material) of our cave-dwelling predecessors contain a set or sets of genes which enable modern man to compose music of infinite complexity and write novels with profound meaning? One is compelled to give an affirmative answer...It looks as though the early Homo was already provided with the intellectual potential which was in great excess of what was needed to cope with the environment of his time."

Hoyle proposes in Intelligent that viruses are responsible for evolution, accounting for mounting complexity over time. However, this seems hard to square with the point just made that such complexity doesn't seem to occur as a result of passive natural winnowing and so there would be no selective "force" favoring its proliferation.

At any rate, I suppose that we may assume that Dawkins in Watchmaker saw the complexity inherent in human intelligence as most likely to be a consequence of neutral mutations.

Another issue not addressed by Dawkins (or Hoyle for that matter) is the question of self-awareness. Usually the mechanists see self-awareness as an epiphenomenon of a highly complex program (a notion Roger Penrose struggled to come to terms with in The Emperor's New Mind (Oxford 1986) and Shadows of the Mind (Oxford 1994).)

But let us think of robots. Isn't it possible in principle to design robots that multiply replications and maintain homeostasis until they replicate? Isn't it possible in principle to build in programs meant to increase probability of successful replication as environmental factors shift?

In fact, isn't it possible in principle to design a robot that emulates human behaviors quite well? (Certain babysitter robots are even now posing ethics concerns as to an infant's bonding with them.)

And yet there seems to be no necessity for self-awareness in such designs. Similarly, what would be the survival advantage of self-awareness for a species?

I don't suggest that some biologists haven't proposed interesting ideas for answering such questions. My point is that Watchmaker omits much, making the computer razzle dazzle that much more irrelevant.

Conclusion

In his autobiographical What Mad Pursuit (Basic Books 1988) written when he was about 70, Nobelist Francis Crick expresses enthusiasm for Dawkins' argument against intelligent design, citing with admiration the "methinks" program.

Crick, who trained as a physicist and was also a panspermia advocate (see link above), doesn't seem to have noticed the difference in issues here. If we are talking about an analog of the origin of life (one-step arrival at the "methinks" sentence), then we must go with a distinct probability of 8.3 x 10^-41. If we are talking about an analog of some evolutionary algorithm, then we can be convinced that complex results can occur with application of simple iterative rules (though, again, the probabilities don't favor passive natural selection).

One can only suppose that Crick, so anxious to uphold his lifelong vision of atheism, leaped on Dawkins' argument without sufficient criticality. On the other hand, one must accept that there is a possibility his analytic powers had waned.

At any rate, it seems fair to say that the theory of evolution is far from being a clear-cut theory, in the manner of Einstein's theory of relativity. There are a number of difficulties and a great deal of disagreement as to how the evolutionary process works. This doesn't mean there is no such process, but it does mean one should listen to mechanists like Dawkins with care.

******************

1. In a 1996 introduction to Watchmaker, Dawkins wrote that "I can find no major thesis in these chapters that I would withdraw, nothing to justify the catharsis of a good recant."  2. My analogy was inadequately posed in previous drafts. Hopefully, it makes more sense now.  3. Genetic Variation and Progressive Evolution David Layzer The American Naturalist Vol. 115, No. 6 (Jun., 1980), pp. 809-826 (article consists of 18 pages) Published by: The University of Chicago Press for The American Society of Naturalists Stable URL: http://www.jstor.org/stable/2460802

Note: An early draft contained a ridiculous mathematical error that does not affect the argument but was very embarrassing. Naturally, I didn't think of it until after I was walking outdoors miles from an internet terminal. It has now been put right.