2008-04-03, 02:31
In another thread, I discussed the idea of a tree with transfinite height, and how we might go about defining such things. Basically, we made use of the 1-to-1 correspondence between nodes and paths from the tree root to each node, in the finite case. Then we made the observation that if a path is in the tree, then all its prefixes are also in the tree. Therefore, a transfinite tree is simply a set of paths of transfinite paths, satisfying the property that if P is in the tree, then all prefixes of P are in the tree as well. A transfinite tree defined this way has the interesting property that some nodes (specifically, those at limit ordinal depths) have no parent nodes but do have ancestor nodes.
Now, let's consider another kind of transfinite tree: a pathological kind where the root may have no children yet still has descendents! It is based on reversing the sense of paths in the previous kind of transfinite tree. Let C be a set with the same cardinality as the maximum number of children per node. Again, we associate strings over C with nodes in the tree, and we define a set of strings to be a tree if they satisfy if x is in the tree, then every suffix of x is also in the tree. The parent of a node x is the string obtained by deleting the first symbol in x. A node x is an ancestor of y if y is a suffix of x. The root node is the empty string, since the empty string is always the suffix of any string.
Clearly, for strings of finite length, this definition is identical to the previous definition. But consider the tree where every node is a string of limit ordinal length (still satisfying the suffix requirement, of course: this is possible because the parent of each string is still of limit ordinal length). The root node has no children, but is an ancestor of every node in the tree!
Even stranger is the tree obtained by taking a finite tree and then appending strings of limit ordinal length to it such that the suffix requirement is satisfied. Since none of the finite strings can possibly be a parent of the limit-ordinal-long strings, the tree consists of two kinds of nodes: one kind reachable by a finite path, and another kind reachable only by an infinite path. These two kinds of nodes are "connected" to the root in two completely different ways; the finite nodes have ancestors which are children of the root, but none of the ancestors of the infinite nodes are the root's children. None of the finite nodes are in the same "branch" as an infinite node, because finite strings are never a suffix of a string that's a limit ordinal long.
The root node doesn't have to be the only node with this peculiar property, of course. We could have paths with lengths of some limit ordinal like w+w, so at depth w we have nodes without children, yet with descendents.
It gets stranger than this. Let's say we now construct a tree with transfinite strings of non-limit ordinal length, say of length w+1. Then, the root does have children; but the children nodes have no further children, yet they do have descendents! Of course, the same thing happens for strings of length L+k, where L is some limit ordinal, and k is a non-zero finite number.
In other words, the difference between the original kind of transfinite tree and the inverted transfinite tree is that in the former, the "leap" across the "infinite gap" always occurs at limit ordinal depths, whereas in the latter, we get to choose when this "leap" happens by selecting a suitable value of k. We can even choose k differently for each branch in the tree. In the former case, we can always "leap" to a unique, minimal depth (we land at a node with no parent); whereas in the latter case, while we need to "leap" to access the infinite depth nodes, there is no minimum depth that we can leap to (we always land at a node with a parent).
Hence, in the original type of transfinite tree, the gaps are always "open upwards": at limit ordinal depths, nodes have no parents but do have ancestors. In inverted transfinite treese, the gaps are always "open downwards": at a certain depth, there are no more children, so you must leap downwards to the infinite descendents. These kinds of gaps are "one-way" gaps, where there is an infinite stretch on one side but not on the other. As long as we use ordinals to index node depths, we will always have only one-way gaps.
But it is possible to conceive of even stranger trees where the paths have infinite gaps that are open both ways: where ancestors are separated from descendents by an infinite gap, but every ancestor has a child and every descendent has a parent---yet the two sides never meet. We cannot index node depths with ordinals in this case: we need to use the equivalent of the closure of ordinals under subtraction. (We can obtain such an index set by using a suitable subset of Conway's surreal numbers.)
Is it possible to have a gap that is closed both ways? Such a thing would mean, hypothetically, that at a certain depth k, there is an "infinite" gap to another depth k', but the node at depth k has no children and the node at depth k' has no parent. But then this implies that there is nothing between the two nodes, and so there is no gap, and k'=k+1. So a gap that's closed both ways is equivalent to no gap at all.
All of this leads one to surmise that we can define a gap to be either open upwards (the usual meaning of transfinite path), open downwards (inverted transfinite trees), open both ways (surreal trees?), or closed (i.e., there is no gap). So a path consists of a sequence of nodes delimited by gaps of any of these 4 kinds, and a tree consists of a set of paths such that if P is in the tree, then every subpath of P is also in the tree. We allow any mixture of different kinds of gaps in a path. If a path has only closed gaps (i.e., no gaps), then it's a finite path; otherwise, it's an infinite path.
I'm not sure where I'm going with this, but it sure sounds interesting.
Now, let's consider another kind of transfinite tree: a pathological kind where the root may have no children yet still has descendents! It is based on reversing the sense of paths in the previous kind of transfinite tree. Let C be a set with the same cardinality as the maximum number of children per node. Again, we associate strings over C with nodes in the tree, and we define a set of strings to be a tree if they satisfy if x is in the tree, then every suffix of x is also in the tree. The parent of a node x is the string obtained by deleting the first symbol in x. A node x is an ancestor of y if y is a suffix of x. The root node is the empty string, since the empty string is always the suffix of any string.
Clearly, for strings of finite length, this definition is identical to the previous definition. But consider the tree where every node is a string of limit ordinal length (still satisfying the suffix requirement, of course: this is possible because the parent of each string is still of limit ordinal length). The root node has no children, but is an ancestor of every node in the tree!
Even stranger is the tree obtained by taking a finite tree and then appending strings of limit ordinal length to it such that the suffix requirement is satisfied. Since none of the finite strings can possibly be a parent of the limit-ordinal-long strings, the tree consists of two kinds of nodes: one kind reachable by a finite path, and another kind reachable only by an infinite path. These two kinds of nodes are "connected" to the root in two completely different ways; the finite nodes have ancestors which are children of the root, but none of the ancestors of the infinite nodes are the root's children. None of the finite nodes are in the same "branch" as an infinite node, because finite strings are never a suffix of a string that's a limit ordinal long.
The root node doesn't have to be the only node with this peculiar property, of course. We could have paths with lengths of some limit ordinal like w+w, so at depth w we have nodes without children, yet with descendents.
It gets stranger than this. Let's say we now construct a tree with transfinite strings of non-limit ordinal length, say of length w+1. Then, the root does have children; but the children nodes have no further children, yet they do have descendents! Of course, the same thing happens for strings of length L+k, where L is some limit ordinal, and k is a non-zero finite number.
In other words, the difference between the original kind of transfinite tree and the inverted transfinite tree is that in the former, the "leap" across the "infinite gap" always occurs at limit ordinal depths, whereas in the latter, we get to choose when this "leap" happens by selecting a suitable value of k. We can even choose k differently for each branch in the tree. In the former case, we can always "leap" to a unique, minimal depth (we land at a node with no parent); whereas in the latter case, while we need to "leap" to access the infinite depth nodes, there is no minimum depth that we can leap to (we always land at a node with a parent).
Hence, in the original type of transfinite tree, the gaps are always "open upwards": at limit ordinal depths, nodes have no parents but do have ancestors. In inverted transfinite treese, the gaps are always "open downwards": at a certain depth, there are no more children, so you must leap downwards to the infinite descendents. These kinds of gaps are "one-way" gaps, where there is an infinite stretch on one side but not on the other. As long as we use ordinals to index node depths, we will always have only one-way gaps.
But it is possible to conceive of even stranger trees where the paths have infinite gaps that are open both ways: where ancestors are separated from descendents by an infinite gap, but every ancestor has a child and every descendent has a parent---yet the two sides never meet. We cannot index node depths with ordinals in this case: we need to use the equivalent of the closure of ordinals under subtraction. (We can obtain such an index set by using a suitable subset of Conway's surreal numbers.)
Is it possible to have a gap that is closed both ways? Such a thing would mean, hypothetically, that at a certain depth k, there is an "infinite" gap to another depth k', but the node at depth k has no children and the node at depth k' has no parent. But then this implies that there is nothing between the two nodes, and so there is no gap, and k'=k+1. So a gap that's closed both ways is equivalent to no gap at all.
All of this leads one to surmise that we can define a gap to be either open upwards (the usual meaning of transfinite path), open downwards (inverted transfinite trees), open both ways (surreal trees?), or closed (i.e., there is no gap). So a path consists of a sequence of nodes delimited by gaps of any of these 4 kinds, and a tree consists of a set of paths such that if P is in the tree, then every subpath of P is also in the tree. We allow any mixture of different kinds of gaps in a path. If a path has only closed gaps (i.e., no gaps), then it's a finite path; otherwise, it's an infinite path.
I'm not sure where I'm going with this, but it sure sounds interesting.