How does one define the usual logical operators (think back to your first course in symbolic logic)?…by way of tables.
Let’s think of the binary representation of (as a coded expression of the continued fraction form of…) an irrational number (…as provided by the cross-reference capability of the Stern-Brocot tree) as a row in an infinitely wide and hence infinitely long “table of definition” that exhausts all possibilities (where T = 1 and F = 0). How can we show such a table, or at least how can we describe its construction? Clearly, as the system or form given by a particular algorithm or rule of construction that will set the labels on the branches in a binary tree. The labels then suffice to assign “output” via infinite paths in the tree associated with L/R moves through the tree.
Our trees are simply data structures, and their output is a record of the search along a designated path, the designation of which is given as an infinite input string…a string where 0 = L and 1 = R.
What is the “operator” we are trying to define? The operator that gives us the strings to begin with…the operator that gets us from the finitude of the codes for the rational numbers to that of the infinite codes for the irrationals. That operator is our set of three infinite binary trees and the system of labels assigned to them. The output is the set of codes, the rows in the table, themselves. The individual elements are common to all three trees, but it is their combined orderings that makes sense of the idea of going beyond the finite strings.
The table has a countable number of rows.
But what about diagonalization? Make the observation that it depends for its conclusion on a specific ordering of N. The ordering of N assumed and required by “ZFC”. However, the natural numbers can correspond to the count of a collection of objects without any reference to their order with respect to themselves. We can buy goods either by count or by “more or less” as in “I want more and you want to give less”. Both systems of trade work and have real world people that use them.
The usual rebuttal to any claim of countability is that one can reorder the set of counting numbers to give the structure necessary for diagonalization… essentially a restatement of the initial assumption in Cantor’s proof. Without a specification of order of the left side of Cantor’s table…x… one cannot get to the definition of the elements on the diagonal (elements in each f(x) corresponding to each x) in terms of that order. Otherwise the elements that would make up his “diagonal” would be all mixed up and no diagonal could be defined.
Instead of claiming “non-denumerable” one should keep the complementary structure of the set of binary codes front and center. Do not put complements in the same table. Adopt the rule that a table of infinite binary strings for the purpose of establishing cardinality must consist of exactly one of each pair of complements. We should be looking at two tables, each following the “no complements” rule. Oh, they say, but you can then reorder your tables by interleaving the two tables….exactly, you have just confirmed that order is inextricably tied up with your idea of cardinality since your rebuttal is based on an assumption that such a reordering of the table is possible and necessary.
The ordering given by the output of the DD tree cannot just be “reordered”…mainly because its output is not just an arbitrary reordering of the set of binary strings. It is a completely different kind of order. Change that order and you have changed the fundamental structure of the set. That structure is part and parcel of what it is to be a “set” of distinct objects. The “leaves” of the DD tree are arranged in an order in which neighbors differ by exactly one bit change. The structure of the infinite binary strings themselves is determined by their ordering since that ordering is all that makes them “definite” in any sense. Otherwise they are “incomplete”. They are not “definite” in themselves. Their ordering cannot be separated from their “essence” as it can be for finite strings. Without it they become non-entities.
The parity of binary strings in DD order is an alternating sequence…perfectly ordered……the parity of strings in counting order is the Thue-Morse sequence.
The output, the goal, is the “exhaustion” of all possibilities. We want an assessment of the structure of that set of possibilities, especially its cardinality as separate from any dependence on a particular ordering of them. We want to see an equivalence class structure that clearly reveals what it is or what it means to take the fateful first step (and only possible step) “beyond finite”. But, you say, to exhaust all possibilities you need both elements of every pair of complements. Yes, but to count them you have to keep track of what has been counted, and for that you must separate them into two collections…those counted and those yet to be counted.
Remember back to the construction of the Binary Tree. Labels on the left half of a row are just the count of all the vertices on the right side of the tree up to but not including the vertices on the right half of the row. One arrives at the labels on the right half of a row two ways:
- counting only on the right side from left to right starting at the first vertex on the right at just below the “top”
- by counting from the left end of the row being labeled.
- The labels assigned either way on the right half of a row will be the same.
We can think of the labels on the left of a row as the “history” of the labels to its right. The second element in each pair of complements is a “second” record of the count. Therefore, if you count pairs of complements as “separate” elements you will have counted the vertex labels twice: once for the vertices on the right half of the tree and again by the “history” of that same count given by the complements on the left half of a row. That double count is the logical error in “uncountability”.
What can be said about a structure that makes it both decidable yet free of the confines of finitude? Clearly, at least it’s clear to me, it is the step of the sort we find throughout the tree. It’s strictly binary…the equivalence class structure is at most and only binary in form. The whole tree can be cut in half…not infinitely often…only once….else it is not the whole tree being cut. Hence “Dedekind cuts” are all the same…there is no way to have your cut and “eat it, too”….if the cut uniquely defines an irrational number then it is possible only because there is a “one-after-the-other” sense to the structure being cut, and that sense must be transitive in the sense of carrying over to the cut itself: the irrational number defined by the cut. That “one-after-the-other” sense means the irrationals must be countable just like the rationals.
“Bah, humbug,” says Cantor…
…sorry people, but if you want the freedom that comes by way of “uncountable”, then you don’t also get definability for your “infinite sets”. It is exactly as Wittgenstein charged…the structure you get when you use algorithm when you want and choice whenever that fails is no structure at all. So much for such “rigor”. It’s a joke.
Don’t like the joke? Then make the obvious step of explicitly defining what it is that you are doing…abandon implicit definition via axiom and embrace a constructive view of what constitutes mathematics. Start with data structures defined via binary trees. After all, counting a collection of objects begins with the ability to separate those already counted from those yet to be counted…a record, a history or memory of sorts…a division into two piles. Otherwise you say, “I lost count”.
21st Century Paradox 