The axiom of choice

and non-enumerable reals

Plato and Cantor vs. Wittgenstein and Brouwer
Thoughts on diagonal reals
Eric Schechter's page on the Axiom of Choice (plenty of links)

[Posted online March 13, 2002; revised July 30, 2002, Aug. 28, 2002, Oct. 12, 2002, Oct. 24, 2002; June 2003]

The following proposition is presented for purposes of discussion. I agree that, according to standard Zermelo-Fraenkel set theory, the proposition is false.

Proposition: The Zermelo-Fraenkel power set axiom and the axiom of choice are inconsistent if an extended language is not used to express all the reals.

Discussion:

The power set axiom reads: 'Given any set X there is a set Y which has as its members all the subsets of X.' The axiom of choice reads: 'For any nonempty set X there is a set Y which has precisely one element in common with set X.'*

---

*Definitions taken from 'Logic for Mathematicians,' A.G. Hamilton, Cambridge, revised 1988.

---

It is known that there is a denumerable set X of writable functions f such that f defines r e R, where R is the nondenumerable set of reals. By writable, we mean f can be written in a language L that has a finite set of operations on a finite set of symbols. In other words, X contains all computable reals.

[This theorem stems from the thought that any algorithm for computing a number can be encoded as a single unique number. So, it is argued, since the set of algorithms is denumerable, so is the set of computable reals. However, we must be cautious here. It is possible for a brouwerian choice rule (perhaps using a random number generator) to compute more than one real.]

X is disjoint from a nondenumerable set Y, subset of R, that contains all noncomputable and hence non-enumerable reals.

P(Y) contains all the subsets of Y, and, like Y, is a nondenumerable infinity. Yet y e Y is not further definable. We cannot distinguish between elements of Y since they cannot be ordered, or even written. Hence, we cannot identify a 'choice' set Z that contains one element from every set in P(Y).

[However, it is important to note that some non-enumerables can be approximated as explicit rationals to any degree of accuracy in a finite number of steps, though such numbers are not Turing computable. See 'Thoughts on diagonal reals' above.]

Remark: It may be that an extended language L' could resolve this apparent inconsistency.

The basic criticism from two mathematicians is that merely because a choice set Z cannot be explicitly identified by individual elements does not prevent it from existing axiomatically.

Dan Velleman, an Amherst logician, remarked: 'But the axiom of choice does not say that 'we can form' [I later replaced 'form' with 'identify'] a choice set. It simply says that the choice set exists. Most people interpret AC as asserting the existence of certain sets that we cannot explicitly define.'

My response is that we are then faced with the meaning of 'one' in the phrase 'one element in common.' The word 'one' doesn't appear to have a graspable meaning for the set Z. Clearly, the routine meaning of 'choice' is inapplicable, there being nothing that can be selected. The set Z must be construed as an abstract ideal that is analogous to the concept of infinitesimal quantity, which is curious since set theory arose as an answer to the philosophical objection to such entities.

It is amusing to consider two types of vacuous truth (using '$' for the universal quantifier and '#' for the existential quantifier):

I. $w e W Fw & W = { }.

II. Consider the countable set X containing all computable reals and the noncountable set Y containing all noncomputable reals.

The statement

$r e R Fr --> $y e Y Fy

even though no y e Y can be specified from information given in Y's definition.

That is, I. is vacuously true because W contains no elements, whereas II. is vacuously true because Y contains no elements specified by Y's definition.

It is just the set Y that the intuitionist opposes, of course. Rather than become overly troubled by the philosophy of

existence

, it may be useful to limit ourselves to specifiability, which essentially means the ability to pair an element with a natural number.

Those numbers in turn can be paired with a successor function, such as S...S(O).

We should here consider the issue of transitivity, whereby the intuitionist admits to

A --> {A}

but does not accept A --> {{A}}

without first specifying, defining or expressing {A}.

That is, the intuitionist says

A --> {{A}} only if {{A}} --> {A}, which is only true if {A} has been specified, which essentially means paired with n e N.

In their book, Philosophies of Mathematics (Blackwell, 2002), Alexander George and Velleman offer a deliberately weak proof of the theorem that says that every infinite set has a denumerable subset:

'Proof: Suppose A is an infinite set. Then A is certainly not the empty set, so we can choose an element a₀ e A. Since A is infinite, A =/= {a₀}, so we can choose some a₁ e A such that a₁ =/= a₀. Similarly, A =/= {a₀,a₁}, so we can choose a₂ e A such that a₂ =/= a₀ and a₂ =/= a₁. Continuing in this way, we can recursively choose a_n e A such that a_n ~e {a₀,a₁,...,a_n-1}. Now let R = {<0,a₀>, <1,a₁>, <2,a₂>...} . Then R is a one-to-one correspondence between N and the set {a₀,a₁,a₂...}, which is a subset of A. Therefore, A has a denumerable subset.'

