A subtle distinction in math is that between infinitely large things and arbitrarily large things. Suppose we have a set of elements, and each element has some “size”, where the sizes are allowed to range over the nonnegative numbers along with “infinity”. If one of the elements does happen to be infinite, then that implies that the set has arbitrarily large elements, in a trivial sense. The converse does not hold, though: the set might have entries which are arbitrarily large, and yet none which are outright infinite.

Example 1: The Real Numbers

Every real number has a size, namely, its absolute value. Now, it’s true that the set of real numbers contains arbitrarily large numbers. Given any possible finite size, there is a real number whose size is bigger. The set of reals does not, however, have any infinite element. There is no individual number whose size is infinity.

Example 2: The Real Intervals

A real interval is a set X of real numbers with “no gaps”, that is, it must have the property that if it contains two points x and y, then it also contains everything between x and y. The set of all real intervals does contain something with infinite size: the whole real line itself, for example, is a real interval (it has no gaps), so is an element of the set of all real intervals, and it certainly has infinite size.

These two examples are kind of silly and trivial, but the next one is more subtle and seems to cause a lot of confusion.

Example 3: Branches in a Tree

Given a mathematical tree, a branch is a sequence of nodes, starting with the root, such that each node in the sequence (except for the first one) is a child of the previous node. A priori, branches are allowed to be infinitely long, but for a specific tree, there may or may not exist an infinite branch.

If the tree itself is finite, then immediately it cannot have an infinite branch, nor can it have arbitrarily long branches. No branch can contain more nodes than the tree itself contains.

People often fall prey to the trap of thinking that if a particular tree does have arbitrarily long branches, then voila, it must have an infinite branch. This is not true. The following tree is a counterexample:

The root in this tree has infinitely many children. The root’s first child has no children. The root’s 2nd child has a child and no further descendants. The root’s 3rd child has a child and a grandchild and no deeper descendants. And so on. If you cut the root, the graph breaks into infinitely many finite graphs. The tree has no infinite branch. Such a branch would have to begin with the root, and then go to some child of the root, and then pass through infinitely many descendants of that child. But each child of the root has only finitely many descendants, so no can do. On the other hand, the tree does have arbitrarily long branches.

Konig’s Lemma provides a sufficient condition for a tree to have an infinite branch. It says that if a tree is infinite, and every node has only finitely many children, then there’s an infinite branch. The theorem confuses some people, who assume it’s absolutely trivial because they equate “tree has arbitrarily long branches” with “tree has an infinite branch”. BTW, the tree above fails the hypotheses of Konig’s Lemma because the root has infinitely many children.

The Topping Game

Here’s a way to intuitively test whether a set has an infinite element. Fix a set S of things which have sizes ranging among the nonnegative integers and maybe “infinity”. Let’s play a little game. In this game, you pick an element from S, and then I try to pick a bigger element. If I manage to pick a bigger element, I win. If not, you win.

If S contains something with infinite size, then you have a winning strategy. Namely, pick something with infinite size. I can’t pick something bigger, because the biggest thing I can possibly pick would be another size “infinity” thing. I’m beaten.

If S contains arbitrarily large things, but nothing with size infinity, then I have a winning strategy. Namely, watch what you pick, and then pick something bigger. I can do this because there are arbitrarily big things, and the thing you picked was finite size, hence cannot be a bound on the sizes of everything else, or else they wouldn’t be arbitrarily big.

If S contains neither arbitrarily large things nor infinite things, then you have a trivial winning strategy: pick something with maximum size.

Advanced Example: Sets Within Sets

One of the axioms of ZFC, the Axiom of Foundation, implies that you can’t find an infinite sequence s1, s2, …, such that each si+1 is an element of si. In other words, you can’t find an infinite chain of sets-within-sets. So a class of sets (satisfying ZFC) does not have such infinite chains. But any such class does have arbitrarily long chains of sets-within-sets. For example: 0 is inside {0} is inside {{0}} is inside {{{0}}} is inside… (repeat the process any finite number of times).

What happens if we try to repeat this process infinitely often? Start with 0, then go to {0}, and keep going, adding on infinitely many new braces on each side. If this resulted in a set, say X={{{…{0}…}}}, where the … indicate infinitely many omitted brackets, then X would have the property that X={X}, and hence, X would be an element of itself, which violates the axiom of foundation.

In this example, things get really bizarre when we start playing with the Compactness Theorem.

Take the language L of ZFC and add a new constant symbol, s. Now take the ZFC axioms and add a bunch of new axioms in the extended language: “s is an infinite sequence”, “s(0) contains s(1)”, “s(1) contains s(2)”, … Call this extended axiom system ZFC+. The Compactness Theorem says that if a set of sentences has the property that every finite subset of those sentences is satisfied by a model, then the entire set of sentences has a model. If we take a finite subset of the axioms in ZFC+, then since it’s finite, it only contains finitely many of the “s(i) contains s(i+1)” axioms. Hence, it’s satisfiable. By the compactness theorem, ZFC+ itself is satisfiable and has a model.

This means there is a model of ZFC– satisfying the Axiom of Foundation and all– containing an infinite sequence s such that s(0) contains s(1) contains s(2) contains … forever. Isn’t this a paradox?

The thing is, we can see that this perverse model of ZFC contains an infinite chain of sets-within-sets, but the model itself cannot see it. We specified that s(i) contains s(i+1) for i=0,1,2,…, that is, for i ranging over the standard natural numbers. The strange model yielded by Compactness Theorem must contain nonstandard natural numbers– or else the sequence s would break the Axiom of Foundation. This model contains natural numbers which are bigger than all the “standard” natural numbers, but in the model’s eyes, these nonstandard naturals are still finite. (In order for the model to see that one of the nonstandard naturals is infinite, the model would have to contain a function which injects the model’s copy of the natural numbers into that number, and this is impossible)

This provides an example where, externally and metamathematically, we can see an infinite chain within a model, but if we work within that model itself, then we only see arbitrarily long chains and no infinite one.


Konig’s Lemma
The Higher Infinite
Goodstein Sequences