A Game On Infinite Trees

December 16, 2015

tags: continuum hypothesis, diamond principle, games, Ronald Jensen, set theory, 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 ${\diamondsuit}$ . 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 ${B_0}$ of depth ${\omega}$ has countably many nodes and levels but uncountably many branches, indeed ${2^{\aleph_0}}$ of them. As usual ${\aleph_0}$ denotes the cardinality of the natural numbers but ${\omega}$ 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 ${\aleph_{0}}$ tree ${T_0}$ , is not too hard to imagine. Say a node is at level ${\ell}$ if it is ${\ell}$ 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 ${\aleph_{0}}$ tree.

Now the next larger cardinal after ${\aleph_{0}}$ is denoted by ${\aleph_{1}}$ . 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

$\displaystyle \aleph_1 = 2^{\aleph_{0}}.$

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

This tree ${T_1}$ 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 ${\aleph_{0}}$ tree.

We can come halfway by imagining trees ${T}$ whose nodes are bounded sets of nonnegative rational numbers. Here ${S}$ is a descendant of ${R}$ if ${R \subset S}$ and every member of ${S \setminus R}$ is greater than the supremum of ${R}$ . We can control which sets are added to ${T}$ by transfinite recursion and create ${\aleph_1}$ levels—one for every countable ordinal—but with only ${\aleph_0}$ -branching since the children of ${R}$ append just one rational ${q > \sup(R)}$ . Stranger still, although ${T}$ has ${\aleph_1}$ levels, each individual branch can only be countable since ${\mathbb{Q}}$ is countable. For contrast, our complete ${\aleph_1}$ -tree ${T_1}$ does have ${\aleph_1}$ -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, ${T_0}$ and ${T_1}$ . 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- ${\aleph_{0}}$ 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 ${\frac{1}{\aleph_{0}}}$ , i.e., zero. Now repeat this ${\aleph_{0}}$ times and we should get that the chance of being blocked is

$\displaystyle 1 - (1 - \frac{1}{\aleph_0}) \times (1 - \frac{1}{\aleph_0}) \times \cdots$

with multiplication a countable number of times. This is zero. But wait. We cannot just treat ${\aleph_{0}}$ like a number. Or can we?

The trouble is the use of ${\frac{1}{\aleph_{0}}}$ 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 ${i}$ let’s restrict the blocker to use only a fixed set of ${m_{i}}$ nodes. Now at level ${i}$ the chance the random path hits a marker at the next level is ${\frac{1}{m_{i+1}}}$ . So the probability that avoids all markers is

$\displaystyle \prod_{i=1}^{\infty} \left(1-\frac{1}{m_{i+1}} \right).$

It is easy to see that if we make ${m_{i}}$ 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

$\displaystyle \sum_{i=1}^{\infty} \frac{1}{m_{i+1}}.$

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

Blockers in Binary Trees

Before we look at the complete ${\aleph_{1}}$ tree, let’s consider the complete binary tree ${B_1}$ with ${\aleph_{1}}$ levels having order type ${\omega_1}$ . Then every branch of ${B_1}$ is a subset ${D}$ of ${\omega_{1}}$ . Every level corresponds to some ordinal ${\alpha < \omega_1}$ and every node at that level is a subset ${A_{\alpha}}$ of ${\alpha}$ —recall that ${\alpha}$ can be identified with the set of ordinals below ${\alpha}$ . A set that consists of one node at each level above the root is therefore the same as a function ${f}$ from ordinals ${\alpha > 0}$ to sets ${A_{\alpha}}$ .

Now with a binary tree we can readily block all paths on the first ${\omega}$ levels. For ${a}$ with ${0 < a < \omega}$ define ${f(a) = \{a-1\}}$ and ${f(\omega) = \emptyset}$ . Branches that include ${0}$ are blocked in the first step from the root, then branches that include ${1}$ but not ${0}$ are blocked at the next step, and so on. Finally, branches that exclude all finite ordinals are blocked at level ${\omega}$ . 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 ${\omega}$ .

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 ${f}$ blocks all branches past that point is:

$\displaystyle (\forall D \subseteq \omega_1)(\exists \text{ infinite }\alpha)[f(\alpha) = D \cap \alpha]. \ \ \ \ \ (1)$

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 ${2^{\aleph_0}}$ independent paths from the get-go and are purporting to cover them with only ${\aleph_1}$ blockers. Jensen’s original statement of ${\diamondsuit}$ is equivalent to the existence of such an ${f}$ but tells us even more: we can block all branches uncountably many times in a particularly “thick” manner.

The Diamond Property

A set ${C}$ of countable ordinals is unbounded if for all ${\alpha < \omega_1}$ there exists ${\gamma \in C}$ such that ${\alpha < \gamma}$ . It is closed if whenever ${\gamma}$ is the limit of a subsequence and ${\gamma < \omega_1}$ we have ${\gamma \in C}$ . 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 ${[0,1]}$ or ${\{0,1\}^{\omega}}$ . 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 ${\diamondsuit}$ from section 6 of Jensen’s paper does not need to constrain ${f(\alpha)}$ for finite ${\alpha}$ . His sequence notation ${A_{\alpha}}$ in place of ${f(\alpha)}$ makes ${A_{\alpha} \subseteq \alpha}$ easier to stipulate. It is:

$\displaystyle (\exists [A_{\alpha}])(\forall D \subseteq \omega_1) : \{\alpha: A_{\alpha} = D \cap \alpha\} \text{ is stationary}. \ \ \ \ \ (2)$