The writers add, 'Although this proof seems convincing, it cannot be formalized using the set theory axioms that we have listed so far. The axioms we have discussed guarantee the existence of sets that are explicitly specified in various ways -- for example, as the set of all subsets of some set (Axiom of Power Sets), or as the set of all elements of some set that have a particular property (Axiom of Comprehension). But the proof of [the theorem above] does not specify the one-to-one correspondence R completely, because it does not specify how the choices of the elements a₀,a₁,a₂... are to be made. To justify the steps in the proof, we need an axiom guaranteeing the existence of sets that result from such arbitrary choices:'

The writers give their version of the axiom of choice:

'Axiom of choice. Suppose F is a set of sets such that Æ =/= F. Then there is a function C with domain F such that, for every X e F, C(X) e X.'

They add, 'The function C is called a choice function because it can be thought of as choosing one element C(X) from each X e F.'

The theorem cited seems to require an abstracted construction algorithm. However, how does one select a₀,a₁,a₂... if the elements of Y are individually nondefinable? AC now must be used to justify counting elements that can't be identified. So now AC is used to assert a denumerable subset by justifying a construction algorithm that can, in principle, never be performed.

Suppose we define a real as an equivalence class of cauchy sequences. If [{a_n}] e X, then [{a_n}] is computable and orderable. By computable, we mean that there is some rule for determining, in a finite number of steps, the exact rational value of any term a_n and that this rule must always yield the same value for a_n.

A brouwerian choice sequence fails to assure that a_n has the same value on every computation, even though {a_n} is cauchy. Such numbers are defined here as 'non-computable,' though perhaps 'non-replicable' is a better characterization. A brouwerian cauchy sequence {a_n}, though defined, is not orderable since, in effect, only a probability can be assigned to its ordering between 1/p and 1/q.

Now we are required by AC to say that either {a_n} is equivalent to {b_n} and hence that [{a_n}] = [{b_n}] or that the two sequences are not equivalent and that the two numbers are not equal.

Yet, a brouwerian choice sequence defines a subset W of Y, whereby the elements of W cannot be distinguished in a finite number of steps. Yet AC says that the trichotomy law applies to w₁ and w₂.

We should note that W may contain members that coincide with some x e X. For example, we cannot rule out that a random-number generator might produce all the digits in pi.

In a 1993 Philosophical Review article, Constructivism liberalized Velleman defends the notion that only denumerable sets qualify as actual infinities. In that case, AC would, I suppose, not apply to a nondenumerable set X since the choice function could only apply to a denumerable subset of X. One can't apply the choice function to something that doesn't exist.

Essentially, Velleman 1993 is convinced that Cantor's reducto ad absurdum proof of nondenumerability of the reals should be interpreted: 'If a set of all reals exists, that set cannot be countable.' By this, we avoid the trap of assuming, without definition, that a set of all reals exists.

He writes that 'to admit the existence of completely unspecifiable reals would violate our principle that if we want to treat real numbers as individuals, it is up to us to individuate them.'

'As long as we maintain this principle, we cannot accept the classical mathematician's claim that there are uncountably many completely unspecifiable real numbers. Rather, the natural conclusion to draw from Cantor's proof seems to be that any scheme for specifying reals can be extended to a more inclusive one, and therefore the reals form an indefinitely extensible totality.'

He favors use of intuitionist logic for nondenumerable entities while retaining classical logic for denumerable sets.

'The arguments of the constructionists have shaken my faith in the classical treatment of real numbers, but not natural numbers,' Velleman 1993 writes in his sketching of a philisophical program he calls 'liberal constructivism.' Unlike strict constructivists, he accepts 'actual infinities,' but unlike classical mathematicians, he eschews uncountable totalities.

For example, he doubts that 'the power set operation, when applied to an infinite set, results in a well-defined totality.'

His point can be seen by considering the Cantorian set of reals. We again form the denumerable set X of all computable, and enumerable, reals and then write the complement set R-X. Now if we apply AC to R-X in order to form a subset Y, does it not seem that Y ought to be perforce denumerable, especially if we are assuming that Y may be constructed? That is, the function C(R-X) seems to require some type of instruction to obtain a relation uRv. If an instruction is required in order to pair u and v, then Y would be denumerable, the set of instructions being denumerable. But does not AC imply that no instruction is required?

Of course, we can then write (R-X)-Y to obtain a nondenumerable subset of R.

We can think of two versions of AC¹: the countable version and the noncountable. In the countable version, AC says that it is possible to select one element from every set in a countable collection of sets. In the noncountable version, AC says that the choice function may be applied to a nondenumerable collection of sets.

In strong AC, we must think of the elements being chosen en masse, rather than in a step-by-step process.

