[FOM] The boundary of objective mathematics

Vaughan Pratt pratt at cs.stanford.edu
Wed Mar 18 21:27:57 EDT 2009

```
W. Mueckenheim wrote:
> When I represent all the real numbers of the unit
> interval by the paths of an infinite binary tree
> with a countable number of nodes, every student
> understands that there cannot be not more paths
> than nodes (because it is really not hard to
> understand that argument).  No student of mine has
> ever argued against that, although that would not
> have changed her marks! So we see Weyl's
> statement approved: Actual infinity cannot be treated free of contradictions.

(Presumably the double negation in "there cannot be not more paths than
nodes" was unintentional, otherwise what would be the contradiction?)

One can argue directly that there are 2^N paths and N nodes, but perhaps
the direct argument is not the best way of contradicting your "it is
really not hard to understand that argument" since your goal is to point
up an inconsistency in mathematics with what purports to be an obvious
argument.  Here are three objections that can be raised, all based on
finitary considerations, that make it really hard to understand your
argument.

1. In the finite case, each node at depth d from the root of a tree of
height h participates in 2^(h-d) paths.  As h increases that node
participates in an exponentially growing number of paths.  Therefore in
the limit each node participates in 2^N paths.  Now you might say, oh,
but there are twice as many new nodes at every height increment.  So
then we have to ask whether this is enough node growth at depth h to
offset the exponentially growing number of paths shared by one node at
depth d.  In the limit each path is shared between N nodes, but that
still leaves 2^N/N paths per node, which cannot be N because N^2 is
countable and 2^N is not.

2. Since the infinite case does not count the leaves (there being none),
it would be misleading to count them in the finite case if we want
insight into what happens at infinity.  For trees of height h we find a
cardinality gap: 2^h - 1 interior nodes vs. 2^h paths.  Why should
passing to the limit close this gap?

3.  Every pair of nodes is connected by a finite path, whereas every
pair of paths has in common only finitely many nodes and they differ by
infinitely many nodes.  Therefore any comparison of nodes to paths is an
apples-to-oranges comparison for which it would very surprising to find
a bijection between them.

Vaughan Pratt
```