[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


More information about the FOM mailing list