Re: The complete infinite binary tree has only countably many infinite paths.
- From: Virgil <Virgil@xxxxxxxxx>
- Date: Sat, 28 Mar 2009 13:50:27 -0600
In article
<807b8cca-e356-4e57-87a2-c9fb887d8b26@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
LudovicoVan <julio@xxxxxxxxxxxxx> wrote:
On 28 Mar, 12:29, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Fri, 27 Mar 2009 13:26:20 -0700 (PDT), LudovicoVan
<ju...@xxxxxxxxxxxxx> wrote:
On 24 Mar, 11:56, WM <mueck...@xxxxxxxxxxxxxxxxx> wrote:
The complete infinite binary tree has only countably many infinite
paths.
Absolutely!
not.
When the nodes are countable, how could the paths be not?
"How could they not be?"
Thanks for the correction, appreciated.
is not a proof of anything.
Indeed, it's even straightforward that there is a bijection between
the paths and the leaf nodes...
Huh? In the tree in question there are _no_ leaf nodes.
That's informal and, as such, I believe it's quite correct: easy to
see by graphical means, but you guys tend to deny any graphical
approach.
Since a "graphical approach" would require graphs with infinitely many
edges, one certainly would not want to try drawing them.
But! If you (or anybody) give a _transfinite definition_ for the
complete infinite binary tree (i.e., as near as possible to a
"constructive recipe"), then -I'll claim- giving the mentioned
bijection in formal terms is going to be trivial...
To start with a graphical approach, let each positive natural represent
a node in the tree with the start of the tree looking like
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
9 10 11 12 13 14 15 16
/ \ / \ / \ / \ / \ / \ / \ / \
Then number of the left child node of node n is 2*n + 0 and
the number of the right child node of node n is 2*n + 1.
Thus every infinite path (starting at the root node and never ending)
can be represented by an infinite sequence of ever larger naturals
starting with 1 and with the successor to each node n of form
2*n+ 0 or
2* n + 1.
But then, every path can equally be specified by the directions of its
successive branchings,
0 for each n to 2*n+0 branch and
1 for each n to 2*n+1 branch.
Thus we man "identify" each path (special set of naturals) with a unique
infinite binary sequence of 0's and 1's and vice versa.
And we see that every possible such binary sequence corresponds to a
path with different sequences corresponding to different paths.
We now have the problem of whether there is any way to map the naturals
to the binary sequences so that
(1) no natural is used more than once, and
(2) every binary sequence is used at least once.
He Cantor "diagonal" proof for binary sequences shows that the two
conditions cannot both be satisfied simultaneously.
.
- Follow-Ups:
- References:
- The complete infinite binary tree has only countably many infinite paths.
- From: WM
- Re: The complete infinite binary tree has only countably many infinite paths.
- From: LudovicoVan
- Re: The complete infinite binary tree has only countably many infinite paths.
- From: David C . Ullrich
- Re: The complete infinite binary tree has only countably many infinite paths.
- From: LudovicoVan
- The complete infinite binary tree has only countably many infinite paths.
- Prev by Date: Re: The complete infinite binary tree has only countably many infinite paths.
- Next by Date: Re: The complete infinite binary tree has only countably many infinite paths.
- Previous by thread: Re: The complete infinite binary tree has only countably many infinite paths.
- Next by thread: Re: The complete infinite binary tree has only countably many infinite paths.
- Index(es):
Relevant Pages
|
