Thursday, November 10, 2011
Plato and Cantor v. Wittgenstein and Brouwer
Pertinent N-fold pages
A geometric note on Russell's paradox
When algorithms collide
Disjoint nondenumerable sets of irrationals
Thoughts on the axiom of choice
Math resources on the web
An algorithm for implying the reals
Prove all things. Hold fast to that which is good.
--I Thes 5:21
[This page was begun in January 2002; as of Aug. 1, 2002, it remains a work in progress. Correction added Aug. 13, 2004, to include an inadvertently omitted "undecidable of the third kind."]
Integers and intuition
Without going into an extensive examination of phenomenology and the psychology of learning, perception and cognition, let us consider the mind of a child.Think of Mommy controlling a pile of lollipops and crayons, some of which are red. In this game, the child is encouraged to pick out the red objects and transfer them to 'his' pile.
The child employs a mental act of separation (some might call this 'intuition') to select out an item, in this case by direct awareness of the properties of redness and of ease of holding with his hands. This primal separation ability is necessary for the intuition of replication. Crayon and lollipop are 'the same' by virtue of redness. In turn, this intuition of replication, or iteration, requires a time sense, whereby if the child hears 'more' he associates the word with an expectation of a craving being satisfied ('more milk').
The child becomes able to associate name-numbers with iteration, such that 'one thing more for me' becomes 'one thing,' which in time is abstracted to 'one.' A sequence of pulses is not truly iterative, because there is no procedure for enumeration. The enumeration procedure is essentially a successor function, with names (integers) associated with each act of selection by replication intuition. Likewise, we must have amorphous 'piles' before we can have sets. As adults we know that the 'mine' pile and the 'Mommy' pile have specific, finite numbers of elements. But we cannot discern the logico-mathematical objects of set and element without first having a concept of counting.
That is, in the minds of small children and of adults of primitive cultures, integers are associated with intuitively replicable material objects, such as apples and oranges. But the names are so useful that it is possible to mentally drop the associated objects in a process of abstraction. That is, we might consider an integer to be quite similar in spirit to an 'operator.' Whatever objects are associated with operators, a common set of rules of manipulation applies to the operators alone.
Platonism vs. intuitionism
Cantor's acceptance of 'actual infinities' seems to me to require a platonic concept of ideals: forms or formalisms that count as existing a priori.The intuitionists, led by Brouwer and partially supported by Wittgenstein (and Kronecker before them), would object to a set or, possibly, a number that 'cannot be constructed. Related to this division is the dispute as to whether a theorem or mathematical form is discovered, as the platonists, see it, or invented, as the intuitionists see it.
I don't intend to inspect every wrinkle of these controversies but rather to focus on the concept of existence of mathematical statements and forms.
Forthwith, let's dismiss the concept of 'potential infinity' that was in vogue in the 19th century as a means of describing a successor operation. 'Potential' invokes the thought of 'empowered to achieve an end.' To say that 'potential infinity' is conceptually acceptable is to say that 'actual infinity' is also permissible.
Let us accept the Zermelo-Fraenkel successor set axiom as underpinning proof by induction and as underpinning open-ended successor functions, such as the function f(n) = n+1, which describes the natural numbers. This axiom is often known as the infinity axiom, but we are not, without further thought, entitled to take that leap. The successor axiom says that a recursion function needn't have a specific stop order. We may visualize a computer that spits out a stream of discrete outputs nonstop. (An issue here is that in thinking of a nonstop successor algorithm, we presuppose units of time being 1:1 with N, the set of natural numbers. Alas, our mental picture is inadequate to overcome the interdependence of primitive concepts.)
So at this point the successor axiom permits us to build ever-larger finite entities but does not permit us to assume some 'limiting value' associated with a particular successor function. Yet such limits are highly desirable.
Let us consider irrational reals. In the case of square roots, a geometric form -- the hypotenuse of a right triangle -- can be measured by a ruler (we neglect the issue of accuracy of the ruler, an issue that also applies to rationals) in less than a minute. Most would agree that the distance expressed by a square root exists and can be plotted on a number line, justifying the naming of that distance by a symbol such as x^0.5.
However, other irrationals, such as 2^0.2 can only ever-better 'approximated' as a rational by some successor function, such as Newton's method or an 'infinite' series. Because the nested interval in which such an irrational is found grows smaller and smaller, we might through careless thinking suppose that we can justify some limiting distance from origin because we believe we are getting closer and closer to an interval of zero length. But our successor function requires eternity to exactly locate that point. So in human terms, such a distance is unmeasurable and might be said by some to be nonexistent. Still, the difference between two nonstop successor functions, unequal in every finite output, may still be held to grow ever smaller, helping to justify existence of such a point.
Now, should we regard this distance/number a fait accompli or should we regard it as impossible to achieve?
Consider the circle. Is the circle an ideal thought form that axiomatically pre-exists geometry or is it an artifact of human ingenuity which in fact doesn't exist because a 'true circle' requires a nonstop algorithm -- perhaps the positing of a a set of n-gons of evermore facets? (Then of course the straight line, the point and the plane must be accepted a priori.)
Daniel J. Velleman (Philosophical Review,1993) proposed that constructivism be 'liberalized' to accept countable infinities (but not uncountable ones) on the grounds that 'performing infinitely many computations is not logically impossible, but only "medically impossible".'
Yet, an intuitionist or constructionist might disagree that such a performance is logically possible, but rather argue that the term 'countable infinity' is simply a phrase for describing extension by induction. That is,
If X is infinite and countable, then x e X <--> (x+no e X.
Still, we are implicitly presupposing that time is already divided into a countably infinite number of unit 1 intervals. That is, we face a circularity problem.
Nevertheless, the inductive model of X does not require that X ever be complete. That is, we can write [we use 'All' for the universal quantifier and '$' for the existential quantifier]
$n e N All m e N All t e T ( f(tm)--> (x e X <--> x+no e X))
We would say that T is an ideal in P-space and not a result of a performable algorithm.
It seems quite evident that the pure constructivist program falters on the issue of time.
The issue is interesting because the successor axiom brings us to the issue of paradoxes (or antimonies), in particular those of Russell and Cantor. Though such paradoxes may be ruled axiomatically out of order, such an approach leaves a mild sense of disquiet, though I fear we must, if pressed, always resort to axioms.
At any rate, the value of a fundamental contradiction is that it demonstrates that a system of rules of thought based on form alone is insufficient to express the 'stuff' of being. And, of course, such a contradiction may pose serious questions as to the usefulness of a theory; I have in mind Cantor's paradox to the effect that the cardinality of U, the set of all sets, is unstable.
Following the Brouwerian path, Wittgenstein, who disliked such self-referencing anomalies, tried to dispose of them through a philosphical appeal to constructionist ideas. Cantor's champion, Hilbert, tried to limit the use of 'ideals,' but was nevertheless pushed to defend the notion of infinite totalities, at least implicitly. Without infinite totalities, or actual infinities, Cantor's paradise would fall.
The dispute between, essentially, platonists and constructionists is not resolvable without further elucidation, and is unlikely ever to be fully resolvable.
I suggest introduction of two axiomatic, or, primitive, concepts: a realm of thought assigned a timelike property, which, for short, we might dub T-space, for time-controlled, or Turing, space; a realm of thought with the property of timelessness, which we might dub P-space, for Platonic space. These spaces, or realms, are not topologically definable.
Now we are in a position to say that rules of mathematical thought that exist in T-space do not exist in P-space. There are no set-theoretic rules or relations in P-space, because no timelike operations.
We are permitted to collect all P-space objects into a set, but P-space itself is axiomatically not a mathematical set. The set of P-space objects is however an ideal and a resident of P-space.
Now, a P-space ideal may be exported to T-space and used in operations. Even so, if a P-space ideal is related to a T-space recursion function, the recursive's successor rule may not be applied to the ideal (no self-referencing permitted).
For example, a limiting value -- no finite nth step of an algorithm can go above it, or below it -- is is considered to exist in P-space. Likewise, the 'construction' of a circle occurs in T-space. The limiting form, a pure circle, is assigned to P-space.
At this juncture, it is necessary to point out that some constructions are purely logical, while others require repetitive computation. A recursion function, such as an algorithm to obtain pi, cannot yield an output value without the previous output value as an input value. That is, computation follows F_n o F_(n-1) o F_(n-2) ... F_0, where F_0 is the initial step of a composite function. Here construction occurs by 'building' one brick at a time. In the case of, for example, [lim n--> inf.] n/(n+1), a recursive computation does not occur. However, an inductive logical operation does occur. That is, we mean that n/(n+1) < (n+1)/(n+2) < 1 for any finite n. Does such a logical relation imply 'construction'? We may say that it can be thought of as a secondary form of construction, since values of n are constructed by
f(n+1) = n + 1.
Still, whether we have direct recursive construction or only indirect recursion, we place such mathematical operations in T-space. Because T-space is considered to be timelike, we avoid the issue of which comes first, the algorithm or the ideal.
Relations between T-space and P-space
An actual infinity can be defined as nondenumerable if it cannot be produced by a nonstop n-step algorithm. The algorithm's logical form is inductive: If property p holds for step n, then property p holds for step n+1.In the case of a denumerable infinity, it is always possible to relate this platonic-space ideal to a Turing-space induction condition. However, simple induction of course is insufficient to justify a nondenumerable infinity. Cantor's diagonal proof of the nondenumerability of the reals uses the contradiction of the possibility of simple induction. Here we have a situation where the set of irrationals exists in P-space but the rule of inference in T-space is not induction alone.
So at this point we assert that if a relation between a P-space ideal and a T-space procedure cannot be justified to the satisfaction of the mathematical community, then we would say that the ideal is not recognized as a mathematical object, even if it be in some way numerical. For example, an infinite digit string which is a priori random would seem to have no direct relation to a T-space procedure, though perhaps an indirect relation might be found. However, if we set up a no-halt order procedure for pseudorandomly assigning at step n a digit to the nth digit space, the P-space ideal of an infinite pseudorandomly digit string would be held to exist as a mathematical object in P-space, being justified by an inductive claim: no matter how great n, there is no step at which the entire digit string inclusive of the nth digit can be known in advance.
In the case of a strict induction model for a geometric ideal, such as a curve, we can partly justify analytic methods here but the issue of the real continuum must also be addressed (see below). That is, we can say that if an n-gon with all facet endpoints equidistant from a centerpoint can be drawn, then a like (n+1)-gon can also be drawn. We relate this induction model to the ideal of a true circle by saying that 0 is the 'limiting value' of n-gon facet length.
Likewise, we can authorize the 'area under a curve' using a numerical 'approximation' induction model. [However, see the page above, 'When algorithms collide.']
A significant analytic issue here is raised by the induction model of obtaining arc length as a sum of approximated line segments. As n is increased, the difference in facet length decreases, so that at the limit of 0 length, all points are of equal length. Yet, each point on the arc is 1:1 with a point on the axis, which are also of 0 length. Yet the infinite sum of the points of the arc may be unequal to the infinite sum of the points on the axis interval. Does this mean arc zeroes are unequal to interval zeroes? Anyway, isn't 0 x infinity equal to 0?
We can always write off such a puzzlement as 'counterintuitive' and leave it at that. But I think it might help to say that the ideal associated with the T-space arc formula A is not identical with the ideal of the T-space arc formula B. We cannot in this case 'compare zeroes.' But we can say that ideal A is a quantum-like ideal where the zero is related to a sub-ideal which we call an infinitesimal quantity. And infinitesimal quantities may be unequal.
Perhaps you accept that the epsilon-delta proofs of analysis have killed off the dread infinitesimal. By that you mean that the induction method obtains a numerical limit but that pure geometric forms are not in fact mathematical objects. The number exists but the curve is not 'constructible.' The 'actual infinity' that makes 'all' points of a curve 1:1 with 'all' points of a line does not exist in this scenario.
Yet if ideals are sometimes necessary in mathematics, why arbitrarily rule out a particular ideal, such as an infinitesimal?
I do not wish to assert that fundamental issues are now, voila!, all resolved. I simply say that the concepts of T-space and P-space may make us more comfortable from the standpoint of consistency. Yet, more reflection is needed as to what these concepts mean with respect to Godel's incompleteness theorems.
Godel's incompleteness theorems say that for a consistent formal system F based, for example, on Peano arithmetic, there is always a true statement P that cannot be proved in F.
If we extend F (call it F1) by adding P as a nonlogical axiom of F, then there is a statement PF that is true but not provable in F1.
We can define a set of systems such that Fn+1 is the formal system obtained by adding PFn as a nonlogical axiom to Fn.
So we have a T-space construction routine, or recursion algorithm, for compiling formal systems such that Fn --> Fn+1 --> PFn+1 is true but not provable in Fn+1.
If we define a P-space ideal limn->inf. Fn, we see that Godel's result does not apply, since constructive activity is not permitted in P space, in which case the Godel sentence PFn is not defined.
On a more fundamental level, we may wish to address the issue of belief that a theorem is true, based on our particular algebra, as against the theorem being a priori true, regardless of what one believes.
Consider what Wittgenstein saw as 'Moore's paradox,' which he obtained by coupling the statements 'There is a fire in the room' and 'I believe there is no fire in the room.' If statement A is a priori true, then, according to some, we would face a fundamental paradox.
You respond perhaps that one does not say 'There is a fire in the room' without either believing or not believing the assertion, whether or not there is an a priori truth to support it. That is, the truth value of a 'fact' is meaningless without a mind to review it. A cognitive act is not precluded by the notion that 'experience tells one' that previous sensory impressions (beliefs) about fire leads one to anticipate (believe) that one's current sensory impression about fire is valid.
So then, does a mathematical ideal require belief (perhaps justified by T-space inference) in order to exist? We come down to the definition of 'exist.' Certainly such an ideal cannot be apprehended without cognition. If, by cognition, we require a sense of time, then we would say that ideals are 'pointed to' from T-space thought patterns but also might exist independently of human minds in P-space, though of course the realms of mentation designated platonic space and turing space presuppose existence of some mind.
Of course, we must beware considering T-space to be a domain and P-space a range. These spaces are a priori mental conditions that cannot be strictly defined as sets or as topological objects.
Coping with paradoxes
Consider Cantor's paradox. The definition of power set permits us to compute the quantity of all elements of a finite power set. In every case, there area 2^n elements. But does an actual infinity, U, the set of all sets, exist? Since U is a set, shouldn't it have a corresponding actually infinite power set? What of the contradiction (with C the subset symbol and U' meaning power set) expressed:U C U' C U'' C U''' ...?
Our response is that U, as a P-space ideal, may not have its 'shadow' generation rule applied to it. We can also accept U', as a P-space ideal, which also cannot have its shadow generation rule applied to it. Though we might export U or U' to T-space for some logico-mathematical operation, we cannot do the operation U C U', which requires application of set-building rules on U, a banned form of self-referencing.
In general, we prohibit a successor rule from being applied non-vacuously to an actually infinite ideal. For example, [lim n->inf.](n) + 1 = n is simply the vacuous application of a successor rule.
Similarly for Russell's paradox: R, the set of 'all' (here assuming 'all' signifies an infinitude) sets that contain themselves as members, and S, which is R's complement, exist as P-space ideals. If exported to T-space a successor rule cannot be applied. So the question of whether R e R is prohibited. However the T-space operation R u S = U is permitted.
An infinite (or open-ended) set 'generated' by a successor rule requires a concept of time, which includes the concept of 'rate of change' (even if the rate is an unobtrusive 1). If we talk about a completed denumerably infinite set, we are saying that 0 is the limiting value of the generation algorithm's rate of change.
Let A be a finite set and P(A) be the power set of A. We now specify
P(A)->P(P(A)), which we may express P[0](A)-> P[1](A).
So, in general, we have P[n](A).
Now to indicate the power set of the set of all power sets, we write
lim n-> ¥ P[n](A) The usual way to dispose of this paradox is to say that though a collection is an extension of the set concept, a collection is not necessarily a set. Hence the collection of all sets would not itself be a set -- a theorem stemming from the ZF axioms.
However, here we address the paradox by saying that, if the denumerably infinite set is construed as completed, then the generation algorithm's rate of change is 0, as in
lim n-> ¥P[n+1](A) = lim n-> ¥P[n](A).
In other words, lim n-> ¥P[n](A) exists in P-space and a 'self-referencing' T-space algorithm is prohibited.
The principle of the excluded middle
The principle of the excluded middle -- which is often read to mean a logico-mathematical statement is either true or false, with no third possibility -- was strongly challenged by Brouwer, who argued that the principle is unreliable for infinities. Our rule of prohibiting 'self-referencing' operations on ideals helps address that concern.The reliability of the principle of the excluded middle is a concern in, for example, the Goldbach conjecture.
Let us define the Goldbach conjecture inductively as
i) Q = ((P(2x) --> P(2(x+1)))
A disproof requires
ii) ~Q = ~((P(2x) --> P(2(x+1)))
There is also the possibility that neither i) nor ii) is decidable [using '+' for the exclusive 'or']:
iii) ~(Q + ~Q)
Here we see a point where platonists and intuitionists clash. The platonists, rejecting iii) as a way of writing 'Q is undecidable' would claim that merely because we cannot know whether Q or ~Q is true does not mean that it is false that either has a truth value. The intuitionists would argue that Q's alleged truth value is of no mathematical interest.
If we accept iii), we must require that De Morgan's law not apply to the exclusive 'or,' even though truth tables for ~P v Q and ~P + Q are identical.
De Morgan's law transforms iii) into ~Q & Q, which is false by contradiction.
However,
P v Q = ((P & Q) + (P + Q))
But if P = ~Q, we would have
~Q v Q = ((~Q & Q) + (~Q + Q))
Yet the contradiction ~Q & Q is disallowed.
A similar philosophical perplexity arises from the question of whether Euler's constant is rational or irrational. The constant g is considered to be a number on the basis of at least one induction model. To wit:
lim -> ¥ å1/n - In1/n = g
where g is an ideal constant.
It is quite plausible that gamma's rationality is undecidable, that there is insufficient data to determine rationality. So the statement 'gamma is rational' may not have a knowable truth value. Does it have an a priori truth value? Many mathematicians would assert that if a truth value is unknowable, the issue of a priori truth value is irrelevant.
Still, undecidability is most satisfactory if proved. Our position would be that, in the case of gamma, the irrationality conjecture would be proved undecidable if rationality could never be decided without application of a successor rule on gamma.
In the case of the continuum hypothesis, we see a case where a logico-mathematical statement has a 0 truth value, validating the warning against unrestricted use of the principle of the excluded middle. Godel and Cantor have collectively shown that Cantorian and ZF set theory contain insufficient information for a yes or no answer to the conjecture, which says that there is no Cantorian cardinal number between cardN (or Aleph_null, if you like) and cardP(N) (another Aleph).
The implicit flaw in the continuum conjecture is the expectation that the conjecture is either true or false. If you draw a playing card face down from a well-shuffled deck an do not turn it over, the proposition 'the card is a face card' is either true or false -- even if you do not examine the obverse before shuffling the card back into the deck. Though the truth value remains forever undecidable, it is presumed to have an a priori truth value. I call such a proposition an undecidable statement of the first kind.
The continuum conjecture is then an undecidable statement of the second kind -- undecidable because the statement has no truth value in some logic system, whether that system be sharply or fuzzily defined.
[Thanks to Paul Kassebaum for drawing my attention to a difficulty with my categorization of undecidables. It seems that I inadvertently omitted the category of undecidable statements of the third kind, which would cover questions that are notionally answerable but which are computationally too difficult. For example, it is computationally imposssible to even name most numbers, let alone compute with them. However, Paul had a good point in noting that computational difficulty seems to fit my "first kind" category, in that, from a platonist perspective, both categories have a priori answers that are inaccessible.
In addition, a "fourth kind" seems in order: the obvious one stemming from Godel's incompleteness theorems: a sufficiently rich complete system contains at least one undecidable statement.]
There is of course the issue of the provability of the assertion that the playing card is either a face card or not; taking a cue from the Copenhagen interpretation of quantum mechanics, we cannot be sure that the two realities are not combined into a superposed state, with neither reality in existence until an observation is made. Though such an interpretation is normally applied to the nanometer world, the thought experiment about Schrodinger's cat shows that quantum weirdness can be scaled up to the macro-world. We cannot be sure that 'reality' does not work that way. (See 'The resurrection of Schrodinger's cat' at the link above.)
I have been unable to think of a logico-mathematical statement that is an undecidable of the first kind and I conjecture that such a statement cannot be proposed.
Of course, propositions of the second kind are common in mathematics, as in: 'The nth integer is prime.'
Godel and Cohen have proved the continuum hypothesis to be such a 'meaningless' statement; similarly our scheme makes the paradoxes of Russell and Cantor equivalent to an undecidable of the second kind.
In our model, we would say that cardN
and cardP(N) are P-space ideals but that a cardX such that cardN less than cardX less than cardP(N) is not a mathematical object in P-space because no inference rule exists relating a T-space procedure to a P-space ideal.
In a 1930 paper, Heyting
(appearing in 'From Brouwer to Hilbert,' compiled by Paolo Mancosu, Oxford, 1998), says the intuitionists replace the concept 'p is false' with 'p implies a contradiction.' So then, ~p is a 'new proposition expressing the expectation of being able to reduce p to a contradiction' and '|- ~p will mean "it is known how to reduce ~p to a contradiction".' Hence comes the possibility that neither |- p nor |- ~p is decidable.
Heyting notes that |- ~~p means 'one knows how to reduce to a contradiction the supposition that p implies a contradiction,' and that |- ~~p can occur without |- ~p 'being fulfilled,' thus voiding double-negation and the principle of the excluded middle.
Through tables of such inferences, Heyting derives the logico-mathematical inference states of proved, contradictory, unsolvable, unprovable, not unprovable, not contradictory and not decided.
On the continuum
The obvious way to define the reals is to posit 'any' infinite digit string and couple it to every integer. Of course, Cantor's diagonal argument proves by contradiction that the reals cannot be enumerated. Since the rationals can be counted, it is the irrationals that cannot be.It is curious that the if f is a function that yields a unique real, the family of such functions, Uf, is considered denumerable. That is, we might try to list such writable functions by i e I. We could then write an antidiagonal function g = f_i(i) + 1. But logicians disdain this type of paradox by requiring that f be written in a language L that imposes a finite set of operations on a finite set of symbols. It is found that the function g cannot be written without resort to an extended language L'.
(It is however possible to establish a nondenumerable subset of irrationals that is 1:1 with a subset of writable functions f if we permit the extended language L'. See 'Disjoint nondenumerable sets of irrationals' above.) So then we find that Cantor's diagonal proof reduces to an existence theorem for a subset of reals undefinable in some language L. To put it another way, such a real is 'unreachable.' We cannot order such an r by the inequality p/q < r < s/t (with p,q,s,t e Z) because we cannot ascertain p/q or s/t.
In my view, such unreachable reals are ideals. They exist in relation to the ideal of the totality of reals. But their shadows do not exist in T-space. So they have low relevance to mathematics. In fact, we cannot even say that the subset of such reals contains individual elements, raising a question as to whether such a subset exists. Again, the subset is a P-space ideal, and the T-space method of defining this subset by individual elements does not apply.
So then we have that cardR (whatever aleph that is after aleph-null) becomes a shorthand way of saying that there exists a set of irrationals whose elements are undefinable in L.
The concept of nondenumerability is useful in that it conveys that the set of irrationals is much 'denser' than the set of rationals. This gives rise to the thought of ordering of infinities with transfinite numbers. But 'X is nondenumerable' means X is ~cardN. The continuum conjecture could be expressed cardN < cardM < cardR. But it can be better expressed cardN < cardM < ~cardN. This last expression succinctly illustrates the result of the labors of Godel and Cohen: that the conjecture is 'independent' of set theoretic logic.
Arithmetic recursives
Consideråio i
We might call this a paradigm iterative function, where the domain and range intersect except at possibly initial and final (or limit) values. Such a function is considered 'non-chaotic' because the sequence is considered informative. That is the naming routine of å i is the same as the naming routine for i. The digit-place system is considered informative because we can order a number y less than x less than z in accord with this naming routine. That is, we know that 52 > 5 because of the rules of the digit-place system.
As shown below, a recursive function may be construed as non-chaotic if the recursive f is writable as some simple well-known function, such as n or n!
An arithmetic recursive can be written:
f(n) = h(n)f(n-1) + g(n)
We note that h(n) and-or g(n) can also be recursive, for a composite of the type: h(n) =k(n)h(n-1) + l(n)
and that it is also possible to have such expressions as
f(n) = h(n)f(n-1) + f(n-2)
where f(n-2) kicks in after a kth step of f(n).
A few recursive sequences:
h(n) = n, g(n) = 0
f(0) = 1, f(n) = n!
In general, if g(n) = 0, then f(n) = Õh(n).
h(n) = (n+1)/n, g(n)=n
f(0) =1, f(n) = 4, 9, 16 = n2; f(0) = 0, f(n) = 3/2, 3, 19/4...
h(n) = 1/n, g(n) = 1
f(0) = 1, f(n) = 1, 3/2, 11/8...
h(n) = 1/n, g(n) = n
f(0) = 1, f(n) = 2, 3, 4... = n
h(n) = 1/n, g(n) =1/ n
f(0) = 1, f(n) = 2, 5/2, 7/6, 13/24...
h(n) = 1, g(n) = 1/n
f(0) = 0, f(n) = 1, 3/2, 5/6 ...
f(0) = 1, f(n) = 1, 2, 5/2...
h(n) = n, g(n) = n
f(0) = 1, f(n) = 2, 6, 21...
h(n) = -n, g(n) = -n
f(0) = 0, f(n) = 0, -3, 8, -45 ...
h(n) = -n, g(n) = n
f(0) = 0, f(n) = 1, 0, 3, -8, 45...[recheck]
h(n) = -n, g(n) = -1
f(0) = 0, f(n) = -1, 1, -4, 15, -66...
if g(n) = 1, we get f(n) = 1, -1, 4, -15, 66...
Basic manipulations of such recursives:
Let f_k express h(n)f(n-1) + g(n) where f(0) = k and k is any real initial value.
If g(n) = 0, then f_k/f_j = (Õ h(n)k)/(Õ h(n)j) = k/j.
f_k - f_j = Õh(n)k - Õ h(n)j = Õ h(n)(k-j)
This last expression yields a function
m(k-j) = h(n)f(n-1) + 0g(n)
Denoting the discrete first derivative of f as f', we have, if h = 1:
f'(n) = f(n) - f(n-1) = g(n).
If h does not equal 1 at all values, we can write f' as an inequality, as in
h'(n) £ f'(n) £ g'(n), or g'(n) £ f'(n) £ h'(n)
Example:
f(n) = (n2 + (1)f(n-1) + n3
g'(n) is polynomial but Õ k(n^2 + 1) changes exponentially. Hence after some finite value of n, we have, assuming k is a positive integer:
3n2 < f'(n) < [Õ k(n2 + 1) - Õ k((n-1)2 + 1)]
Example:
f(n) = (n2 + 1)f(n-1) + Õ (n3 + 1)
Because g(n)'s exponential rate of change is higher than f(n)'s, we have, after some finite n:
h'(n) < f'(n) < g'(n)
Such inequalities are found in recursive ratios fa/fb, where fa =/= fb
For example, the irrational z(-2) can be written:
fa(n)/fb(n) = [n2fa(n-1) - (n-1)2!]/n2!
At step n+1, the ratio has a numerator that contains an integer greater than the numerator integer for step n; likewise for the denominator.
We see that ever-greater integers are required. Assuming the limit of fa/fb is constant, when this ratio at step n is converted into a decimal string, the string lengthens either periodically or aperiodically.
So we might say that [lim n-> inf]fa is an 'infinite integer' -- or a pseudo-integer. An irrational can be then described as a ratio whereby two pseudo-integers are relatively prime. Or, we might say that there exists a proof that if the ratio is relatively prime at step n, it must be relatively prime at step n+1.
Obviously, the set of pseudo-integers is 1:1 with the reals, a pseudo-integer being an infinite digit string sans decimal point.
If we require that a real be defined by a writable function based on the induction requirement, then the set of reals is countable. But if we divorce the function from the general induction requirement, then the set of reals is nondenumerable, as discussed here.
Do your best to present yourself to God as one approved, a workman who has no need to be ashamed, rightly handling the word of truth.
--2 Tim 2:15
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 a0 e A. Since A is infinite, A =/= {a0}, so we can choose some a1 e A such that a1 =/= a0. Similarly, A =/= {a0,a1}, so we can choose a2 e A such that a2 =/= a0 and a2 =/= a1. Continuing in this way, we can recursively choose an e A such that an ~e {a0,a1,...,an-1}. Now let R = {<0,a0>, <1,a1>, <2,a2>...} . Then R is a one-to-one correspondence between N and the set {a0,a1,a2...}, 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 a0,a1,a2... 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 a0,a1,a2... 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 [{an}] e X, then [{an}] 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 an and that this rule must always yield the same value for an.
A brouwerian choice sequence fails to assure that an has the same value on every computation, even though {an} is cauchy. Such numbers are defined here as 'non-computable,' though perhaps 'non-replicable' is a better characterization. A brouwerian cauchy sequence {an}, 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 {an} is equivalent to {bn} and hence that [{an}] = [{bn}] 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 w1 and w2.
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 AC1: 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 yo 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 2n+2.
At limn->inf. 2n+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 n2n+2.
But limn->inf. n/2n = 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 kn has a cellular diagonal at the tiling algorithm's infinite limit.
On the other hand, a tiling defined by nk 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 card2n, which corresponds to step n of our algorithm, in which we have a set of 2n+2 pre-reals.
Additional remark:
Lemma: Any set with limn->inf kn 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 limn->inf 2n elements. Hence the cardinality of each set is identical. Similarly, the algorithm above can be rewritten as ckn, with c a nonzero integer constant, meaning that all real digit strings are established at limn->inf ckn.
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 an of cauchy sequence {an}, then {an} is a choice sequence if f(n) --> aon+1 or a1n+1 or . . . or amn+1.
Note i.Since a choice sequence is cauchy |am - an| <= 1/k for all m and n after some no. However, the rule for determining step n+1 means that more than one choice sequence is possible for every n after some no. That is, a choice sequence's limiting value must fall within an upper and lower bound.
Note ii: It may be that axn+1 is non-randomly determined. Yet, there exists an infinity of choice sequences such that the limiting value of {an} 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 TN 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 104 years old, against a cosmic time scale of 1.5 x 109. In other words, we have a ratio of 2.5(104)/1.5(109) = 1.6/105.
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
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 3Before 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.
No comments:
Post a Comment