The wildness implicit in AC is further shown by the use of a non-formulaic function to pair noncomputables in Y with noncomputables in a subset of Y, as in f:Y->Y. That is, suppose we take all the noncomputables in the interval (0,1/2) and pair each with one noncomputable in (1/2,1), without specifying a means of pairing, via formula or algorithm. Since we can do the same for every other noncomputable in (1/2,1), we know there exists a nondenumerable set of functions pairing noncomputables.

This is strange. We have shown that there is a nondenumerable set of nonformulaic functions to pair non-individuated members of domY with a non-individuated member of ranY. If x e domY, we say that x varies, even though it is impossible to say how it varies. If y_o e ranY, we can't do more than approximate it on the real line. We manipulate quantities that we can't grasp. They exist courtesy of AC alone.

In an August 2002 email, Velleman said that though still attracted to this modified intuitionism, he is not committed to a particular philosophy.

Jim Conant, a Cornell topologist, commented that the reason my exposition is not considered to imply a paradox is that 'the axioms of set theory merely assert existence of sets and never assert that sets can be constructed explicitly.' The choice axiom 'in particular is notorious for producing wild sets that can never be explicitly nailed down.'

He adds, 'A platonist would say that it is a problem of perception: these wild sets are out there but we can never perceive them fully since we are hampered by a denumerable language. Others would question the meaning of such a statement.'

Also, the ZF axioms are consistent only if the ZF axioms + AC are consistent, he notes, adding that 'nobody knows whether the ZF axioms are consistent.' (In fact, his former adviser, topologist Mike Freedman, believes there are ZF inconsistencies 'so complicated' that they have yet to be found.)

'Therefore I take the point of view that the axiom of choice is simply a useful tool for proving down to earth things.'

Yet it is hard to conceive of Y or P(Y)\Y as 'down to earth.' For example, because Y contains real numbers, they are axiomatically 'on' the real number line. Yet no element of Y can be located on that line. y is a number without a home.

[See the 'Plato' link above.]

---

Note added in April 2006: Since arithmetic can be encoded in ZFC, we know from Kurt Godel that ZFC is either inconsistent or incomplete. That is, there is at least one true statement in ZFC that cannot be proved from axioms or ZFC contains a contradiction.

We also know that ZFC is incomplete in the sense that the continuum hypothesis can be expressed in ZFC, its truth status is independent of ZFC axioms, as Godel and Paul Cohen have shown.

---

1. Jim Conant brought this possibility to my attention.

An algorithm for implying all reals

Thoughts on diagonalization

• An algorithm for constructing the reals
• Approximating some non-enumerable reals with rationals
• Extending the concept of non-denumerability
• Does the set of choice sequences contain a non-enumerable limit?
• Have algorithm, will travel (sets of optimal graphs)

Thoughts on the axiom of choice
Constructing non-denumerable sets 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 construct 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.

Time thought experiments

Godel's theorem and a time travel paradox

In How to Build a Time Machine (Viking 2001), the physicist Paul Davies gives the 'most baffling of all time paradoxes.' Writes Davies:

'A professor builds a time machine in 2005 and decides to go forward ... to 2010. When he arrives, he seeks out the university library and browses through the current journals. In the mathematics section he notices a splendid new theorem and jots down the details. Then he returns to 2005, summons a clever student, and outlines the theorem. The student goes away, tidies up the argument, writes a paper, and publishes it in a mathematics journal. It was, of course, in this very journal that the professor read the paper in 2010.'

Davies finds that, from a physics standpoint, such a 'self-consistent causal loop' is possible, but, 'where exactly did the theorem come from?... it's as if the information about the theorem just came out of thin air.'

Davies says many worlds proponent David Deutsch, author of The Fabric of Reality and a time travel 'expert,' finds this paradox exceptionally disturbing, since information appears from nowhere, in apparent violation of the principle of entropy.

This paradox seems well suited to Godel's main incompleteness theorem, which says that a sufficiently rich formal system if consistent, must be incomplete.

Suppose we assume that there is a formal system T -- a theory of physics -- in which a sentence S can be constructed describing the mentioned time travel paradox.

If S strikes us as paradoxical, then we may regard S as the Godel sentence of T. Assuming that T is a consistent theory, we would then require that some extension of T be constructed. An extension might, for example, say that the theorem's origin is relative to the observer and include a censorship, as occurs in other light-related phenomena. That is, the professor might be required to forget where he got the ideas to feed his student.

But, even if S is made consistent, there must then be some other sentence S', which is not derivable from T'.

Of course, if T incorporates the many worlds view, S would likely be consistent and derivable from T. However, assuming T is a sufficiently vigorous mathematical formalism, there must still be some other sentence V that may be viewed as paradoxical (inconsistent) if T is viewed as airtight.

How old is a black hole?

Certainly less than the age of the cosmos, you say.

