Trees and Infinity

With this post I hope to do a little to strengthen readers' (and my) understanding of the mathematics of the infinite (something easy to neglect in the study of resource-bounded computation), while focusing on the discrete infinite structures that arise in computability theory.

In mathematics, a tree is an important kind of structure. It consists of a set of nodes, with one designated the root. Each node has a (possibly empty) set of 'children' (of which it is the parent), and any node is reachable from the root in a unique way by a finite series of steps, where each step takes you from a node to one of its children.

The genealogies of asexual organisms, for example, are naturally describable using trees. An important tree in discrete math is that formed with the finite bitstrings as nodes, where the root is the empty string and where the children of x are x0 and x1. (Exercise: use this tree to exhibit the following, somewhat startling, phenomenon: there exists an uncountable collection of subsets of N, the natural numbers, such that any two subsets have at most a finite intersection.)

This tree on bitstrings is an infinite tree, but it has the nice property of being 'locally finite': every node has only finitely many children. Konig's Lemma (the 'o' in Konig needs an umlaut) asserts that any infinite, locally finite tree contains an infinite path (hopping parent-to-child at each step).

The proof is simple: we build such a path. Start at the root; by the pigeonhole principle, one of the root's children c must itself be the root of an infinite subtree. Hop to c, repeat the same process, ad infinitum.
QED.

This innocuous Lemma is in fact very powerful. I will describe some basic applications.

1) The Compactness Theorem for Propositional Logic: Suppose {F_i} is an infinite family of Boolean functions over x_1, x_2, ..., such that i) each F_i depends on finitely many variables, ii) for each K we can find a setting of the variables that satisfies F_1, F_2, ... F_k (i.e. makes them all equal 1).
Then we can find an assignment satisfying all the F_i simultaneously.

Proof: For any finite bitstring y, say of length j, interpret y as an assignment to x_1, ... x_j. Say y is in T if there is no particular F_i that y has already forced to output 0.

T is clearly a tree, and locally finite. If it has an infinite path, that path describes an assignment satisfying all of {F_i}. So assume it does not. But then, by the contrapositive form of Konig's Lemma, T must be finite, say with no node representing a bitstring of length K or more.

This means that for any length-K bitstring y, there is some formula F_{i[y]} forced to be 0 by setting x_1 ... x_K = y.

How, then, can one find any assignment to x_1, x_2, ... that satisfies all of the finite set of formulas {F_{i[y]}: |y| = K } ? One cannot. This contradicts the assumptions of the Theorem, completing the proof.
QED.

Here's a nice application of the Compactness Theorem:

2) show that the 4-color Theorem of graph theory holds even for infinite planar graphs, as long as each graph node is of finite degree. (Assume the finite 4-color Theorem is valid. Or, hey, don't...)

Konig's Lemma or The Compactness Theorem can each yield a simple proof (exercise!) of the following 'query complexity'-type result:

3) Suppose f is a Boolean function on x = x_1, x_2, ... Say whenever f(x) = b, for b = 0 or 1, there is a finite subset of the variables which force f to equal b.
Then f in fact only depends on finitely many variables.

This result is redolent of the statement 'REC = RE intersect coRE' in computability. It also has an analogue in a more finite setting--a kind of moral equivalent of 'P = NP intersect coNP' in query complexity--which I invite readers to discover or ask about.

It's interesting to wonder to what extent Konig's Lemma can be 'constructivized'. Let D be an infinite subtree of the prefix-tree over finite strings (as described above). Suppose membership in D is computable. Say infinite string s refines D if all of its finite prefixes are in D.

4) Is it necessarily the case that for such D there is a computable s refining D? (Hint: Diagonalize.)

4.5) If the sequence of functions from the Compactness Theorem (1) is a computable one, is there a computable assignment to x_1, x_2, ... satisfying every function?

5) What if, in 4, there is an additional guarantee that only countably many s refine D?

For readers interested in Kolmogorov complexity, the following somewhat challenging result rewards similar tree thinking:

6) Suppose that for some infinite string s there is a constant C such that for all n, there is a Turing machine M_n which, on input n, outputs the length-n prefix of s.
Then s is computable. (The converse is easy.)
(Source for 6: the gorgeous Li-Vitanyi book on Kolmogorov complexity.)

Addendum: I just found a good source for further material related to 4-5 and other aspects of 'recursive (infinite) combinatorics': Bill Gasarch's chapter in the hefty Handbook of Recursive Mathematics, Vol. II.

Shifting quite a bit now, I'd like to briefly describe a nice probabilistic result about infinite genealogical trees. Consider an idealized asexual organism in an idealized environment. Each individual alive at time t (an integer) gives birth to some number (possibly zero) of offspring, whose number is determined by the outcome of a random variable X. Then the individual dies as we enter time t+1. Each new individual's reproduction is governed by the outcome of an independent copy of X (so, just because your parent had reproductive success doesn't make you more likely to).

X could be very complicated. But it turns out that the expectation E(X) is still quite powerful in understanding the population dynamics: if E(X) is less than 1 then an eventual extinction occurs with probability 1, while if E(X) is greater than 1 then extinction happens with probability less then 1, and conditioning on the event that extinction does not occur, then with probability 1 the population size goes to infinity rather than oscillating indefinitely.
The proofs I've seen of these results are generatingfunctionological. Are there more 'natural' proofs out there? Or a relation to Konig's Lemma?


I should note that real trees are worth thinking about too. I would recommend the site Carbonfund.org as what seems to be the most well-run and cost-effective place to buy carbon credits, reducing global warming and deforestation. $55 will offset 10 tons of CO2, a significant chunk of the direct yearly impact of an average American.
P.S. Anyone who uses PayPal for this kind of thing should be aware of the fraudulent emails sent by PayPal impersonators to solicit credit card numbers.

Finally, for a more soulful/whimsical take on trees and the infinite you might check out Calvino's novel The Baron in the Trees. (Thanks, Chaya!)