We can get a feel for why Cantor's continuum hypothesis is independent
of standard set theory, both in the case of ZFC axioms and NBG axioms,
by beginning with the fact that Cantor's theory, as modified by ZFC
and NBG and other systems, implies the existence of non-specifiable
numbers.
Cantor's diagonal proof requires that a real be definable as a denumerable infinite decimal (or n-nary) extension. From this he showed that listing the reals in some consecutive order yields a number that cannot be on that list. Hence, the reals must be non-denumerable, which he saw as a "larger" actual infinity than the actual infinity of the naturals. So a cardinal number is defined by equipollence with some representative set, such as N. CardN is not equipollent to CardR, or in Cantorian notation Aleph_null is equivalent to CardN.
So, for Cantor, the cardinal numbers should represent a discrete set of "infinite integers." He was unable to prove however that CardR = Aleph_1, the second infinite "integer" or cardinal number.
The general continuum hypothesis (GCH) is that only cardinals equipollent to power sets exist after Aleph_null, or cardN. For example, the reals are bijective with the power set of N, which reflects another proof that R is of a higher actual infinity than N. (Any proof or disproof of GCH would follow almost immediately from a proof or disproof of HC, in which R represents the real number line continuum [1a].)
Now consider that the Church-Turing thesis (which is a fundamental intuition or axiom) posits that any computation that can be done (whatever its practicality) may be put in Turing machine form. This certainly makes sense when one considers that we would expect that every mechanical, mindless computation can be encoded as a Boolean logic circuit. And any non-logical circuit would not reliably output a computation that could be used with other computations in coming up with another logical circuit that solves a problem.
So one can say that every Boolean logic circuit, can, following a similar procedure for a Turing machine, have every gate given a unique integer number. We then encode these numbers, perhaps in a Goedelian fashion. So then, every Boolean logic circuit is assigned a unique positive integer (it is irrelevant whether more than 1 circuit yields the same output). For both Turing machines and Boolean circuits, the initial conditions, including input code, are included in the encodement by what may be called a Description Number.
In that case, every computable number is associated with one or more unique integers. We shall call this the set of computables, or K. K is infinite, because, among other things there is some description number k that encodes an algorithm for yielding any integer. So K is an infinite subset of N, meaning that cardK = cardN.
We shall call K's complement W, the set of noncomputables. No w e W can be specified or identified, though the Axiom of Choice can be used to manipulate W in standard set-theoretic ways. And of course K U W = R. (So most of the reals have only a ghostly reality.)
Well, any subset of K is either bijective with N or with n e N. A mixed set, such as K' U Y' -- in which K' and Y' are subsets of K and Y -- is either bijective with N, bijective with R or is equipollent to card(K' U Y') but not to K or R. But how can we determine Y'? Well, at least we know that Y' is bijective with Y/K or K/Y. The latter case is possible but not germane to the argument, which is that the mixed case is equivalent to the case Y being composed of all non-computables.
So to the point: If cardN < cardY < cardR, we must find a subset X of Y that is neither bijective with K nor R. Likewise, to show that no subset of Y is bijective with K, we must exclude all subsets of Y such that one has cardY.
But of course a set is defined by its elements. What to do when each element is individually undefined? We know w e W can express some magnitude on the real line, conventionally between 0 and 1; the trouble is, in principle, no one can hone in on that real point. [1]
From this we can see intuitively that the probability of proving or disproving GCH is virtually nil. So we can see the enormous plausibility of the combined results of Kurt Goedel and Paul Cohen that GCH is independent of the axioms of modern set theory -- without actually examining their rigorous proofs.
Interestingly, the WOT version of AC requires that anything properly defined as a set can be well-ordered, as in a nested sequence of least elements descending to a secure bottom (of the well). So the reals are well-ordered, even though we know of no algorithm to yield an element by element well-ordering. So all the k's are in the well-ordering of R. Because R is bijective with the power set of N, proving GCH requires proving that Y is never bijective with any element of p e P(N). Note that if we exclude all members p that are bijective with either N or P(N), we would still be unsure that the result is the null set without the independence proofs of Goedel and Cohen.
Cantor's diagonal proof requires that a real be definable as a denumerable infinite decimal (or n-nary) extension. From this he showed that listing the reals in some consecutive order yields a number that cannot be on that list. Hence, the reals must be non-denumerable, which he saw as a "larger" actual infinity than the actual infinity of the naturals. So a cardinal number is defined by equipollence with some representative set, such as N. CardN is not equipollent to CardR, or in Cantorian notation Aleph_null is equivalent to CardN.
So, for Cantor, the cardinal numbers should represent a discrete set of "infinite integers." He was unable to prove however that CardR = Aleph_1, the second infinite "integer" or cardinal number.
The general continuum hypothesis (GCH) is that only cardinals equipollent to power sets exist after Aleph_null, or cardN. For example, the reals are bijective with the power set of N, which reflects another proof that R is of a higher actual infinity than N. (Any proof or disproof of GCH would follow almost immediately from a proof or disproof of HC, in which R represents the real number line continuum [1a].)
Now consider that the Church-Turing thesis (which is a fundamental intuition or axiom) posits that any computation that can be done (whatever its practicality) may be put in Turing machine form. This certainly makes sense when one considers that we would expect that every mechanical, mindless computation can be encoded as a Boolean logic circuit. And any non-logical circuit would not reliably output a computation that could be used with other computations in coming up with another logical circuit that solves a problem.
So one can say that every Boolean logic circuit, can, following a similar procedure for a Turing machine, have every gate given a unique integer number. We then encode these numbers, perhaps in a Goedelian fashion. So then, every Boolean logic circuit is assigned a unique positive integer (it is irrelevant whether more than 1 circuit yields the same output). For both Turing machines and Boolean circuits, the initial conditions, including input code, are included in the encodement by what may be called a Description Number.
In that case, every computable number is associated with one or more unique integers. We shall call this the set of computables, or K. K is infinite, because, among other things there is some description number k that encodes an algorithm for yielding any integer. So K is an infinite subset of N, meaning that cardK = cardN.
We shall call K's complement W, the set of noncomputables. No w e W can be specified or identified, though the Axiom of Choice can be used to manipulate W in standard set-theoretic ways. And of course K U W = R. (So most of the reals have only a ghostly reality.)
Well, any subset of K is either bijective with N or with n e N. A mixed set, such as K' U Y' -- in which K' and Y' are subsets of K and Y -- is either bijective with N, bijective with R or is equipollent to card(K' U Y') but not to K or R. But how can we determine Y'? Well, at least we know that Y' is bijective with Y/K or K/Y. The latter case is possible but not germane to the argument, which is that the mixed case is equivalent to the case Y being composed of all non-computables.
So to the point: If cardN < cardY < cardR, we must find a subset X of Y that is neither bijective with K nor R. Likewise, to show that no subset of Y is bijective with K, we must exclude all subsets of Y such that one has cardY.
But of course a set is defined by its elements. What to do when each element is individually undefined? We know w e W can express some magnitude on the real line, conventionally between 0 and 1; the trouble is, in principle, no one can hone in on that real point. [1]
From this we can see intuitively that the probability of proving or disproving GCH is virtually nil. So we can see the enormous plausibility of the combined results of Kurt Goedel and Paul Cohen that GCH is independent of the axioms of modern set theory -- without actually examining their rigorous proofs.
Interestingly, the WOT version of AC requires that anything properly defined as a set can be well-ordered, as in a nested sequence of least elements descending to a secure bottom (of the well). So the reals are well-ordered, even though we know of no algorithm to yield an element by element well-ordering. So all the k's are in the well-ordering of R. Because R is bijective with the power set of N, proving GCH requires proving that Y is never bijective with any element of p e P(N). Note that if we exclude all members p that are bijective with either N or P(N), we would still be unsure that the result is the null set without the independence proofs of Goedel and Cohen.
1a. The continuum is an ancient concept and so is often taken to mean the mapping of all the positive integers onto a finite line segment. That is, the continuum is often identified with N mapped onto a finite magnitude, rather than the set R being so mapped. So then, the set of reals may be said to be the power of the continuum, or R is bijective with P(N).
1. See Kurt Goedel, 'What is Cantor's continuum problem?' in Philosophy of Mathematics, selected readings, 2d ed., Paul Benacerraf and Hilary Putnma, eds. (Cambridge 1984). In particular, see Page 278.
No comments:
Post a Comment