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”?
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…
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
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.
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.
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.
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.
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.