Skip to content

A Game On Infinite Trees

December 16, 2015


An independent principle in set theory

RonaldJensen
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}.

B1blockingW
    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”?

 

6 Comments leave one →
  1. Paul Beame permalink
    December 17, 2015 11:17 am

    This brings back memories – though not exactly happy ones – of a class on infinitary combinatorics I took in 1981. There were a few more principles/properties named after card suits that I don’t remember. It was a grad class with only two students, both of us undergrads and both out of our depth. (We had been encouraged to take it after a previous model theory course, which the other student ended up going to grad school to study. I was seduced by automata theory that term, which led me to an abrupt switch into computer science.) The recommended text was Devlin’s Fundamentals of Contemporary Set Theory which didn’t seem to help at all. I wish it had been taught using the intuitions you give here but I still doubt I would have enjoyed it…

  2. December 18, 2015 2:41 am

    Regarding the second open question: One notable example of a proof that applies both in the finite and infinite case is the diagonal proof that 2^n >n for every cardinal n. I ‘d love to learn some additional examples. Of course there are many examples where statements and proofs about infinite combinatorics (or mathematics) inspired developments in finite combinatorics (mathematics) and also examples in the opposite direction. I vaguely remember that the concept of “non determinism” in computation started in the infinite case (but I may be wrong) and also I remember that Mike Sipser’s lower bound for bounded depth circuits started from infinite statement.

  3. December 18, 2015 4:08 pm

    THE P VERSUS NP PROBLEM

    We define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP–complete}$ problem $\textit{SUBSET–PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent and large instances of $\textit{SUBSET–PRODUCT}$. Moreover, we show $MAS \in \textit{NP–complete}$.

    In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, because all currently known $\textit{NP–complete}$ are $\textit{NP–complete}$ under logarithmic-space reduction including our new problem $MAS$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou’s book is proved the following statement: “$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input”. Since $MAS$ is a succinct version of $\textit{SUBSET–PRODUCT}$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, then we obtain that $MAS$ should be also in $\textit{EXP–complete}$.

    Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.

    You could see more on (version 3)…

    https://drive.google.com/file/d/0B3yzKiZO_NmWZ1M1MkNuYVBreXc/view?usp=sharing

    Best Regards,
    Frank.

  4. Paul Beame permalink
    December 21, 2015 9:15 pm

    vegafrank: A succinct version of an NP-complete problem is not in NP (let alone P) because the supposed NP-witness for the problem would in general need to be exponentially longer than the succinct input. The approach that you are trying cannot possibly work.

  5. December 24, 2015 3:39 pm

    Paul: I hope you can understand better what I mean with a succinct version of the NP-complete $\textit{SUBSET–PRODUCT}$ in my new version of my work, regards…

    P VS NP

    We define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP–complete}$ problem $\textit{SUBSET–PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent large instances of $\textit{SUBSET–PRODUCT}$. Moreover, we show $MAS \in \textit{NP–complete}$.

    In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, because all currently known $\textit{NP–complete}$ are $\textit{NP–complete}$ under logarithmic-space reduction including our new problem $MAS$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou’s book is proved the following statement: “$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input”. Since $MAS$ is a succinct version of $\textit{SUBSET–PRODUCT}$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, then we obtain that $MAS$ should be also in $\textit{EXP–complete}$.

    Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.

    You could see more on (version 4)…

    https://drive.google.com/file/d/0B3yzKiZO_NmWa2xjUlhmeDRUVkU/view?usp=sharing

    Best Regards,
    Frank.

  6. January 3, 2016 12:52 pm

    Paul, you are certainly right. It is impossible that a succinct problem of some NP-complete language would be in NP-complete, because it will be in NEXP-complete. Thanks a lot for your help.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s