↑ Return to Mathematical Foundations

Cantor’s Fallacy: Proof that All Sets are Countable in a True Infinitism Foundation for Mathematics

Cantor’s Fallacy – Proof that All Sets are Countable in a True Infinitism Foundation for Mathematics

Definitions

Let a “class” be anything with parts.

Let an “atom” be anything that is not a class.

Let a thing x be “distinguishable from” a thing y if and only if x is part of a class y is not part of, or y is part of a class x is not part of.

Let the act of assigning x and y to classes so as to make them distinguishable from each other be called, “to distinguish.”

Let a “thinker” be a thing that distinguishes things.

Let a class be “discrete” if and only if it has no part, including its whole self, that is indistinguishable from another part or distinguishable from itself.

Let a “set” be a discrete class.

Let a set’s parts be called its “elements.”

Let there be an atom named “zero” that is part of a class named “the natural numbers” and let any part of the natural numbers except itself be called a “natural number.”

Let “the successor of” any natural number be the set containing that natural number and its elements.

Let “the zeroth successor” of any natural number be that natural number itself.

Let “succession” be the act of forming the successor of a natural number.

Let “the strict successors of” any natural number be the set of natural numbers formed by recursive succession on that number, and let any element of the set of its strict successors be called a “strict successor” of it.

Let “the successors of” any natural number be the set consisting of itself and its strict successors.

Let a “sentence” of a set be any many-to-one mapping of zero and its successors to the members of that set.

Let a “sequencing” of a set be any one-to-one mapping of zero and its successors to the members of that set.

Let the “index” of an element of a sentence or sequencing be the first element of its ordered pair.

Let the act of generating a sequencing through acts of distinguishing be called “to sequence” a set.

Let a sentence of a set of atoms “specify” a set if and only if it enables a thinker to sequence that set.

Let the sentence of atoms that specifies a set be called a “specification” of the set.

Let the set of atoms used to specify a set be called the “minimal alphabet of the set.”

Let a “revision of” any specification of a set be another specification that strictly includes the first specification as a part.

Let any specification be called the “zeroth revision” of itself.

Let a “revision sequence” of a specification of some set be a sequence of recursed revisions of a specification beginning with itself as the zeroth revision; let the set be called the “base set” of the revision sequence.

Let the “restriction to” a set R of any mapping, including the mappings from the successors of zero to atoms that are defined to be sentences, have its usual meaning of being the subset of the mapping where the initial pair in each ordered pair is a member of the intersection between the entire mapping’s domain and the set R that the mapping is being restricted to.

Let an “initial clause” of length n of any sentence S, n a successor of zero, be the restriction of S to the set consisting of zero and the first n successors of zero.

Let the “final set” of a revision sequence be the set specified by either the last revision in the revision sequence or, if there is no last revision, by the sentence F formed by the concatenation of all members of the revision sequence in order of succession separated by some atom, called the “revision operator” of that revision sequence, that is not in the minimal alphabet of any revision in the sequence, and whose occurrence in the sentence F is interpreted to mean, “Given the set specified by the restriction of this sentence to the successors of zero less than my index,” which has the effect of deferring the sequencing of the set specified by the entire concatenated sentence to the subsentence with indexes higher than that occurrence.

Let “the revisions of” any specification of a set be the set of successively recursed revisions of that specification.

Let a “definition” of any set be the set containing all the revisions in a revision sequence of the set, as well as that revision sequence itself.

Let the “extension” of any set be the set of things a thinker ultimately sequences as a result of applying all the revisions of the set in the order given by the revision sequence of the set.

Let two revisions sequences be “informationally equivalent” if they result in the exact same sequencing of atoms.

Let a “defining sequence” of any set be any sequence the thinker generates using the set’s definition to specify the set’s extension.

For any number n and revision sequence V of any set, let the “nth set rendition in V” be the set of things specified by the thinker’s sequencing of the set based on the nth revision in V.

Let a set be called “finite” if and only if any sequencing of it includes a number but not its successor; let it be called “infinite” if it is not finite.

Let a set be called “finitely definable” if and only if there exists a finite sequence of atoms that defines its extension; let it be called “finitely undefinable” if it is not finitely definable.

Let the “cardinality” of a set be the number, if it exists, that is not mapped to any member of the set by any sequencing of that set, but is the successor of a number that is thus mapped.

Lemmas

Lemma 0: Every extension of a set is the same.

Proof of Lemma 0: Suppose a set has two distinct extensions. Then that set belongs to two classes, the class containing all classes without the one extension, and the class containing all classes without the other extension. Thus the set is distinguishable from itself. But by definition, a set is not distinguishable from itself. By contradiction, then, every extension of a set is the same.

Lemma 1: A set has a cardinality if and only if it is finite.

Proof of Lemma 1: By definition a sequencing of a finite set maps a number whose successor it does not also map, which is by definition its cardinality. Conversely, if a set has a cardinality, the cardinality is a successor of a number mapped by a sequencing of the set, and yet is not in the set, therefore by definition the set is finite.

Lemma 2: The definition of a finitely definable set has a finite number of finite revisions.

