A Game On Infinite Trees

An independent principle in set theory

Cropped from Oberwolfach source

Ronald Jensen is a famous set theorist who was a past president of the Kurt Gödel Society. Dana Scott is the current president of this prestigious society.

Today I thought we would turn from graphs and their isomorphism problem to the study of simple trees. Well I wrote that last week, but Ken has filled out details. In the meantime we are happy to note that László Babai has released his 84-page graph-isomorphism paper, and we anticipate saying more about it in coming weeks.

OK, our trees are not so simple, since they are infinite. The isomorphism problem for finite trees has long been known to easy—actually computable in linear time. But the infinite trees that we will look at are “complete” trees in a natural sense, and so isomorphism is not an issue. But they still have interesting properties.

A key property is one first studied by Jensen in 1972, which he called the diamond property and denoted by . I like this property because it is based on a natural game on infinite trees, which I could imagine playing on finite graphs. But Ken doubts it. We both like that Jensen was once the president of the Society named after Gödel, and so we at GLL should be interested in what he did.

Infinite Trees

In computing we study various types of finite trees. A binary tree, for example, starts at a root and each node has at most two children. The longest path from the root is the depth of the tree. The tree is finite if and only if the depth is finite.

We can extend this notion by allowing the number of children and the depth to be larger. An important type of infinite tree is when we insist that all nodes have a finite number of children but allow the depth to be countable. Many important computational processes can be modeled by such trees. The complete binary tree of depth has countably many nodes and levels but uncountably many branches, indeed of them. As usual denotes the cardinality of the natural numbers but denotes their order type.

Another more powerful notion is to insist the number of children of all nodes is countable and the depth is also countable. This tree, which we call the complete tree , is not too hard to imagine. Say a node is at level if it is steps from the root. Thus this tree corresponds to a process where at each stage one can make a countable number of choices. Think of a game played on an infinite chessboard, a game that never ends. Such a game would be a complete tree.

Now the next larger cardinal after is denoted by . The famous continuum hypothesis (CH), which was shown by Kurt Gödel and Paul Cohen to be independent of the standard axioms of set theory, says that

Putting that aside for the moment we can imagine that there is a complete tree. Every node has children, and the tree has levels of order type , which stands for the first uncountable ordinal.

This tree is frankly more difficult to imagine—at least for me—but let’s try and extend our minds. This tree has a very wide branching and is very deep. This combination makes its behavior quite different from the “smaller” complete tree.

We can come halfway by imagining trees whose nodes are bounded sets of nonnegative rational numbers. Here is a descendant of if and every member of is greater than the supremum of . We can control which sets are added to by transfinite recursion and create levels—one for every countable ordinal—but with only -branching since the children of append just one rational . Stranger still, although has levels, each individual branch can only be countable since is countable. For contrast, our complete -tree does have -sized branches, but this hints at the kind of behavior we must think about.

The Blocking Game

We will now consider a simple game that plays differently on these two trees, and . Drawing on the neat book Forcing for Mathematicians by Nik Weaver, we call it the blocking game:

Given a tree, can we place one mark on some node at each level of the tree so that there is no branch that starts at the root and continues forever and avoids any marks?

The obvious answer for the complete- tree is that this should be impossible—there are just too many choices at each level so how could one mark per level destroy all paths? We can prove this in many ways. Place the markers. Then pick a random walk down the tree. What is the probability that the walk never hits any marker? My intuition says that the probability of being blocked should be zero.

Start at the root. The chance your path hits a marker is , i.e., zero. Now repeat this times and we should get that the chance of being blocked is

with multiplication a countable number of times. This is zero. But wait. We cannot just treat like a number. Or can we?

The trouble is the use of as if it is a number. Let’s avoid this by making the blocker’s strategy easier. If we can still show that the probability of being blocked is small, then there will be a path that avoids all the markers. At level let’s restrict the blocker to use only a fixed set of nodes. Now at level the chance the random path hits a marker at the next level is . So the probability that avoids all markers is

It is easy to see that if we make go to infinity fast enough, then this is a positive probability. If you need some more convincing take the logarithm of the above and note that it is approximately

And we can certainly make this sum as small as we wish.

Blockers in Binary Trees

Before we look at the complete tree, let’s consider the complete binary tree with levels having order type . Then every branch of is a subset of . Every level corresponds to some ordinal and every node at that level is a subset of —recall that can be identified with the set of ordinals below . A set that consists of one node at each level above the root is therefore the same as a function from ordinals to sets .