The black hole relativistic time problem illustrates that the age of the cosmos is determined by the yardstick used.

Suppose we posit a pulsar pulsing at the rate T, and distance D from the event horizon of a black hole. Our clock is timed to strike at T/2, so that pulse A has occurred at T=0. We now move the pulsar closer to the event horizon, again with our clock striking at what we'll call T'/2. Now because of the gravitational effect on observed time, the time between pulses is longer. That is T' > T, and hence T'=0 is farther in the past than T=0.

Of course, as we push the pulsar closer to the event horizon, the relative time T^N becomes asymptotic to infinity (eternity). So, supposing the universe was born 15 billion years ago in the big bang, we can push our pulsar's pulse A back in time beyond 15 billion years ago by pushing the pulsar closer to the event horizon.

No matter how old we make the universe, we may always obtain a pulse A that is older than the cosmos.

Yes, you say, but a real pulsar would be ripped to shreds and such a happening is not observable. Nevetherless, the general theory of relativity requires that we grant that time calculations can yield such contradictions.

Anthropic issues

A sense of awe often accompanies the observation: 'The conditions for human (or any) life are vastly improbable in the cosmic scheme of things.'

This leads some to assert that the many worlds scenario answers that striking improbability, since in most other universes, life never arose and never will.

I point out that the capacity for the human mind to examine the cosmos is perhaps 2.5 x 10⁴ years old, against a cosmic time scale of 1.5 x 10⁹. In other words, we have a ratio of 2.5(10⁴)/1.5(10⁹) = 1.6/10⁵.

In other words, humanity is an almost invisible drop in the vast sea of cosmic events.

Yet here we are! Isn't that amazing?! It seems as though the cosmos conspired to make our little culture just for us, so we could contemplate its vast mysteries.

However, there is the problem of the constants of nature. Even slight differences in these constants would, it seems, lead to universes where complexity just doesn't happen. Suppose that these constants depend on initial cosmic conditions which have a built-in random variability. In that case, the existence of a universe with just the right constants for life (in particular, humanity) to evolve is nothing short of miraculously improbable. Some hope a grand unified theory will resolve the issue. Others suggest that there is a host of bubble universes, most of which are not conducive to complexity, and hence the issue of improbability is removed (after all, we wouldn't be in one of the barren cosmoses). For more on this issue, see the physicist-writers John Barrow, Frank Tipler and Paul Davies.

At any rate, it doesn't seem likely that this drop will last long, in terms of cosmic scales, and the same holds for other such tiny drops elsewhere in the cosmos.

Even granting faster-than-light 'tachyon radio,' the probability is very low that an alien civilization exists within communications range of our ephemeral race. That is, the chance of two such drops existing 'simultaneously' is rather low, despite the fond hopes of the SETI crowd.

On the other hand, Tipler favors the idea that once intelligent life has evolved, it will find the means to continue on forever.

Anyway, anthropomorphism does seem to enter into the picture when we consider quantum phenomena: a person's physical reality is influenced by his or her choices.

First published Friday, October 20, 2006

On infinitely long statements

This note addresses a point I raised elsewhere: Is there a set of noncomputable but grammatical strings that are inherently impossible to cryptanalyze?

Again, we are assigning a digit to each symbol in some logic language (agreeing to first make sure we start out with a sufficiently high base number system). A string of digits then represents a string of symbols.

A grammatical string of symbols is one whereby certain substrings are barred as ungrammatical. But this does not mean we rule out logical contradictions or "false" statements. For example the string (A and not-A) is permitted. However, we see that the set of all proofs (defining proof as a statement verifying another statement) is a subset of our set of grammatical strings.

Whether an infinitely long grammatical string represents a proof, or a true or false, or undecidable, statement is a matter of philosophical preference.

But, to the matter at hand:

Can an infinitely long string be noncomputable but grammatical? The answer depends on the "reasonableness" of the grammatical rules. Note that in routine first-order logic notation our biggest concerns as to grammar are the right and left parentheses. If we had a set of 30 symbols, we would still have nearly 28 random choices for step n+1. So let's be generous and suggest that for language L, half the symbol set is disallowed.

[Note: I have been told that there is a proof that some such strings are satisfiable (have a truth value) and that others are undecidable.]

Now, using Zermelo-Frankel set theory's infinity axiom to permit use of induction, we consider the set of all n-length strings of base K digits (there are K^n strings).
By induction we see that we obtain the set of all possible strings, and this must be bijective with the set of reals.

Now suppose we add the proviso that at any n, we permit only (K^n)/2 strings. Yet by the ZF infinity axiom and induction we obtain half the reals, which is still a nondenumerable infinity. Since the computables have a denumerable cardinality, there must be a nondenumerable set of noncomputable but grammatical strings.

However, for grammatical rules that increasingly limit the number of choices for n, this theorem is not valid.