Proof of Lemma 2: If the definition contained an infinite number of finite revisions, or any infinite revision, it would have infinitely many atoms, and would therefore not be the definition of a finitely definable set as assumed.

Lemma 3: The set of all sequencings of any finitely definable infinite set is finitely undefinable.

Proof of Lemma 3: Suppose not. Then there is a finitely definable infinite set A whose set of all sequencings Q is also finitely definable.

Thus there is a finite sequencing of atoms B defining A, and since B is finite it has a cardinality b.

And there is a finite sequencing of atoms R defining Q, and since R is finite it has a cardinality r.

We will us Cantor’s familiar diagonal argument to show there is a sequencing x of A that is not in Q.

R enables a thinker T to sequence Q with the sequencing RQ, which is a sequencing of all the sequencings of A.

We now give the following finite sequencing of atoms that will enable thinker T to sequence A in a way not listed in RQ:

“For each number n, let x be the sequencing of A that maps n to the member of A to which the the nth member of RQ maps the successor of n.”

Since the nth member of x differs from the nth member of each member of RQ, x is not a member of RQ.

Since this is true of any finite sequencing R of the set Q of all sequencings of A, there is no finite sequencing of Q, hence there is no finite definition of Q, the set of all the sequencings of A.

This is true of any finitely definable infinite set A, thus the set of all sequencings of any finitely definable infinite set is finitely undefinable.

Lemma 4: Any set with a revision sequence that includes an infinite-length revision has another revision sequence consisting of infinitely many finite revisions which provides the same information to any thinker.

Proof of Lemma 4: Let S be a set. By definition of “revision sequence” there is no such thing as a finitely undefinable set of revisions of S. Thus any revision sequence V of S contains a finitely definable set of revisions. Thus we can replace the (finitely definable set of) infinite revisions in V with an infinite number of finite revisions by taking, as each successive revision Wn, increasing finite segments of each infinite revision for an increasing number of infinite revisions. As n increases, the revision Wn approaches V, thus V and W provide the same information to any thinker T.

Lemma 5: Any finitely definable set has a defining sequence and thus an extension.

Proof of Lemma 5: Suppose the finitely definable set S has no definition. S either has no elements, has some element, or has both no elements and some elements.

Case 1: If S has no elements, it has the following:

a) a definition containing a revision sequence that includes only one specification, which is an empty mapping of the elements of S with the natural numbers, and

b) that empty mapping as the only revision in the sequence.

Case 2: If S has a finitely definable set of elements, it has the following:

a) a definition containing a revision sequence that includes only one specification, which is a one-to-one mapping of the natural numbers to the finite unique identifiers of all its elements, and

b) that mapping as the only revision in the sequence.

Case 3: If S has both no elements and some elements, then it belongs to the class of all things with no elements and the class of all things with some elements, hence is distinguishable from itself, and is therefore not a set.

Since all cases lead to contradiction when assuming the contrary, any set S has a definition, thus a defining sequence that establishes its extension.

Lemma 6: Any finitely undefinable set has a defining sequence and thus an extension.

Proof of Lemma 6: Let U be any finitely undefinable set. Let V be a revision sequence of U, and let |V| be the set of revisions in it. Then |V| either consists of infinitely many finite revisions or contains an infinite revision (containing infinitely many atoms).

Case 1: If |V| consists of infinitely many finite revisions, let Z be the result of the sequential application of all members of V according to their ordering in V.

For each natural numbers n, let Un be the nth set rendition in V, and let Zn be some one-to-one mapping of the set of multiples of the first n primes to the members of Un.

Then as n increases, the domain of Zn approaches the set of all natural numbers and its range approaches U. Thus Zn is the nth set rendition in a revision sequence we may call W, which defines a set Z that is a one-to-one function of the natural numbers onto U. Thus the revision sequence whose nth revision is “the range of the nth set rendition in W” is a defining sequence of U.

Case 2: If |V| contains finitely many revisions, including one or more infinite revisions, then by Lemma 4 U has another informationally equivalent revision sequence W that fits Case 1.

Theorems

Theorem 1: There exists a one-to-one mapping of the real numbers with the natural numbers.

Proof of Theorem 1: The set of real numbers maps one-to-one with the set of all sequencings of the natural numbers, which is finitely undefinable by Lemma 3. By Lemma 6 it has a defining sequence, which by definition is a one-to-one mapping of its members with the natural numbers. By transitivity of one-to-one mappings, the set of real numbers maps one-to-one with the set of natural numbers.

Theorem 2: All sets are countable.

Proof of Theorem 2: Since there exists a one-to-one mapping of the real numbers with the natural numbers, by definition the real numbers are countable. Let Q be any set. Since Q is a set, by definition it is indistinguishable from itself, thus it is either finitely definable or finitely undefinable, and not both. If it is finitely definable, it has a one-to-one mapping with the natural numbers by Lemma 5. If it is finitely undefinable, it has a one-to-one mapping with the natural numbers by Lemma 6. In both cases, the mapping proves by definition that Q is countable.

Cantor’s Fallacy in His First Uncountability Theorem