Another interpretation of ${\diamondsuit}$ is that as we are traveling up the tree through each level ${\alpha}$ the function ${f(\alpha) = A_{\alpha}}$ represents a “prediction” of exactly what and where some branch will be at time ${\alpha}$ . Then the principle says that a single ${f}$ 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 ${\aleph_1}$ tree ${T_1}$ . The blocking strategy at finite levels of ${B_1}$ is blown away by the immediate ${\aleph_1}$ -branching, though at level ${\omega}$ we still have ${\aleph_1^{\aleph_0} = 2^{\aleph_0}}$ branches. Can ${T_1}$ be blocked by one node at each level? Each node at level ${\alpha}$ is now a function ${g: \alpha \rightarrow \omega_1}$ , not a subset of ${\alpha}$ . A branch is a function ${h: \omega_1 \rightarrow \omega_1}$ .

The potential winning strategies of our blocking game on ${T_1}$ are functions ${f: \omega_1 \rightarrow V(T_1)}$ such that ${f(\alpha)}$ is a node on level ${\alpha}$ . This means a binary function ${f: \omega_1 \times \omega_1 \rightarrow \omega_1}$ but restricting ${f(\alpha,\beta)}$ to be defined only when ${\beta \leq \alpha}$ . Again the sequence notation ${[g_{\alpha}]}$ is traditional and clearer, so we use it to state the form of ${\diamondsuit}$ given in Weaver’s book:

$\displaystyle (\exists [g_{\alpha}])(\forall h: \omega_1 \rightarrow \omega_1) : \{\alpha: g_{\alpha} = h |_{\alpha}\} \text{ is stationary}. \ \ \ \ \ (3)$

Is ${T_1}$ harder to block than the ${\omega_1}$ -binary tree ${B_1}$ ? It seems yes but the answer is no: this form of ${\diamondsuit}$ is equivalent to the original. Roughly the reason is that ${\aleph_1^{\aleph_1} = 2^{\aleph_1}}$ so ${T_1}$ and ${B_1}$ have the same number of branches, and ${\aleph_0^{\aleph_0} = 2^{\aleph_0}}$ 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 ${\mathsf{L}}$ . 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 ${\mathsf{L}}$ as a ‘true’ model of set theory. We examine a couple more consequences and principles.

Saturation Blocking?

Suppose we have ${f}$ such that (2) holds. Let ${R}$ be the subtree of ${B_1}$ or ${T_1}$ that includes each branch up to the first point at which it is blocked. Then ${R}$ still has ${\aleph_1}$ levels, but every branch of ${R}$ 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 ${\diamondsuit}$ for this kind of tree—ZFC suffices to build our ${T}$ defined above: At a limit ordinal ${\beta}$ , for each existing node ${R}$ and rational ${q > \sup(R)}$ , choose one branch of the previously existing tree that contains ${R}$ and has supremum ${q}$ , and let level ${\beta}$ 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 ${\mathbb{Q}}$ while keeping each level countable.

However, ${\diamondsuit}$ also implies the existence of a tree having ${\aleph_1}$ 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 ( ${\diamondsuit^+}$ ) implies the existence of height- ${\omega_1}$ trees in which each level is at most countable, but that unlike ${T}$ still manage to have ${\aleph_2}$ -many branches. These trees are named for Đuro Kurepa. The ${\diamondsuit^+}$ principle, which also holds in ${\mathsf{L}}$ , says that allowing countably many blockers at each level of ${B_1}$ suffices to “club” every branch into submission. That is, there exists ${f}$ mapping ${\alpha}$ to countable collections ${{\cal A}_{\alpha}}$ of subsets of ${\alpha}$ such that for all branches ${D}$ there is a club ${C}$ giving:

$\displaystyle (\forall \alpha \in C)[C \cap \alpha \in {\cal A}_{\alpha} \wedge D \cap \alpha \in {\cal A}_{\alpha}].$

Recall that ${B_1}$ already has ${2^{\aleph_0}}$ branches by level ${\omega}$ . By CH this equals “only” ${\aleph_1}$ , but ${\diamondsuit^+}$ 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 ${\omega_1}$ . 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”?

	Serge on Have Ten Years Brought Us…
	Anon Postdoc on Have Ten Years Brought Us…
	Anees Shah on Global Warming?
	Héctor Corvalán on Have Ten Years Brought Us…
	vznvzn on Have Ten Years Brought Us…
	Héctor Corvalán on Have Ten Years Brought Us…
	vegafrank on Have Ten Years Brought Us…
	Gil Kalai on Have Ten Years Brought Us…
	Have Ten Years Broug… on Unique Games: A Three Act…
	Have Ten Years Broug… on A Nightmare about SAT
	Have Ten Years Broug… on NP too big or P too small…
	Have Ten Years Broug… on Bait and Switch: Why Are Lower…
	Serge on Can Amateurs Solve P=NP?
	talegu on David Hilbert Speaks
	Héctor Corvalán on Can Amateurs Solve P=NP?

a personal view of the theory of computation

A Game On Infinite Trees

Infinite Trees

The Blocking Game

Blockers in Binary Trees

The Diamond Property

The Complete Aleph-One Tree Case

Saturation Blocking?

Open Problems

Leave a Reply Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

A Game On Infinite Trees

Infinite Trees

The Blocking Game

Blockers in Binary Trees

The Diamond Property

The Complete Aleph-One Tree Case

Saturation Blocking?

Open Problems

Share this:

Like this:

Related

Leave a Reply Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter