[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.
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.
No comments:
Post a Comment