Cantor’s First Uncountability Theorem held that for any sequencing W of the real number interval [0,1], given a real interval [a,b] within [0,1], the sequencing X of a subset of W that takes the first element a’ in W in that interval, and then the next element b’ in W that lies in [a’, b], and then the next element a” that lies in [a’,b’], and the next element b” in W that lies in [a”, b’], and so on and so forth with increasing index of iteration n in X, then the upper and lower bounds of that shrinking interval must either approach the same real number as n increases, or must approach different real numbers with a real interval between them. In either case, there must be a real number in the interval [a,b] that is not an element in W.

Cantor’s theorem is just a simple application of our Lemma 3 if by W he means a finitely definable sequencing of real numbers in [0,1]. Certainly no finitely definable sequencing will exhaust the set of real numbers in [0,1], because that set is finitely undefinable. But if Cantor here means to assert that any sequencing, finitely definable or not, will fail to exhaust the real numbers in [0,1], then he is wrong. And it is clear from the conclusions he later draws from this theorem that he does indeed fallaciously believe that he has proven here that no sequencing of the real numbers in [0,1] at all can define the real numbers in [0,1].

Suppose, then, W sequences a finitely undefinable set. Then by Lemma 6 we can have W be the limit of an infinite sequence of revisions of the set of real numbers in [0,1], each revision a one-to-one mapping of an infinite subset of the set of real numbers in [0,1] onto an infinite subset of the natural numbers, and each revision specifying the set’s extension in a finite string of symbols that includes the entire specifying string from the immediately preceding revision.

Of course, since there is no telling how the set’s specified extension changes from one revision to the next, the revision sequence does not “converge,” but it does not have to. We know that the length of the specification string diverges, and that is all that we require to maintain that the sequence is not finitely definable. We know that each revision includes the information from all prior revisions, though it may use it in a very different way, so that with each revision the revision sequence potentially changes about how to use that information to help it specify an extension. A finitely undecidable set’s ultimate specification of its extension, its ultimate sequencing of its membership, is the result of a linearly ordered but endless process of arbitrarily deliberative revision, what Brouwer called a “choice sequence.”

The fact that this deliberative process takes infinitely many steps instead of finitely many does not mean the resulting infinite set has “more” members than the infinite set whose membership is specified in finitely many steps. The “moreness” is not in the size of the set’s resulting extension, but in the number of successive independent choices made to arrive at the final extension, an infinite number versus a finite number, and in the total size of the specifying language string, an infinite string versus a finite string.

Now, if we define another set with a specification string that uses a finite string as a name to refer to the extension of a set already defined by an infinite string, and then we revise infinitely many times to build up an infinite string as well, then in some sense the new set is based on a “higher infinity,” but only because it is infinite at two levels of reference, the result of two recursive loops of infinite-revision limit-taking. This also, however, has no bearing on the size of the resulting set extension thus specified. The “moreness” in this case, rather, has to do with the number of levels of embedded reference to infinitely defined sets the specification string contains. Expanding all of those embedded references to their full infinite length, even if they are embedded infinitely deeply, still results in just a concatenation of infinitely long strings, which is simply one string that is infinitely long, and countable.

Consider a string S that is the concatenation of a finite string A with a string B following it, where A represents an infinitely long string C. Replace A with C in S to get string S2. It is a fallacy, akin to Cantor’s fallacy, to think that the string B at the end of S2 lies somehow beyond infinity and that S2 therefore must have more than an infinity of symbols in it, more symbols than C has. If that were true, then I could cause the quantity of symbols in C to be greater than itself simply by picking out any symbol in C and putting it at the end of C. The fallacy here is that there is such a thing as an “end of C.” C is infinitely long, which by definition means there is no end to the sequence of its symbols. So what, then, does it mean to concatenate C and B? It simply means that the resulting string S2 is not a total ordering of its symbols.

Another way to look at this fallacy is to see its nonsense in the substitution of the infinite string C for the finite string A in S. Clearly that substitution completely displaces the rest of S, which is B, leaving B no place to exist in the resulting string S2, because B is “the rest of S” after A, but once we substitute C for A in S to transform it into S2, there cannot be anything in S2 after C, by the fact that C is infinite. So if we require S2 to be a total linear ordering of its symbols, which is to say, if we define string concatenation as an operation that preserves the total linear ordering attribute of its operands, then there is no such thing as the concatenation of C with B, and hence no such thing as the substitution of A with C in S.

Of course, just as we have found it useful to expand the ontology of mathematics to allow us to subtract numbers from smaller numbers, or take the roots of negative numbers, we could find it useful to concatenate infinite strings with strings that follow them. The result, however, will be a different kind of string, just as integers are different from natural numbers and complex numbers are different than real numbers.

If we allow an expanded notion of concatenation, which has to be one that does not preserve the total linear ordering attribute of strings, to let us create S2 by concatenating C and B, then S2 is a new kind of string that is not a total linear ordering of its symbols.

Cantor, however, assumes that S2 would still be a total linear ordering. And that is not unworkable. But it means we have to redefine what we mean by “total linear ordering.” Cantor’s fallacy, therefore, can also be explained in this way. He failed to recognize that, in concatenating an infinite string with another string following it, and preserving the total linear ordering attribute of strings in that concatenation operation, he implicitly employed a new and different meaning of “total linear ordering.” He pulled a bait and switch. The string S2, if it is still a total linear ordering, is not the same kind of total linear ordering as A, B and C are.