Related pages by Conant:
http://www.angelfire.com/az3/nfold/diag.html
http://www.angelfire.com/az3/nfold/choice.html
http://www.angelfire.com/az3/nfold/qcomp.html

First published Thursday, October 12, 2006

Information theory and intelligent design

Draft 3

Before his trail-blazing paper on information theory (or "communication theory"), Claude Shannon wrote a confidential precursor paper during World War II on the informational and transmission issues inherent in cryptography, an indication of how closely intertwined are information theory and cryptology.

In this post, we digress from cryptology a bit to approach the issue of "meaning" in information theory, an issue Shannon quite properly avoided by ignoring it. We are going to avoid the philosophical depths of "meaning" also while addressing a continuing concern, the fact that some information is more useful or compelling or relevant than other information. We might think of Shannon's work as a complete generalization of communicative information, whereas our idea is to draw some distinctions. (I have only a modest familiarity with information theory and so I have no idea of whether any of what follows is original.)

For convenience we limit ourselves to the lower case alphabet and assign equal probability to the occurrence of letters in a letter string. We also use the artificially short string n=4. In that case, the Shannon information content of the gibberish string abbx equals 18.8 bit. The Shannon information value of the word goal is likewise 18.8 bit.

Now we ask the probability that a four-letter string is an English word. Let us suppose there are 3,000 four-letter English words (I haven't checked). In that case, the probability that a string belongs to the set of English words would be 3000/26^4, or 0.0065, which we now characterize as equivalent to a structured information content of 0.0095 bit. Of course, the alphabet provides the primary (axiomatic?) structure. In this case, an English dictionary provides the secondary structure.

The number of gibberish strings is then 1-0.00656, or 0.9934, which we say is equivalent to a structured information content of 0.0095 bit. We see that these values are closer to our intuitive notion of information and also fits well with the Shannonist notion that a piece of information carries a surprisal value.

Here we say that we are not particularly surprised at the string abbx because it is a member of a lawless set and because background noise is, in many circumstances, ubiquitous. We say that for our purposes the information value of any member of the lawless set is identical with the information value of the set, as is the case for any member of the structured set and the structured set. On the other hand, the surprisal value of the string goal is fairly high because of the likelihood that it was not generated randomly and hence stems from a structured or designed set. That is, the chances are fairly good that a mind originated the string goal but the chances that a mind originated a string such as abbx are harder to determine. Clearly, our confidence tends to increase with length of string and with the number of set rules.

We see how our concept of structured information fits well with cryptography, though we will not dwell on that here.

Another way to deal with the structure issue here is to ignore the gibberish strings and simply say that goal has a probability of (say) 1/3000, with an equivalent information content of 11.55 bit.

What we are doing here is getting at a principle. We are not bothering to assign exact probabilities to individual letters, letter pairs, letter triplets or letter quadruplets. We are not assigning an empirical frequency to the word goal.
Rather, what we are doing, is closing on the problem of assigning an alternative information value to patterns that show a specified structure.

Above, we have used a streamlined alphabet. But a set of some logic language's symbols can be treated like an alphabet. Importantly, we assign only grammatical symbol strings to the structured set, using rules such as ")" cannot be used to begin a sentence. We can then use the process sketched above to assign a structured information value to any string.

Clearly this method can be used for all sorts of sets divided into lawless and lawful subsets, where "law" is a pairing rule or relation. (For example, by this, we could arrange that a non-computable irrational number have a much lower information value than a computable irrational.)

We see that the average information of a gibberish string (as defined via the structured set) is far less than that of the string matching elements of the structured set. For example, the string abbx rsr is a member of the gibberish set and gibberish, in this case (assuming as a wild guess 5,000 three-letter English words) has a probability of 1-(3,000/26^4) + 1-(5,000/26^3), for an information average of 0.4925 bit. Compare the string goal new (disregarding word order), which has the complementary probability, with an information average of 50 bit.

Hence, if one saw the message goal new one could have a strong degree of confidence that the string was not random but stemmed from a designed set.

A design inference?
William Dembski, the scholar who advocates a rational basis for inferring design by intelligence, uses the SETI example to buttress his cause. The hunters of extraterrestrial intelligence, in a fictional account, are astounded by a sequence of radioed 'zeroes and ones' that matches the prime number sequence for the first 100 primes. One must assume that such a low entropy (and high average information) content must be by design, he says, and uses that as a basis for justifying the inference of an intelligent designer behind the creation of life.

However, it should be noted that it seems imperative that in order to have a set of low entropy elements, there must be a human mind to organize that set (not the physical aspects, but the cognitively appreciated set). So, such a bizarre signal from the stars would be recognized as other than background noise because of a centuries-long human effort to distill certain mathematical relations into concise form. Hence, human receivers would recognize a similar intelligence behind the message.

But does that mean one can detect a signal from amid noise without falling into the problem whereby one sees all sorts of "things" in an atmospheric cloud?
That is, when one says that the formation of the first life forms is highly improbable, what does one mean? Can we be sure that the designer set (using human assumptions) has been sufficiently defined? (I am not taking sides here, by the way.)

However, as noted above, the question of computability enters the picture here. Following prevailing scientific opinion (Penrose being an exception), every organism
can be viewed as a machine and every machine responds to a set of algorithms. Hence every machine can be assigned a unique and computable number. One simply assigns numbers to each element of the logic language in use and puts together an algorithm for the machine. The machine's integer number corresponds to some right-left or left-right sequence of symbols (to avoid confusion, the computation may require a high-base number system).

So then, the first organic machines -- proto-cell organisms perhaps -- must be regarded as part of a larger machine, the largest machine of all being the cosmos. But, the cosmos cannot be modeled as a classical machine or computer. See link in sidebar.

A sea of unknowable 'designs'
Also, the set of algorithmic machines (the set of algorithms) is bijective with a subset of the computable reals (some algorithmic substrings are disallowed on grammatical grounds).

Now a way to possibly obtain a noncomputable real is to use a random lottery for choice of the nth digit in the string and, notionally, to continue this process over denumerable infinity. Because the string is completely random we do not know whether it is a member of the computable or noncomputable reals (which set, following Cantor's diagonal proof and other proofs, has a higher infinite cardinality than the set of computable reals).

So there is no reason to conclude that a grammatical string might not be a member of the noncomputables. In fact, there must be a nondenumerable infinity of such strings.
Nevertheless, a machine algorithm is normally defined as always finite. On the other hand, one could imagine that a machine with an eternal time frame might have an infinite-step algorithm.

That is, what we have arrived at is the potential for machine algorithms that cannot possibly have been arrived at by human ken. Specifically, we have shown that there exists a nondenumerable infinity of grammatical statements of infinite length. One might then argue that there is a vast sea of infinite designs that the human mind cannot apprehend.

First published Wednesday, November 01, 2006

Does math back 'intelligent design'?

Two of the main arguments favoring "intelligent design" of basic biotic machines:

. Mathematician William A. Dembski (Science and Evidence for Design in the Universe) says that if a pattern is found to have an extraordinarily low probability of random occurrence -- variously 10^(-40) to 10^(-150) -- then it is reasonable to infer design by a conscious mind. He points out that forensics investigators typically employ such a standard, though heuristically.

. Biochemist Stephen C. Meyer (Darwin's Black Box) says that a machine is irreducibly complex if some parts are interdependent. Before discussing intricate biological mechanisms, he cites a mousetrap as a machine composed of interdependent parts that could not reasonably be supposed to fall together randomly.

Meyer is aware of the work of Stuart Kauffman, but dismisses it because Kauffman does not deal with biological specifics. Kauffman's concept of self-organization via autocatalysis however lays the beginnings of a mathematical model demonstrating how systems can evolve toward complexity, including sudden phase transitions from one state -- which we might perceive as "primitive" -- to another state -- which we might perceive as "higher." (Like the word "complexity," the term "self-organization" is sometimes used rather loosely; I hope to write something on this soon.)

Kauffman's thinking reflects the work of Ilya Prigogine who made the reasonable point that systems far from equilibrium might sometimes become more sophisticated before degenerating in accordance with the "law of entropy."

This is not to say that Meyer's examples of "irreducible complexity" -- including cells propelled by the cilium "oar" and the extraordinarily complex basis of blood-clotting -- have been adequately dealt with by the strict materialists who sincerely believe that the human mind is within reach of grasping the essence of how the universe works via the elucidation of some basic rules.

One such scientist is Stephen Wolfram whose New Kind of Science examines "complexity" via iterative cellular automaton graphs. He dreams that the CA concept could lead to such a breakthrough. (But I argue that his hope, unless modified, is vain; see sidebar link on Turing machines.)

Like Kauffman, Wolfram is a renegade on evolution theory and argues that his studies of cellular atomata indicate that constraints -- and specifically the principle of natural selection -- have little impact on development of order or complexity. Complexity, he finds, is a normal outcome of even "simple" sets of instructions, especially when initial conditions are selected at random.

Thus, he is not surprised that complex biological organisms might be a consequence of some simple program. And he makes a convincing case that some forms found in nature, such as fauna pigmentation patterns, are very close to patterns found according to one or another of his cellular automatons.

However, though he discusses n-dimensional automata, the findings are sketchy (the combinatorial complexity is far out of computer range) and so cannot give a three-dimensional example of a complex dynamical system emerging gestalt-like from some simple algorithm.

Nevertheless, Wolfram's basic point is strong: complexity (highly ordered patterns) can emerge from simple rules recursively applied.

Another of his claims, which I have not examined in detail, is that at least one of his CA experiments produced a graph, which, after sufficient iterations, statistically replicated a random graph. That is, when parts of the graph were sampled, the outcome was statistically indistinguishable from a graph generated by computerized randomization. This claim isn't airtight, and analysis of specific cases needs to be done, but it indicates the possibility that some structures are somewhat more probable than a statistical sampling would indicate. However, this possibility is no disproof of Dembski's approach. (By the way, Wolfram implicitly argues that "pseudorandom" functions refer to a specific class of generators that his software Mathematica avoids when generating "random" numbers. Presumably, he thinks his particular CA does not fall into such a "pseudorandom" set, despite its being fully deterministic.)

However, Wolfram also makes a very plausible case (I don't say proof because I have not examined the claim at that level of detail) that his cellular automata can be converted into logic languages, including ones that are sufficiently rich for Godel's incompleteness theorem to apply.

As I understand Godel's proof, he has demonstrated that, if a system is logically consistent, then there is a class of statements that cannot be derived from axioms. He did this through an encipherment system that permits self-referencing and so some have taken his proof to refer only to an irrelevant semantical issue of self-referencing (akin to Russell's paradox). But my take is that the proof says that statements exist that cannot be proved or derived.

So, in that case, if we model a microbiotic machine as a statement in some logic system, we see immediately that it could be a statement of the Godel type, meaning that the statement holds but cannot be derived from any rules specifying the evolution of biological systems. If such a statement indeed were found to be unprovable, then many would be inclined to infer that the machine specified by this unprovable statement must have been designed by a conscious mind. However, such an inference is a philosophical (which does not mean trival) difficulty.

First published Thursday, November 02, 2006

Pseudorandom thoughts on complexity

Draft 2


This post supplements the previous post "Does math back 'intelligent design'?"

With respect to the general concept of evolution, or simply change over time, what do we mean by complexity?

Consider Stephen Wolfram's cellular automata graphs. We might think of complexity as a measure of the entropy of the graph, which evolves row by row from an initial rule whereby change occurs only locally, in minimal sets of contiguous cells. Taken in totality, or after some row n, the graphs register different quantities of entropy. That is, "more complex" graphs convey higher average information than "less complex" ones. Some graphs become all black or all white after some row n, corresponding to 0 information after that row. There exists a significant set of graphs that achieve neither maximum nor minimum entropy, of course.

How would we define information in a Wolfram cellular automaton graph? We can use several criteria. A row would have maximum entropy if the probability of the pattern of sequential cell colors is indistinguishable from random coloring. [To be fussy, we might use a double-slit single photon detector to create a random sequence whereby a color chosen for a cell is a function of the number of the quadrant where a photon is detected at time t.]

Similarly for a column.

Obviously, we can consider both column and row. And, we might also consider sets of rows and-or columns that occur as a simple period. Another possibility is to determine whether such sets recur in "smooth curve quasi-periods" such as every n^2. We may also want to know whether such sets zero out at some finite row.

Another consideration is the appearance of "structures" over a two-dimensional region. This effectively means the visual perception of at least one border, whether closed or open. The border can display various levels of fuzziness. A linear feature implies at least one coloration period (cycle) appearing in every mth row or every nth column. The brain, in a Gestalt effect, collates the information in these periods as a "noteworthy structure." Such a structure may be defined geometrically or topologically (with constraints). That is, the periodic behavior may yield a sequence of congruent forms (that proliferate either symmetrically or asymmetrically) or of similar forms (as in "nested structures"), or of a set of forms each of which differs from the next incrementally by interior angle, creating the illusion of morphological change, as in cartoon animation.

At this juncture we should point out that there are only 254 elementary cellular automata. However, the number of CA goes up exponentially with another color or two and when all possible initial conditions are considered.

So what we are describing, with the aid of Wolfram's graphs, is deterministic complexity, which differs from the concept of chaos more on a philosophical plane than a mathematical one.

We see that, depending on criteria chosen, CA graphs, after an evolution of n steps, differ in their maximum entropy and also differ at the infinite limit in their maximum entropy. Each graph is asymptotic toward some entropy quantity. By no means does every graph converge toward maximum entropy as defined by a truly random pattern.

So we may conclude that, as Wolfram argues, simple instructions can yield highly complex fields. The measure of complexity is simply the quantity of information in a a graph or subgraph defined by our basic criteria. And what do we mean in this context by information? If we went through all n steps of the rule and examined the sequence of colors in, for example, row n, the information content would be 0 because we have eliminated the uncertainty.

If, however, we don't examine how row n's sequence was formed, then we can check the probability of such a sequence with the resulting information value. At this point we must beware: Complete aperiodicity of cell colors in row n is NOT identical with maximum entropy of row n. Think of asking a high school student to simulate flipping of a coin by haphazardly writing down 0 or 1 in 100 steps. If one then submits the sequence to an analyst, he or she is very likely to discover that the sequence was not produced randomly because most people avoid typical sub-sequences such as 0 recurring six times consecutively.

So then, true randomness (again, we can use our quantum measuring device), which corresponds to maximum entropy, is very likely to differ significantly from computed chaos. This fact is easily seen if one realizes that the set of aperiodic computable irrational numbers is of a lower cardinality than the set of random digit sequences. Still, it must be said that the foregoing lemma doesn't mean there is always available a practical test to distinguish a pseudorandom sequence from a random sequence.

We might also think of deterministic complexity via curves over standard axes, with any number of orthogonal axes we like. Suppose we have a curve y = x. Because there is no difference between x and y, there is effectively no information in curve f(x). No work is required to determine f(x) from x. The information in y = 2x is low because minimal work (as counted by number of simple steps in the most efficient algorithm known) is required to determine g(x) from x. Somewhat more information is found for values of h(x) = x^2 because the computation is slightly slower.

A curve whose values hold maximum information -- implying the most work to arrive at an arbitrary value -- would be one whereby the best method of determining f(x+k) requires knowledge of the value f(x). Many recursive functions fit this category. In that case, we would say that a computed value whose computational work cannot be reduced from n steps of the recursive function or iterative algorithm holds maximum information (if we don't do the work).

So let's say we have the best-arranged sieve of Eratosthenes to produce the sequence of primes. On an xyz grid, we map this discrete curve z = f(y) over y = x^2, using only integer values of x. Now suppose we perceived this system in some other way. We might conclude that a chaotic system shows some underlying symmetry.

It is also possible to conceive of two maximally difficult functions mapped onto each other. But, there's a catch! There is no overall increase in complexity. That is, if f(x) is at maximum complexity, g(f(x)) cannot be more complex -- though it could conceivably be less so.

This conforms to Wolfram's observation that adding complexity to rules does little to increase the complexity of a CA.

Now what about the idea of "phase transitions" whereby order suddenly emerges from disorder? Various experiments with computer models of nonlinear differential equations seem to affirm such possibilities.

Wolfram's New Kind of Science shows several, as I call them, catastrophic phase transitions, whereby high entropy rapidly follows a "tipping point" as defined by a small number of rows. Obviously one's perspective is important. A (notional) graph with 10^100 iterations could have a "tipping point" composed of millions of rows.

Wolfram points out that minor aymmetries in a high entropy graph up to row n are very likely to amplify incrementally -- though the rate of change (which can be defined in several ways) can be quite rapid -- into a "complex" graph after row n. I estimate that these are low entropy graphs, again bearing in mind the difference between true randomness and deterministic chaos or complexity: the entropies in most cases differ.

What we arrive at is the strong suggestion -- that I have not completely verified -- that a high information content in a particular graph could easily be indicative of a simple local rule and does not necessarily imply an externally imposed design [or substitution by another rule] inserted at some row n.

However, as would be expected, the vast majority of Wolfram's graphs are high-entropy affairs -- no matter what criteria are used -- and this fact conforms to the anthropomorphic observation that the cosmos is en toto a low entropy configuration, in that most sets of the constants of physical law yield dull, lifeless universes.

I should note that New Kind of Science also analyzes the entropy issue, but with a different focus. In his discussion of entropy, Wolfram deploys graphs that are "reversible." That is, the rules are tweaked so that the graph mimics the behavior of reversible physical processes. He says that CA 37R shows that the trend of increasing entropy is not universal because the graph oscillates between higher and lower entropy eternally. However, one must be specific as to what information is being measured. If the entropy of the entire graph up to row n is measured, then the quantity can change with n. But the limiting value as n goes to infinity is a single number. It is true, of course, that this number can differ substantially from the limiting value entropy of another graph.

Also, even though the graphs display entropy, the entropy displayed by physical systems assumes energy conservation. But Wolfram's graphs do not model energy conservation, though I have toyed with ways in which they might.

The discussion above is all about classical models arranged discretely, an approach that appeals to the computer science crowd and to those who argue that quantum physics militates against continuous phenomena. However, I have deliberately avoided deep issues posed by the quantum measurement/interpretation problem that might raise questions as to the adequacy of any scientific theory for apprehending the deepest riddles of existence.

It should be noted that there is a wide range of literature on what the Santa Fe Institute calls "complexity science" and others sometimes call "emergence of order." I have not reviewed much of this material, though I am aware of some of the principle ideas.

A big hope for the spontaneous order faction is network theory, which shows some surprising features as to how orderly systems come about. However, I think that Wolfram graphs suffice to help elucidate important ideas, even though I have not concerned concerned myself here with New Kind of Science's points about networks and cellular automata.