Now with a binary tree we can readily block all paths on the first levels. For with define and . Branches that include are blocked in the first step from the root, then branches that include but not are blocked at the next step, and so on. Finally, branches that exclude all finite ordinals are blocked at level . This gives the first hint that our intuition above about always having the freedom to make the branch avoid blockers fails when it comes to limit ordinals like .

Modified from MathOverflow item—note interesting long answers from Joel Hamkins and Emil Jeřábek.

Now suppose we don’t allow any blockers at finite levels of the tree. The assertion that blocks all branches past that point is:

 

Can we disprove this? Amazingly, we cannot—not within set theory even given the axiom of choice. Moreover, this statement entails CH, since we have independent paths from the get-go and are purporting to cover them with only blockers. Jensen’s original statement of is equivalent to the existence of such an but tells us even more: we can block all branches uncountably many times in a particularly “thick” manner.

The Diamond Property

A set of countable ordinals is unbounded if for all there exists such that . It is closed if whenever is the limit of a subsequence and we have . A set that is both closed and unbounded is called a club.

A club set is loosely analogous to a set of measure one in or . The intersection of two or even countably many clubs is again a club. A set that has nonempty intersection with every club is called stationary. A stationary set is analogous to a set that has nonzero measure or is non-measurable; it has some thickness whereas a non-stationary set is called thin and is analogous to a nullset. The analogy is furthered by the fact that the intersection of a stationary set with any club remains stationary.

The original version of from section 6 of Jensen’s paper does not need to constrain for finite . His sequence notation in place of makes easier to stipulate. It is:

 

Another interpretation of is that as we are traveling up the tree through each level the function represents a “prediction” of exactly what and where some branch will be at time . Then the principle says that a single can predict every branch exactly correctly infinitely often—indeed uncountably often.

The Complete Aleph-One Tree Case

Now let’s turn to the the complete tree . The blocking strategy at finite levels of is blown away by the immediate -branching, though at level we still have branches. Can be blocked by one node at each level? Each node at level is now a function , not a subset of . A branch is a function .

The potential winning strategies of our blocking game on are functions such that is a node on level . This means a binary function but restricting to be defined only when . Again the sequence notation is traditional and clearer, so we use it to state the form of given in Weaver’s book:

 

Is harder to block than the -binary tree ? It seems yes but the answer is no: this form of is equivalent to the original. Roughly the reason is that so and have the same number of branches, and so they have the same number of nodes at each infinite level.

The diamond principle implies CH but is not equivalent to it. It holds in Gödel’s constructible universe . Weaver’s book closes with an interesting discussion of whether any of these independent principles should be accepted as “really true” the way we believe the consistency of various formal theories that we implicitly use. Along those lines, if you find these tree-blocking assertions hard to believe, it might be a reason not to regard as a ‘true’ model of set theory. We examine a couple more consequences and principles.

Saturation Blocking?

Suppose we have such that (2) holds. Let be the subtree of or that includes each branch up to the first point at which it is blocked. Then still has levels, but every branch of stops at a countable ordinal and so is countable. An uncountable tree in which every branch and level is countable is called an Aronszajn tree after Nachman Aronszajn who constructed one in 1934. We don’t need for this kind of tree—ZFC suffices to build our defined above: At a limit ordinal , for each existing node and rational , choose one branch of the previously existing tree that contains and has supremum , and let level consist of all the sequences obtained by unioning branches thus chosen. This use of uncountable choice enables transfinite recursion to embed the needed sequences over while keeping each level countable.

However, also implies the existence of a tree having levels in which not only is every branch countable but also every set containing no two elements on the same branch is countable. Such trees were first defined by Mikhail Yakovlevich Suslin. In a Suslin tree, so long as you don’t block any branch twice, you can throw in blockers plugging any open branches anywhere you like and never exceed a countable number. Unlike Aronszajn trees, their existence is independent of ZFC.

A stronger form called the diamond-plus principle () implies the existence of height- trees in which each level is at most countable, but that unlike still manage to have -many branches. These trees are named for Đuro Kurepa. The principle, which also holds in , says that allowing countably many blockers at each level of suffices to “club” every branch into submission. That is, there exists mapping to countable collections of subsets of such that for all branches there is a club giving:

Recall that already has branches by level . By CH this equals “only” , but is still saying that by picking off just countably many at each level, we can block every one by our analogue of a full-measure subset of . This is consistent, but do we wish to adopt it? More on this can be found in Weaver’s book and various sources including this paper and blog post by Assaf Rinot.

Open Problems

What intuition can we gain from blocking games on infinite trees? Is there any point in favoring set theories that stay closer to our intuitions about combinatorial structures “closer to home”?