So what kind of total linear ordering is it? Cantor says, a “transfinite” one. But how does he define that? He does not. He simply gives it a name. So “transfinite” means a total linear ordering that is not a total linear ordering in the accepted sense. It is a total linear ordering in which that which has no end does have an end. That, of course, is nonsense. The only kind of total linear ordering S2 could be is one in which some member of its infinite class of symbols is the immediate successor of the rest.

Nowadays we call such a successor a “limit ordinal.” But what does that mean? It means it is the immediate successor of an infinite sequence of successors, which means it is not the immediate successor of any of its predecessors. That defies the definition of a successor. So the definition of “successor” must be changed to make room for limit ordinals. It must be changed to include more than natural numbers. We have defined “natural number,” “successor” and related terms above as follows:

Let there be an atom named “zero” that is part of a class named “the natural numbers” and let any part of the natural numbers except itself be called a “natural number.”

Let “the successor of” any natural number be the set containing that natural number and its elements..Let “the successor of” any natural number be the set containing that natural number and its elements.

Let “the zeroth successor” of any natural number be that natural number itself.

Let “succession” be the act of forming the successor of a natural number.

Let “the strict successors of” any natural number be the set of natural numbers formed by recursive succession on that number, and let any element of the set of its strict successors be called a “strict successor” of it.

Let “the successors of” any natural number be the set consisting of itself and its strict successors.

To allow for limit ordinals, we would have to change these definitions like this:

Let there be an atom named “zero” that is part of a class named “the transfiniter numbers” and let any part of the transfinite numbers except itself be called a “transfinite number.”

Let “the finite successor of” any transfinite number be the set containing that transfinite number and its elements.

Let “the zeroth successor” of any transfinite number be that transfinite number itself.

Let “finite succession” be the act of forming the successor of a transfinite number.

Let “the strict finite successors of” any transfinite number be the set of transfinite numbers formed by recursive succession on that number, and let any element of the set of its strict finite successors be called a “strict successor” of it.

Let “the finite successors of” any transfinite number be the set consisting of itself and its strict successors.

Let “the infinite successor of” any transfinite number be the set containing its finite successors and elements (that transfinite number, its elements and its strict finite successors).

Let “infinite succession” be the act of forming the infinite successor of a transfinite number.

Let “the strict infinite successors of” any transfinite number be the set of transfinite numbers formed by recursive infinite succession on that number, and let any element of the set of its strict infinite successors be called a “strict infinite successor” of it.

Let “the strict transfinite successors of” any transfinite number be the set of transfinite numbers formed by recursive finite or infinite succession on that number, and let any element of the set of its strict transfinite successors be called a “strict transfinite successor” of it.

This is all good and well, and using it we can define a “transfinite string” and let S2 be such a string, and allow concatenation to preserve its total ordering attribute. But it’s clear that the set of all transfinite numbers is still countable, even if we infinitely nest the replacement of finite substrings with infinite substrings, since the resulting quantity of symbols would still just be an algebraic expression in countable infinity, and hence still just equal to countable infinity.

The problem with Cantor’s proof of his first uncountability theorem is that his assumed sequencing of W is not general, but is implicitly a finitely defined sequencing. We can show this explicitly by describing a finitely undefinable instance of W which is not susceptible to his diagonalizing argument.

Theorem: Cantor’s First Uncountability Theorem does not apply to finitely undefinable sets.

Proof: For any n, let Wn be the nth revision of W defined by the finite string Dn, and let the range of Wn be distinct from that of any prior revision in the sequence. Let Zn be the mapping defined by Dn of the members of Wn one-to-one with the set containing zero, the nth largest prime number and its products with any number of instances of itself and any lesser prime numbers. As n increases, let Wn approach the set of all real numbers in [0,1], while Zn approaches a one-to-one mapping of the real numbers in [0,1] with the natural numbers.

What justifies our “letting” Wn approach the set of all real numbers in [0,1] as n increases? We know that for any n, the finite string Dn that defines Wn cannot map to every real number in the interval [0,1], because, being a finite string, it is susceptible to diagonalization. What justifies us assuming that an infinite sequence of such diagonalizable mappings will approach in the limit a non-diagonalizable mapping?

Our justification is precisely in the fact that finitely undefinable mappings are not diagonalizable, and that hence an infinite sequence of optimally short finite definition strings, each necessarily incorporated into the next so that the next is necessarily longer, approaches a necessarily infinitely long string in the limit. In the case of our Dn sequence, the infinitely long definition in the limit, D, cannot be reduced to a finitely long definition because the range that each Dn defines for Wn is distinct from that which every other Dn defines, thus D contains infinitely many substrings that define infinitely many distinct sets, and since the manner in which each successive Dn distinguishes the set it defines as the range of Wn is entirely arbitrary, a diagonal argument can prove that there exists a sequence Wn whose range sets defy generation by any finite string of any language.

