2007-11-19, 20:50
Recently I've been playing around with non-standard set theories where Quine Atoms exist (a Quine Atom is a set Q that satisfies Q={Q}). In the course of exploring other Quine-Atom-like sets, I stumbled across the idea of transfinite trees.
Transfinite Trees
A finite tree, as we know, consist of a finite set N of nodes, with a distinguished node called the root node, and a set of edges such that there is a unique path from the root node to every other node.
An infinite tree is a tree where the set N is infinite. As has been proven by mathematicians, if every level of an infinite (countable) tree is finite, then there must exists an infinite branch (a branch that extends indefinitely). It is possible to have an infinite tree of finite depth, if some nodes have an infinite number of children. Infinite trees aren't that hard to visualize; they are just trees that extend indefinitely (has one or more infinite branches), or have one or more nodes with an infinite number of children.
But what is a transfinite tree? How do we consistently define nodes that lie beyond finite paths? Here's a possible idea:
Let C be a set of the same cardinality as the maximum number of children per node in the tree. We can then define a finite path as a sequence of elements from C (in other words, a finite path is a string on C), where each element in the sequence represents which child node to traverse next in our path. Each (finitely-reachable) node, n, then corresponds to a unique sequence
, which is the path to n. Now, we observe the following property: a node m is an ancestor of n if and only if 
is a prefix of . In particular, if the length of is precisely one less than the length of , then m is the parent node of n.
So now, we can define a transfinite node n as a node that corresponds with a path of infinite (possibly transfinite) length, satisfying the property that all of its prefixes also lie in the tree. Note that transfinite nodes with paths that correspond with limit ordinals have no parent node, but they do have ancestor nodes!
Since paths and nodes have a 1-to-1 correspondence, we can define transfinite trees simply as a collection of (possibly transfinite) strings on C, satisfying the property that if a string S is in the tree, then every prefix of S is also in the tree. The null string then corresponds with the root node, strings which are not prefixes of other strings in the tree are leaf nodes, and the remaining strings are internal nodes.
Note that transfinite trees have the property that even if C is finite, the resulting tree could be uncountable. For example, let C={0,1}, and take all sequences of C of length L. If L is finite, the corresponding tree is countable (indeed, finite). But if L is
, then the tree is infinite, because its leaf nodes corresponds with infinite sequences of C, which are uncountably many!
Quine Atoms and other Pathological Sets
How does all of this apply to Quine Atoms? Well, given a set A with elements that are themselves sets, we may consider A as the root node of a tree, and the elements of A as nodes under A, and the elements of those elements as nodes under these nodes, and so forth. In other words, the tree represents the "containment hierarchy" of A. The well-founded sets of ZFC then correspond with trees of finite depth. If we allow infinite trees, we see that the Quine Atom Q corresponds with an infinite linear sequence of nodes, since Q has itself as its sole element.
Now, if we generalize this to transfinite trees, we suddenly realize that Quine Atoms need not be unique; because it is possible for two sets Q and R, satisfying Q={Q} and R={R} respectively, to differ only at the transfinite depth in their containment hierarchies. For example, the tree corresponding to Q may have no leaf node, and the tree corresponding to R may have a transfinite leaf node at depth. In set-theoretic notation, Q={{{{...}}}} and R={{{{... {} ...}}}}. Thus, both sets satisfy the Quine Atom definition, but they differ at the transfinite depth: Q is "bottomless" whereas an empty set lies at the "bottom" of R.
In fact, we can substitute the transfinite node at depth with any arbitrary tree, possibly transfinite in themselves, and thus generate an infinitude of different sets all satisfying the Quine Atom definition.
If we consider arbitrary transfinite trees, we find many Quine-Atom-like sets that do not necessarily contain themselves as such, but may contain sub-elements that are not reachable via finite applications of the 'element-of' relation. I.e., they are not well-founded sets. However, none of these sets are truly pathological sets such as the one in the Russell Paradox.
The interesting thing about such infinitely-deep contained nodes is that they are not reachable by finite applications of the 'element-of' relation, and so their exact structure at transfinite depth is of limited utility. However, the fact that they differ in spite of behaving identically at finite depths allows us to use them as distinct urelements. We are also safe from running into Russell's Paradox.
Transfinite Trees
A finite tree, as we know, consist of a finite set N of nodes, with a distinguished node called the root node, and a set of edges such that there is a unique path from the root node to every other node.
An infinite tree is a tree where the set N is infinite. As has been proven by mathematicians, if every level of an infinite (countable) tree is finite, then there must exists an infinite branch (a branch that extends indefinitely). It is possible to have an infinite tree of finite depth, if some nodes have an infinite number of children. Infinite trees aren't that hard to visualize; they are just trees that extend indefinitely (has one or more infinite branches), or have one or more nodes with an infinite number of children.
But what is a transfinite tree? How do we consistently define nodes that lie beyond finite paths? Here's a possible idea:
Let C be a set of the same cardinality as the maximum number of children per node in the tree. We can then define a finite path as a sequence of elements from C (in other words, a finite path is a string on C), where each element in the sequence represents which child node to traverse next in our path. Each (finitely-reachable) node, n, then corresponds to a unique sequence
So now, we can define a transfinite node n as a node that corresponds with a path
Since paths and nodes have a 1-to-1 correspondence, we can define transfinite trees simply as a collection of (possibly transfinite) strings on C, satisfying the property that if a string S is in the tree, then every prefix of S is also in the tree. The null string then corresponds with the root node, strings which are not prefixes of other strings in the tree are leaf nodes, and the remaining strings are internal nodes.
Note that transfinite trees have the property that even if C is finite, the resulting tree could be uncountable. For example, let C={0,1}, and take all sequences of C of length L. If L is finite, the corresponding tree is countable (indeed, finite). But if L is
Quine Atoms and other Pathological Sets
How does all of this apply to Quine Atoms? Well, given a set A with elements that are themselves sets, we may consider A as the root node of a tree, and the elements of A as nodes under A, and the elements of those elements as nodes under these nodes, and so forth. In other words, the tree represents the "containment hierarchy" of A. The well-founded sets of ZFC then correspond with trees of finite depth. If we allow infinite trees, we see that the Quine Atom Q corresponds with an infinite linear sequence of nodes, since Q has itself as its sole element.
Now, if we generalize this to transfinite trees, we suddenly realize that Quine Atoms need not be unique; because it is possible for two sets Q and R, satisfying Q={Q} and R={R} respectively, to differ only at the transfinite depth in their containment hierarchies. For example, the tree corresponding to Q may have no leaf node, and the tree corresponding to R may have a transfinite leaf node at depth
In fact, we can substitute the transfinite node at depth
If we consider arbitrary transfinite trees, we find many Quine-Atom-like sets that do not necessarily contain themselves as such, but may contain sub-elements that are not reachable via finite applications of the 'element-of' relation. I.e., they are not well-founded sets. However, none of these sets are truly pathological sets such as the one in the Russell Paradox.
The interesting thing about such infinitely-deep contained nodes is that they are not reachable by finite applications of the 'element-of' relation, and so their exact structure at transfinite depth is of limited utility. However, the fact that they differ in spite of behaving identically at finite depths allows us to use them as distinct urelements. We are also safe from running into Russell's Paradox.