In article <9b9b4efc-4e5f-42df-a1ce-669f029333d2@hj4g2000vbb.googlegroups.com>, WM <mueckenh@rz.fh-augsburg.de> wrote:
> On 31 Okt., 11:28, Gus Gassmann <horand.gassm...@googlemail.com> > wrote: > > On Oct 31, 7:01 am, Brian Chandler <imaginator...@despammed.com> > > > > > > Well, WM's argument looks much like "Any set including an infinite > > > number of integers must include an infinite integer", which is > > > obviously false, > > as obviously as the assumption of a finished infinite set. > > > but could you sketch an example of a binary tree with > > > infinitely many nodes and no infinite path? > > > > That would be the tree that WM gives as an alternative. The nodes are > > numbered as follows: > > > > 0 > > 1 2 > > 3 4 5 6 > > ... > > > First, this is not an alternative. Every proof of the countability of > the set of nodes proceeds in this way and every Binary Tree carries > this structure in addition to the numerical values ascribed to the > nodes. > Second, this Binary Tree has no path that could not be continued > somewhere.
Any finite binary tree can be "continued", i.e., embedded in a larger binary tree. > > > In the complete binary tree you do, of course, have (only) infinite > > paths, but if you use the nodes above you can define the set of > > (finite) paths whose last (i.e., lowest) edge points to the right. > > They are finite, and they span the tree. Sorted by length, the first > > few are 0 (!), 0-2, 0-1-4, 0-2-6, 0-1-3-8, ...- Zitierten Text ausblenden - > > Same is true for the complete Binary Tree (simply because it does not > differ from the node-structure given above).
Any binary tree has finite sub-paths, but a complete infinite binary tree does not have any finite paths. Any such path must have either infinitely many left branchings or infinitely many right branchings, and "most" have both ( only countably many out of uncountably many can have a finite number of either).
> > The complete Binary Tree contains also the paths 0, 0-1, 0-1, 0-0-0, > 0-0-1, and so on until 0-1-1-1-...
A "complete" binary tree" that has a 1-node path has only 1 such path and one node.
A "complete" binary tree" that has 2-node paths has 3 nodes and 2 paths. A "complete" binary tree" that has 3-node paths has 7 nodes and 4 paths. A "complete" binary tree" that has n-node paths has 2^n-1 nodes and 2^(n-1) paths. A "complete" binary tree" that has endess paths has Aleph_0 nodes and 2^Aleph_0 paths.
For every finite tree, the number of paths is equal to the number of terminal nodes, but in a tree with nodes but without terminal nodes, this pattern necessarily fails. --