Thus we may simply let Wn be such a diagonal sequence, and thereby let the Dn approach an infinitely long limiting definition string D that defines a limiting mapping W of the Wn whose range is a subset of the real interval [0,1], a subset that is distinct from any of the finitely defined range sets of the Wn. Since the range of W cannot be finitely defined, it cannot be the range of any mapping of any sequence Wn, for any n, for any sequence of definition strings Dn. But those ranges are all the diagonalizably defined subsets of the real interval [0,1]. Thus the range of W must be a non-diagonalizable subset of real interval [0,1]. Without loss of generality, we can simply let W be the total subset of the real interval [0,1], namely, the entire interval itself.

Applying Cantor’s proof to W thus constructed, consider a real interval [a,b], and the sequencing X of a subset of W that takes the first element a’ in W in that interval. Now, how do we determine what a’ is? We have to determine what natural number Z maps a’ to. But we cannot determine this in a finite number of steps. The ultimate sequential natural number indexing of the real numbers in [0,1] by Z is only accomplished through an infinite succession of revisions, and at each revision the real numbers that had been assigned certain natural number indices in the previous revision will likely be reassigned to new indices. So when Cantor blithely refers to “the next real number in the list W that is greater than a and less than b,” he is actually writing shorthand for an infinite length specification, and is thus introducing an infinite length string into his proof, making his proof itself infinitely long.

But his proof relies on a construction. To work, it must succeed in constructing the sequencing X that marches the left and right legs of the original interval [a,b] it begins with, left-right-left-right deeper and deeper inward but never such that left and right meet. Each step in that inward march is meant to peg an ever-higher natural number index, in our sequencing W of the real numbers in [0,1], to a left or right footprint, a lower bound or upper bound of a shrinking interval on the real line, thus assuring that the gap between those bounds, the forever shrinking but indelible gap between the left and right feet, will forever be out of reach of any index in our sequencing W. The march is meant to stomp down the entire infinite stretch of W outside that unreachable gap.

The problem is, for X to stomp down W in that way, it must determine the next element in W to stomp on at each step. To determine that, it must take each element of W in order and compare it to the last two elements in X to see if it falls between them on the number line. To take the next element of W it must first complete the construction of W; otherwise the mapping of the reals in [0,1] with the natural numbers is incomplete and provisional only, and can provide no basis for stomping down W outside the gap with finality. But we have shown that W, to be a sequencing of the real numbers in [0,1], must be the limit of an infinite sequence of revised mappings of subsets of that real interval with a progressively inclusive infinite subset of the natural numbers. To complete such a construction requires an infinite number of steps.

But we cannot afford to take an infinite number of steps before taking our first stomp. If we do that, we make our construction of X itself infinite in length, and in particular we make the entire infinite construction of W a required first step in the construction of X, with the rest of the construction only possible afterwards. This makes |X| a finitely undefinable set just like |W|, so either W and X can both be mapped one-to-one with the natural numbers, or both cannot be. If both cannot be mapped one-to-one with the natural numbers, then X cannot be constructed. If both can be mapped one-to-one with the natural numbers, then X can be constructed and the proof may proceed as planned, and it leads to contradiction as planned, proving that |W| cannot be mapped one-to-one with the natural numbers. But if |W| cannot be, |X| cannot be either since X is constructed by reference to W, and W does not exist. If that is the case, the proof breaks down again since there is no way to construct the sequence X required for the proof.

So to avoid this collapsing of Cantor’s proof into self-negating paradox, we have to find a way to construct |X| without first having to complete the construction of |W|. The only way we can do this is to try to construct |X| and |W| simultaneously, hopefully keeping our construction of |W| one step ahead of our construction of |X| so that as we pin down the values of W we are able to stomp them down outside our gap by assigning them as needed as values of X. Can we accomplish this feat?

No, we cannot. For the construction of W requires there to be no rule-driven restriction on the changes to the extension of |W| from one revision of W to the next. So the values of W at every index are utterly unsettled through every step of its construction until the very end, at infinity. Only upon the completion of an infinite number of revision steps does each index of the sequence W settle finally on a one-to-one assigned real value in [0,1]. Thus Cantor’s proof cannot avoid completing the infinite construction of W before embarking on its construction of X, hence it cannot avoid collapsing into self-negating paradox, rendering it meaningless and inconclusive.

Cantor’s Fallacy In his Second Uncountability Theorem

Cantor’s fallacy was his assumption that no method of construction exists to map the real interval [0,1] one-to-one with the natural numbers. We have provided such a construction using the very same principle of the supremum construction of infinite sets that was essential to Cantor’s set theory, and we have shown that the inaccessibility of the resulting bijection’s specific values to finite-length definitions of sets and sequences turns out to entail the non-existence of cardinals above countable infinity.

Cantor’s second uncountability proof meets a similar fate. In that one he claimed that any function f mapping a set S one-to-one and onto its power set P(S) can be used to construct a paradoxical set X, namely, the set of all elements s of S for which s is not an element of f(s). Since f maps some element of S to each and every subset of S, there must be some element x that it maps to X, f(x) = X. But if x is an element of X, then by the definition of X it is not an element of f(x) = X. And yet, since x is not an element of f(x) = X, by definition of X it is indeed an element of f(x) = X. Since either way, x both is and is not an element of X, the premises lead to contradiction and thus their conjunction must be false.

