If you randomly start tracing down the family tree of mankind, you’ll probably reach a dead-end. But if you’re lucky you might avoid dead-ends forever and trace out an infinite chain of descendants. The likelihood of this depends on how prone humans are to spawn offspring: if everyone always has children, then you’ll get an infinite chain guaranteed, but of course this isn’t how things are. If mankind goes extinct then it’s impossible to get an infinite chain because after a certain generation everybody’s dead. But what about the converse: is it possible there could be an alternate universe where mankind doesn’t go extinct, but contains no infinite chains? The answer is no, and the proof uses a profound combinatorial result called Konig’s Lemma.

Trees

Mathematical trees are a bit more simplified than family trees. A tree is a set of nodes. One of the nodes is the root. Every node except for the root has exactly one parent. If node A is the parent of node B then node B is a child of node A. The descendants of A are the children of A, together with their own children, and their grandchildren, and so on. Loops are not allowed: a node is not allowed to be its own descendant. And every node must be a descendant of the root (except for the root itself).

The difference between a mathematical tree and a family tree is, in the mathematical tree, people (nodes) only have one parent. Essentially, the mathematical tree is a family tree for a species which reproduces asexually. The reason for this is it’s a lot easier to prove things about asexual trees. We’ll see below that the theorems we get for mathematical trees can often be tweaked for family trees, so nothing is really lost.

The generations of a tree are defined exactly how you’d think. The first generation is the set consisting solely of the root. The second generation is the set of children of the root; the third generation is the set of children of nodes in the second generation… and in general, the (k+1)th generation is the set of children of nodes in the kth generation. In the literature, a more common synonym for generation is level, and sometimes the counting starts at 0, so that the root is said to be at level 0 and its children at level 1. “A rose by any other name…”

Konig’s Lemma

Let T be a tree. If T is infinite but every generation is finite, then T contains an infinite descending chain of children.

Proof. We’ll construct an infinite chain n1n2n3… inductively in such a way that every nk+1 is a child of nk.

First, let n1 be the root of the tree. Note that n1 has infinitely many descendants, because the whole tree is infinite by assumption, and everything (except the root itself) is a descendant of the root.

Now, inductively, suppose we’ve defined n1n2…nk, each one a child of the previous, and such that nk has infinitely many descendants. I’ll show how we can define nk+1, a child of nk, itself with infinitely many descendants.

Let c1,c2,…,cn be the children of nk (nk must have at least one child since it has infinitely many descendants). I’m using the fact here that nk only has finitely many children, and that’s true by the assumption that every generation of T is finite (if nk had infinitely many children, that would make a whole infinite generation).

I claim that at least one of the ci‘s has, itself, infinitely many descendants. The proof is by contradiction: assume c1,c2,…,cn each have only finitely many descendants. Add finitely many finite numbers, and the result is finite: thus nk has only finitely many descendants-of-children. Together with the finitely many children themselves, nk has only finitely many descendants. But we assumed we’d chosen nk to have infinitely many descendants, so this is a contradiction, and my claim must be true.

So, take one of the ci with infinitely many descendants, and pick it as nk+1.

Inductively, this defines a whole infinite sequence n1n2… which goes on forever with each node the parent of the next. In other words, an infinite descending chain of children. QED.

Application to Family Trees

In real life, people have two parents, not one. We can convert mankind’s family tree into a mathematical tree by systematically erasing one parent from every mother-father pair. For example, we could erase all females, and have each person count only as a descendant of their father: sort of like a medieval European throne-room. Or we could ignore males, counting only mothers as parents. We aren’t really erasing these people in real life, only erasing their names from the family tree, to turn it into a mathematical one.

Assume mankind never goes extinct: there is always an nth generation, for every n>0 (see note 1). Assume nobody has infinitely many children.

I claim there is an endless chain of people, each one a parent of the next: an infinite chain of progeny.

Proof: Turn the family tree into a mathematical tree– say, by erasing females. Now “parent” becomes synonymous with “father” (this might alter what generations people belong to, but the assumption that no father has infinitely many children, ensures the generations are still finite). The “root” (which previously was the matriarch-patriarch pair) is now just the patriarch and the matriarch is banished. The tree is infinite: otherwise, only finitely many generations would be witnessed. By Konig’s Lemma, the tree has an infinite descending chain of children. And this infinite chain of kids translates back into the original, non-mathematical family tree, completing the proof.

In fact, we proved something stronger than we needed: not only is there an infinitely descending chain of children, but we can find such a chain which is all male.

Identical reasoning would also yield an infinite chain of children of all female gender: instead of ignoring females, ignore males.

Here’s a challenge-question for the reader. Is it true, that in every alternate universe where mankind never goes extinct, that you can always find an infinite chain of children which alternates male-female-male-female forever?

Application to Games

Suppose a game has infinitely many possible configurations– for example, a game of Chess on an infinite board. But assume at any particular point in the game, there are only finitely many moves available– for example, infinite-board Chess with only finitely many pieces. Then it is possible to play the game forever without ever hitting the same configuration twice.

(In the infinite chess game, this is obvious: both players can simply move their rooks sideways forever and ever in the same direction. But the application works for all games which meet the assumptions)

Proof: Create a tree as follows. Nodes correspond to configurations of the game. The root is the initial configuration. Now, inductively, for each node N we’ve already defined, N being a game configuration, and for each possible game configuration M, add M as a child of N if and only if two criteria are met:

  1. M hasn’t already been added to the tree yet
  2. It’s possible to go from configuration N to configuration M in one move

The fact that we assumed there are only finitely many legal moves at any given time, ensures that no node has infinitely many children; it follows that every generation is finite. The tree itself is infinite: every one of the possible configurations can be reached by following a finite number of moves from the initial configuration– this is the definition of “possible”– and thus will be added as a child to the corresponding configuration right before it– assuming it hasn’t been added even earlier by some other series of moves.

By Konig’s Lemma, there is an infinite branch through this tree. You can “play” this branch, because each configuration follows from the previous one by a legal move in the game (criteria 2). You’ll never hit the same configuration twice, because criteria 1 ensures no configuration appears twice in the tree, hence in the infinite branch. So the theorem is proved.

The Nonconstructive Nature of Konig’s Lemma

In the proof of Konig’s Lemma, we create an infinite branch inductively, using reductio ad absurdum at every step except the first. A proof by contradiction, proving that some choice works, gives us no clue about which choice works. In a sense, if we’re confused once by once proof by contradiction, then Konig confuses us infinitely often, and the infinite branch is infinitely nonconstructive (but this is handwavey and not actually a formal statement).

In some alternate universe, the root of mankind is named Adam and his sons are named Cain and Abel. Konig assures us that at least one of Cain or Abel will have infinitely many descendants (or mankind will go extinct). We have no idea which one.

Notes

1. In a non-mathematical family tree, “generation” isn’t very well-defined, because it’s possible for a person’s two parents to come from two different generations. For the sake of making everything well-defined, you can say that a person whose mother and father are generation x and y, is generation max(x,y)+1. Assume no John Connor time-travel paradoxes ;)

2. The form I gave here is a special case of the full Konig’s Lemma, which is a statement about more general graphs which don’t have to be trees.

FURTHER READING

Goodstein Sequences
Additive Geometric Patterns of Resemblance
Is Summation Notation Ambiguous?