Theorem: Cantor’s Second Uncountability Theorem is False

Proof: There are actually two ways our foundation for mathematics, which we are calling True Infinitism, dispenses with Cantor’s proof of his Second Uncountability Theorem as fallacious.

First, X is simply not a set, because it is distinguishable from itself.

Second, even if we admit proofs about sets using classes like X that are not sets, X is constructible only with an infinite definition, because its definition incorporates that of the finitely undefinable function f. This second line of reasoning will bear some explanation.

To begin with, as a formality, we point out that we know the domain S and range P(S) of f are both infinite in extension, because if not, the finite cardinality of P(S) would exceed that of S ( |P(S)| = 2^|S| > |S| if |S| > 0) and f would not be one-to-one and onto.

Now, if P(S) were finitely definable, then since S and P(S) are infinite, the finite definition of P(S) would have to be recursive in some way. Without some kind of recursive interpretation of the finite definition string for P(S), there would be no way to specify an infinite sequence of elements with that string. This is not to say (yet) that P(S) would have to be “recursive” in the sense of being computable by a Turing machine. It does at least mean, however, that P(S) would have to be computable by a Turing machine with the aid of some finitely definable oracle (by “oracle” we mean the sequencing of some Turing-incomputable subset of the natural numbers). The oracle’s finite definition, however, would in turn have to be recursive in some way, relying on yet another finitely definable oracle, whose finite definition in turn would have to rely on yet another oracle, ad infinitum. This infinite regress of finite definitions of oracles would constitute a necessarily infinite definition string when fully expanded.

The only way to cut short the infinite regress would be either to arrive at an oracle whose definition is infinite and thus does not rely on yet another oracle, or to arrive at an oracle whose finite definition requires no further oracle. If the last oracle’s definition is infinite, then of course the entire definition of P(S) is infinite just as in the case of the infinite regress of finitely definable oracles. If the last oracle’s definition requires no further oracle, then it is not really an oracle because it would be Turing-computable without an oracle, which would render the previous oracle also Turing-computable without an actual oracle (it would be defined with a Turing-machine using a non-oracle input that could just as well be computed by the Turing-machine itself), and the entire sequence of oracle definitions would collapse backward into just a simple Turing-machine that defines P(S) with no help from any oracle at all. Thus either P(S) is Turing-computable or it has an infinitely long definition string.

We have shown that if any set, including P(S), has a finite definition, it is Turing-computable.

Now, if P(S) is Turing-computable, so is S. Otherwise we would not be able even to identify the elements of S in a Turing-computable definition of P(S), which we must do to specify the subsets of S which constitute the elements of P(S). But if S and P(S) are both Turing-computable, any function f mapping S one-to-one and onto P(S) would be a subset of S x P(S), the cross product of two Turing-computable sets.

If f were finitely definable, it would be Turing-computable, so it would have to be a Turing-computable subset of the cross-product of two Turing-computable sets. Clearly such an f is not the general case f that appears in Cantor’s second theorem, which refers to any function f that maps any set S one-to-one and onto its power set P(S).

If f were finitely definable, it also could not be the limit of any infinite sequence of extensionally arbitrary revisions fn mapping subsets Sn one-to-one and onto their power sets P(Sn), with each revision incorporating and adding onto the finite definition string of the last revision, because if it were, the sequence of revision definitions would be strictly increasing in length, and in the limit it would be be an infinitely long string. But that limit is precisely what f must be constructed as in the general case of f being an arbitrary one-to-one mapping of an arbitrary set S onto its power set P(S). Thus by contradiction f, and with it X, must be constructible only with an infinite definition. Both f and X are thus finitely undefinable.

Since f is finitely undefinable, it maps S one-to-one and onto P(S), but yields no method of determining which element of s maps to which element of P(S). So if we try to construct X by using f, we find we cannot. The specific values of S and P(S) mapped by f can only be established by comprehending the infinitely long definition of f, which is impossible to do.

But this does not mean X cannot be constructed. X must simply be constructed the same way as f or any finitely undefinable set, as the limit of an infinite sequence of revisions, each of which is a finitely defined set incorporating the definition of the prior revision. But each revision Xn is defined on the basis of the corresponding fn in the construction of f, which is not onto P(S), and Xn is among the subsets of S that fn does not map any member of S to, for otherwise the paradox will be invoked for Xn and fn. We cannot have Xn be self-contradictorily defined, for that would stall and break our construction of X. So we have to conclude that for any n, Xn is not in the range of fn.

It may seem at first fine to allow Xn to be excluded from the range of fn, and yet include X in the range of f, since there are obviously infinitely many subsets of S that are not in the range of any fn, yet they are all in the range of f. It seems even more plausible since the Xn for any n could well be in the range of fm for any m not equal to n. But the Xn are a special subset of the set of subsets of S that are not in the range of fn, because the Xn are necessarily excluded from the range of their corresponding fn and thus are excluded as an inherent aspect of the definition of the fn. Each fn does not just happen to exclude the Xn; it excludes Xn because if it does not, it collapses into paradox. Thus by definition, not just by happenstance, fn does not have Xn in its range.

Now, consider all the subsets of S. Given any fn, each subset of S must be either in the range of fn, or not. And presumably we can determine the exact membership of Xn by running through each member s of S and checking whether fn(s) exists, and if so, determine whether s is an element of it or not. Suppose we do so, and have a precise infinite enumeration of Xn. There is no reason, then, why we should not be able to revise fn to obtain fn+1 by taking any element s1 of S that fn maps to some subset of S fn(s1), and map it instead to Xn.

Now, suppose that s1 is not an element of fn(s1). Then it is an element of Xn. Thus since fn+1 maps s1 to Xn, of which it is an element, s1 would not be an element of Xn+1.

But let us revise fn+1 to obtain fn+2 by mapping s1 to Xn+1 instead of to Xn. Then s1 is not an element of fn+2(s1), thus it is an element of Xn+2. We can begin this pattern with n=0, and continue this alternation ad infinitum, so that s1 is in Xn for even n, and not in Xn for odd n.

Now, suppose we also make f0 differ from f2 in a specific way. Consider some s2 in S, not equal to s1. Let f0(s2) be some subset of S that does contain s2. Then s2 is not an element of X0. Now let f2(s2) = X0. Then since s2 is not an element of f2(s2), s2 is an element in X2. Now, suppose we repeat this pattern of revision in relation to s2 for all even n, so that s2 is not in Xn for values of n that are even multiples of 2, and s2 is in Xn for values of n that are odd multiples of 2.

Now, suppose we also make f0 differ from f3 in a specific way. Consider some s3 in S, not equal to s1 or s2. Let f0(s3) be some subset of S that does not contain s3. Then s3 is an element of X0. Now let f3(s3) = X0. Then since s3 is not an element of f3(s3), s3 is not in X3. Now, suppose we repeat this pattern of revision in relation to s3 for all n divisible by 3, starting with n=0. Then s3 is in Xn for values of n that are even multiples of 3, and s3 is not in Xn for values of n that are odd multiples of 3.

Suppose we repeat this pattern ad infinitum for s4, s5, … sm, sm+1, … and suppose this sequence of sm includes all elements of S.

Then for every element s of S, there exists some subsequence of the sequence of revisions Xn for which that element s keeps flipping in an out of Xn, ad infinitum. Far from being a sequence of arbitrary revisions, then, the sequence of Xn that in the limit defines X actually has a very definite pattern in relation to every member of S. There is some infinite subsequence of the Xn that oscillates between including and excluding each and every member of S, ad infinitum.

Thus it is clear that as n approaches infinity, the Xn converge in the limit to an ambiguous collection that both contains and does not contain each and every element in S, and is therefore distinguishable from itself and thus not a set but a class without extension. By contrast, the conditions we have placed on the fn to construct X in this manner do not cause the fn to converge to any particular kind of function, and hence the fn are still free to converge to a finitely undefinable set that maps the elements of S one-to-one and onto the power set of S.

Now, while it is certainly worthy of note that f can be easily constructed so as to render the concomitant construction of X as the convergence of the oscillating Xn sequence that is so in accord with the paradoxical nature of X itself, and while we continue to maintain that X is therefore not a set at all but an extensionsless class, what we have proven beyond that here is that X can be defined in a finite string of symbols. We did that very thing when we defined it as the limit of a sequence of subsets of S that oscillate on the membership of every member of S in perpetuity and at different frequencies. This definition fully characterizes the extensionality of X, which is the specific manner in which it fails to have an extension at all. Thus X is finitely definable without reference to f at all, and cannot therefore be either a set or a class that is genuinely defined upon the basis of the finitely undefinable function f that maps S one-to-one and onto the power set of S. If it were thus defined, it would, like f, not be susceptible any finite definition.

The downfall of X, which is a fully generalizable version of the paradoxical Russell set, is precisely the susceptibility of its defining sequence of revisions to rule-driven lockdown of its divergent behavior on each input as a direct result of its lack of any independent grounding other than the arbitrary behavior of a finitely undefinable function’s freewheeling perpetual revisioning of the relationship between the members of its domain with the members of its range. Any set defined solely in terms of the relationship between the domain and the range of a finitely undefinable function ultimately can be defined finitely in its entirety because the relation between its own revisions is finitely and rigidly defined in terms of the relation between the domain and range of each finitely definable revision of the finitely undefinable function. This recursive rigidity in the definitional dependence of the Xn on the fn ultimately decouples X entirely from the function f in the limit as the Xn converge to X in a way that can be defined independently of the fn, and the fn converge to f in an arbitrary way that breaks free of whatever structure the Xn found in the fn upon which to establish its convergence to Xn.

The Diagonal Contained

The usual textbook version of a proof of the uncountability of the real numbers is to imagine a random list of decimals numbers and to create one not on the list by changing each digit along the diagonal of the list. The decimal number that results going down the diagonal could not have been on the original list because it was created by changing one digit of each line of the original list.

Suppose, however, we consider the diagonal to be part of the list to begin with, as well as any sequence of digits obtained by taking any path through the list from the top left in rightward or downward steps, and any sequence obtained by changing all the digits in any such path. Then there would be no diagonal or other meandering hidden decimal that is not “on the list” because we have defined “on the list” to include them all.

Is that assuming what we are trying to prove? Not at all. For suppose we take any finite square of digits on this list that includes the top left digit. It contains an initial segment of all possible diagonal or meandering decimal numbers our rules define to be “on the list.” As we expand that square, we can obviously read all those initial segments out loud in sequence if we want, so in what sense does expanding that finite square indefinitely result in an inability to represent any decimal numbers “on the list?”

Ah, one might say, if we read all the initial segments in sequence, we can construct a diagonal down that sequence that is not included “on the list” by our rules. Alright then, we’ll broaden our rules to include any diagonal or meandering decimal constructed by changing digits in a path through any sequentially recited list of decimals “on the list.” Really, it’s not that hard to come up with a set of rules that makes the set of decimals we consider “on the list” to be closed under any diagonalizing type of operation on the list.

Of course, in the end, that closure would simply amount to the set of all sequences of digits of length x. Is that cheating? Not at all. It only feels like cheating because ten digits seems like more than a fair number of variants to the human mind who likes to clump things comfortable in thee’s or five’s. If we repeat this entire discussion in binary instead of with decimals, and we physicalized it to say each digit is a copper penny, then we would just be saying we’re allowed to read each digit as itself or its flip-side. Is that cheating? So it’s a two-sided list, so what? What makes a set of numbers uncountable simply because you can’t list them all with a one-sided list with right-only walk but you can with a two-sided list with right-down walk?

The difference, of course, is merely that with two-sided right-down walk readings of the list, we get exponential branching coverage of sequences of heads and tails, which we don’t get with one-sided right-only walk. But if that’s the difference between an “uncountable” reading of the list and a “countable” reading of it, then it makes no sense to call this difference one of countable versus uncountable, for clearly we are counting the “uncountable” two-sided right-down walks every bit as much as we are counting the “countable” one-sided right-only walks.

The true difference between these two ways of reading the same list is that the one-sided right-only walk way results in a sequence of binary sequences that can actually be described in a finite string of recursive definition, whereas the two-sided right-down walk way results in a sequence that cannot thus be defined. The difference comes down the finite vs infinite intension, not infinite versus “transfinite” extension.

Implications for Set Theory

The class X is actually a generalized Russel “set.” We have shown that it has a perfectly acceptable and meaningful intension, which happens to define for it an extensionality that fails to achieve for it any extension at all. That is not to say it has the empty set for its extension. It is to say that it has no set at all for its extension, that it has no extension at all.

What we have done in the foregoing proofs of the fallaciousness of both Cantor’s Uncountability Theorems is to specify precisely the characteristic of a Russell set that causes it to be paradoxical, namely, that despite being finitely defined within the highly intuitive language and syntax of naive set theory, it fails to have an extension.

We have distinguished between such paradoxical finitely definable classes that are not sets, and the non-paradoxical classes that are finitely undefinable, by showing how the former can always be reduced to a finite definition that causes the extension of the class to oscillate in a rule-driven manner ad infinitum, whereas the latter cannot be reduced to any finite definition and thus have extensions that do not oscillate or follow any rule-driven pattern at all but, rather, arrive at their extensions through an infinitely long but non-self-contradictory process of arbitrary revision.

We can similarly resolve the mystery of the complement of the generalied Russel Set; call it Y. We define it as the set of sets to which f maps some natural number that is a member of the set f maps it to.

We can construct Y like we constructed X, by revising fn+1 for each n such that fn+1(s1) for some s1 in S, such that fn+1(s1) = fn(s). The result is that Yn can be constructed to either oscillate or stay steady on each candidate element as n increases, and which it does is entirely an arbitrary result of initial conditions. Thus it is also finitely definable, and therefore although it exists for each revision fn, it does not exist in relation to the finitely undefinable limit function f.

In elucidating the fallacies in Cantor’s Uncountability Theorems we have shown how the Russel Paradox and related antinomies of naive set theory can finally be resolved by the exclusion of the generalized Russell “set,” which is really an extensionless class, from the class of sets, without excluding any non-paradoxical sets, and in a perfectly understandable, intuitive, consistent and coherent manner. We have provided, in short, a new foundation for mathematics that suffers from no antinomies, and is both complete and consistent.

Conclusion

All sets are countable. Cantor’s two uncountability theorems are premised on a single fallacy, mistaking infinite intension for a purportedly higher kind of extensional infinity. By DeCantorizing infinity, we are able to set forth a new foundation for mathematics we call “True Infinitism” that does not suffer from the antinomies of naïve set theory, nor from the semantic limitations of less naïve set theories that attempt to evade those antinomies by axiomatizing them out of the syntax.

In axiomatizing away the paradoxes created by Cantor’s fallacy, we merely end up chasing the underlying fallacy into the woodwork of the semantics, where it continues to wreak havoc in the form of vexing problems of uncertainty and inherent trade-offs over ontology, epistemology, modality, reference, constructibility, decidability, consistency, completeness, non-standard interpretive models, convergence in its many meanings and infidelity to mathematical intuition.

By shifting our foundations instead onto the bedrock of True Infinitism, we resolve all these lingering difficulties.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

CAPTCHA
Reload the CAPTCHA codeSpeak the CAPTCHA code