| View previous topic :: View next topic |
| Author |
Message |
WM
Guest
|
 Posted: Mon Oct 06, 2008 6:25 pm Post subject: Binary Tree and Pairs of Nodes |
 |
|
A path in an infinite binary tree is the representation of a real
number of the interval [0, 1]. (Terminating rational numbers have two
representations each.)
Two paths A and B in the infinite binary tree can be distinguished by
at least one pair of nodes a and b where a belongs to A but not to B,
and b belongs to B but not to A.
Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
Conclusion: The number of paths is not larger than the number of
nodes. The number of nodes is countable. As the number of paths is not
less than the number of reals in the interval [0, 1], the number of
reals in the interval [0, 1] is countable.
Or: The assumption is wrong. There are at least two pairs of paths
that cannot be distinguished by different nodes.
Regards, WM |
|
| |
|
 Back to top |
MoeBlee
Guest
|
| Posted: Mon Oct 06, 2008 10:12 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 6, 11:25 am, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]A path in an infinite binary tree is the representation of a real
number of the interval [0, 1]. (Terminating rational numbers have two
representations each.)
Two paths A and B in the infinite binary tree can be distinguished by
at least one pair of nodes a and b where a belongs to A but not to B,
and b belongs to B but not to A.
[/quote]
Yes, if p and p' are different paths, then there exist nodes n and n'
such that n is on p but not on p' and n' is on p' but not on p.
And I suppose that below by 'distinguishing pair of nodes'' you mean a
pair of nodes with regard to a path such one node is on the path and
the other node is not on the path.
[quote]Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
[/quote]
I don>t know what you>re trying to say by 'used to distinguish another
pair of paths' or by that with the rest of your assumption above.
But the following holds:
If p and p' are different paths, then there is a unique node n such
that n is on both p and p' and such that all nodes at levels less than
the level of n are such that either (1) both p and p' are on it or (2)
neither p nor p' are on it, and all nodes at levels greater than the
level of n are such that it is not the case that both p and p' are on
it.
[quote]Conclusion: The number of paths is not larger than the number of
nodes.
[/quote]
You>ve not given any logic of argument by which you derive your
conclusion.
Please state your axioms, system of logic (and language syntax if
different from ordinary first order language), and the argument for
your conclusion.
MoeBlee |
|
| |
|
| Back to top |
george
Guest
|
| Posted: Mon Oct 06, 2008 10:42 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 6, 2:25 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
[/quote]
Your "no node" is incorrect. You meant "neither node" or "that pair"
of nodes.
In any case, the assumption is obviously false.
Consider
01000000000000000000... versus
10000000000000000000....
You could distinguish these either at the pair of nodes closest to the
root,
or at the inner pair one level down, but obviously,
011111111111111111111... and
101111111111111111111... can ALSO be distinguished ONLY
at those two positions. You could insist that this is not yet a
counterexample by
distinguishing the first (0000>s) pair of strings at the first level/
position,
and the second (1111>s) pair of strings at the 2nd position, but the
point is, you would
then be fresh out of positions for distinguishing
000000000000000000000... from
110000000000000000000...,
and for distinguishing
0011111111111111111111... from
1111111111111111111111....
This is four pairs of strings that differ in only 2 positions, so
obviously,
you may NOT say that there is always a node-pair that is never used
to distinguish another pair of paths. |
|
| |
|
| Back to top |
WM
Guest
|
| Posted: Tue Oct 07, 2008 11:49 am Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On 7 Okt., 13:03, David C. Ullrich <dullr...@sprynet.com> wrote:
[quote]On Mon, 6 Oct 2008 11:25:34 -0700 (PDT), WM
mueck...@rz.fh-augsburg.de> wrote:
A path in an infinite binary tree is the representation of a real
number of the interval [0, 1]. (Terminating rational numbers have two
representations each.)
Two paths A and B in the infinite binary tree can be distinguished by
at least one pair of nodes a and b where a belongs to A but not to B,
and b belongs to B but not to A.
Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
"is used to distinguish" is unclear. I>m going to assume you meant
"distinguishes", or "can be used to distinguish".
[/quote]
The nodes that distinguish paths can be mapped onto those paths, in
the example above a can be mapped on A and b can be mapped on B. The
assumption is that a node mapped on a path is not needed to be mapped
on another path.
[quote]
Conclusion: The number of paths is not larger than the number of
nodes. The number of nodes is countable. As the number of paths is not
less than the number of reals in the interval [0, 1], the number of
reals in the interval [0, 1] is countable.
Or: The assumption is wrong.
That>s correct, the assumption is wrong. (Obviously wrong,
in fact).
There are at least two pairs of paths
that cannot be distinguished by different nodes.
Wow. No, that>s not the negation of the assumption.
The negation of the assumption would be that there
is a pair of paths such that every pair of nodes
distinguishing those two paths also distinguishes
another pair of paths.
[/quote]
There is no reason for a "Wow". Your statement implies mine. Therefore
the negation of the assumption implies my statement: There are at
least two pairs of paths that cannot be distinguished by different
nodes.
[quote]
And that>s obviously so. Say P_1 and P_2 are
any two paths, distinguished by nodes a and b.
If P_1' and P_2' are the same as P_1 and P_2
down to the level of a and b but then go off
in different directions from P_1 and P_2 then
a and b also suffice to distinguish P_1' and P_2'.
[/quote]
The question is not about being sufficient, but about being
*required*. Cp. the assumption. In short: Can we establish a bijective
mapping between nodes and paths?
[quote]
I gather all this started when someone pointed
out some elementary errors in some publication
of yours.
[/quote]
Please stop suspecting things you do not know of - try to understand
my argument. But thank you for the atempt. (No, I never tried to
publish the binary tree other than where it has been printed already.
I do not see any necessity to use the limited audience of a printed
medium because the audience of the internet is much broader.)
< You>re taking a very curious approach
[quote]to fixing that, making hundreds of posts containing
similar elementary errors.
[/quote]
There is nothing to fix. Obviously there cannot be more paths than
nodes in the binary tree.
Regards, WM |
|
| |
|
| Back to top |
WM
Guest
|
| Posted: Tue Oct 07, 2008 11:55 am Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On 7 Okt., 00:42, george <gree...@email.unc.edu> wrote:
[quote]On Oct 6, 2:25 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
Your "no node" is incorrect. You meant "neither node" or "that pair"
of nodes.
In any case, the assumption is obviously false.
Consider
01000000000000000000... versus
10000000000000000000....
You could distinguish these either at the pair of nodes closest to the
root,
or at the inner pair one level down, but obviously,
011111111111111111111... and
101111111111111111111... can ALSO be distinguished ONLY
at those two positions.
[/quote]
You misunderstand the binary tree.
0.
/ \
0 1
/ \ / \
0 1 0 1
....
The paths you give above can be distinguished by infinitely many
nodes.
[quote]You could insist that this is not yet a
counterexample by
distinguishing the first (0000>s) pair of strings at the first level/
position,
and the second (1111>s) pair of strings at the 2nd position, but the
point is, you would
then be fresh out of positions for distinguishing
000000000000000000000... from
110000000000000000000...,
and for distinguishing
0011111111111111111111... from
1111111111111111111111....
This is four pairs of strings that differ in only 2 positions,
[/quote]
Nevertheless they differ at *every* node.
[quote]so
obviously,
you may NOT say that there is always a node-pair that is never used
to distinguish another pair of paths.
[/quote]
I can.
Regards, WM |
|
| |
|
| Back to top |
David C. Ullrich
Guest
|
| Posted: Tue Oct 07, 2008 4:03 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Mon, 6 Oct 2008 11:25:34 -0700 (PDT), WM
<mueckenh@rz.fh-augsburg.de> wrote:
[quote]A path in an infinite binary tree is the representation of a real
number of the interval [0, 1]. (Terminating rational numbers have two
representations each.)
Two paths A and B in the infinite binary tree can be distinguished by
at least one pair of nodes a and b where a belongs to A but not to B,
and b belongs to B but not to A.
Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
[/quote]
"is used to distinguish" is unclear. I>m going to assume you meant
"distinguishes", or "can be used to distinguish".
[quote]Conclusion: The number of paths is not larger than the number of
nodes. The number of nodes is countable. As the number of paths is not
less than the number of reals in the interval [0, 1], the number of
reals in the interval [0, 1] is countable.
Or: The assumption is wrong.
[/quote]
That>s correct, the assumption is wrong. (Obviously wrong,
in fact).
[quote]There are at least two pairs of paths
that cannot be distinguished by different nodes.
[/quote]
Wow. No, that>s not the negation of the assumption.
The negation of the assumption would be that there
is a pair of paths such that every pair of nodes
distinguishing those two paths also distinguishes
another pair of paths.
And that>s obviously so. Say P_1 and P_2 are
any two paths, distingished by nodes a and b.
If P_1' and P_2' are the same as P_1 and P_2
down to the level of a and b but then go off
in different directions from P_1 and P_2 then
a and b also suffice to distinguish P_1' and P_2'.
I gather all this started when someone pointed
out some elementary errors in some publication
of yours. You>re taking a very curious approach
to fixing that, making hundreds of posts containing
similar elementary errors.
[quote]Regards, WM
[/quote]
David C. Ullrich
"Understanding Godel isn>t about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.) |
|
| |
|
| Back to top |
WM
Guest
|
| Posted: Wed Oct 08, 2008 12:54 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On 8 Okt., 13:58, David C. Ullrich <dullr...@sprynet.com> wrote:
[quote]Please stop suspecting things you do not know of - try to understand
my argument.
Sorry, I>m not going to try to understand an argument
that purports to show that there are only countably
many paths in an infinite binary tree.
[/quote]
But it is true, as you can see below without stretching yourself too
far, I think.
[quote]The only possible
reason for that would be to try to explain to the
author where the error is. I>ve done that - your
comment "Your statement implies mine." is
simply wrong.
[/quote]
You talked about a path and *every pair of nodes*. That implies at
least one pair of nodes, i.e., my statement, doesn>t it?
[quote]No point in going further since you
don>t seem to have an adequate grasp of simply logic.
[/quote]
Not adequate to what you may misunderstand as logic.
[quote]
But thank you for the atempt. (No, I never tried to
publish the binary tree other than where it has been printed already.
I do not see any necessity to use the limited audience of a printed
medium because the audience of the internet is much broader.)
Giggle. Of course the fact that anyone can say anything
they want on the internet has nothing to do with it.
[/quote]
I published the binary tree already in printed form. I do not belong
to the set of people who publish every minute idea at 10 different
places.
[quote]
You>re taking a very curious approach
to fixing that, making hundreds of posts containing
similar elementary errors.
There is nothing to fix. Obviously there cannot be more paths than
nodes in the binary tree.
Obvious or not, it>s not so.
[/quote]
It is very easy to see that there are not more paths than nodes in the
binary tree. For the sake of simplicity we will add one node to start
with. This node is mapped on one of the infinite paths, no matter
which one, say that one always turning left, i.e., 0.000....
o
|
/
/
/
....
The next node is mapped on another path, no matter which one, say one
always turning right, i.e., 0.111...
o
|
o
/ \
/ \
/ \
....
The next node is mapped on another path, no matter which one, say one
always changing direction, i.e., 0.010101...
o
|
o
/ \
o \
/ \ \
/ / \
/ \ \
/ / \
....
And so on.
Drawing gets difficult with increasing number of nodes, because space
becomes narrow. But perhaps you have understood already, that every
infinite path that exists in the infinite binary tree has one node
mapped onto it.
Of course we could also have selected the path pi-3 or any other one
to start with. There is no path existing in the tree being left out by
the mapping.
Regards, WM |
|
| |
|
| Back to top |
LauLuna
Guest
|
| Posted: Wed Oct 08, 2008 3:19 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 7, 1:49 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]On 7 Okt., 13:03, David C. Ullrich <dullr...@sprynet.com> wrote:
On Mon, 6 Oct 2008 11:25:34 -0700 (PDT), WM
mueck...@rz.fh-augsburg.de> wrote:
A path in an infinite binary tree is the representation of a real
number of the interval [0, 1]. (Terminating rational numbers have two
representations each.)
Two paths A and B in the infinite binary tree can be distinguished by
at least one pair of nodes a and b where a belongs to A but not to B,
and b belongs to B but not to A.
Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
"is used to distinguish" is unclear. I>m going to assume you meant
"distinguishes", or "can be used to distinguish".
The nodes that distinguish paths can be mapped onto those paths, in
the example above a can be mapped on A and b can be mapped on B. The
assumption is that a node mapped on a path is not needed to be mapped
on another path.
Conclusion: The number of paths is not larger than the number of
nodes. The number of nodes is countable. As the number of paths is not
less than the number of reals in the interval [0, 1], the number of
reals in the interval [0, 1] is countable.
Or: The assumption is wrong.
That>s correct, the assumption is wrong. (Obviously wrong,
in fact).
There are at least two pairs of paths
that cannot be distinguished by different nodes.
Wow. No, that>s not the negation of the assumption.
The negation of the assumption would be that there
is a pair of paths such that every pair of nodes
distinguishing those two paths also distinguishes
another pair of paths.
There is no reason for a "Wow". Your statement implies mine. Therefore
the negation of the assumption implies my statement: There are at
least two pairs of paths that cannot be distinguished by different
nodes.
And that>s obviously so. Say P_1 and P_2 are
any two paths, distinguished by nodes a and b.
If P_1' and P_2' are the same as P_1 and P_2
down to the level of a and b but then go off
in different directions from P_1 and P_2 then
a and b also suffice to distinguish P_1' and P_2'.
The question is not about being sufficient, but about being
*required*. Cp. the assumption. In short: Can we establish a bijective
mapping between nodes and paths?
I gather all this started when someone pointed
out some elementary errors in some publication
of yours.
Please stop suspecting things you do not know of - try to understand
my argument. But thank you for the atempt. (No, I never tried to
publish the binary tree other than where it has been printed already.
I do not see any necessity to use the limited audience of a printed
medium because the audience of the internet is much broader.)
You>re taking a very curious approach
to fixing that, making hundreds of posts containing
similar elementary errors.
There is nothing to fix. Obviously there cannot be more paths than
nodes in the binary tree.
Regards, WM- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
[/quote]
I>m not sure I>ve understood you but as far as I>ve done so your
assumption seems to contain a valid intuition: if we are constructing
pairs of distinguishable paths starting from the root, there is no
need to re-utilize an already used pair of nodes to distinguish two
new paths; any two different paths differ in an infinite quantity of
nodes, so we can leave behind all nodes already employed and go
further to fetch a fresh pair of nodes able to distinguish the new
paths. Is that what you mean?
But I think you>re assuming this implies we can identify each pair of
paths by one pair of nodes, so that there is an injection from the set
of pairs of paths into the set of pairs of nodes. This does not
follow.
It follows indeed that we will always find a new pair of nodes to
distinguish any two paths we can ever come to distinguish. But note
that the gist of the uncountable is that it goes beyond any such
constructive setting: there are more paths than we could ever come to
distinguish; most paths are absolutely indistinguishable from a
constructive point of view.
From the fact that, given any amount of already effectively
distinguished paired paths, we can always use a new pair of nodes to
distinguish from one another the paths in the next pair, does not
follow that for any different pair of paths there is a different pair
of nodes able to univocally identify it.
That would only be the case if the whole set of path couples could be
constructively exhausted. But, of course, assuming this is so would
simply beg the question since the constructive remains within the
countable.
I feel that most of your arguments share this trait: you assume that
all is constructive and you reason from that viewpoint.
Excuse me for trying to psychoanalize you :) and excuse me if I have
misunderstood you.
Regards |
|
| |
|
| Back to top |
WM
Guest
|
| Posted: Wed Oct 08, 2008 4:24 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On 8 Okt., 17:19, LauLuna <laureanol...@yahoo.es> wrote:
[quote]I>m not sure I>ve understood you but as far as I>ve done so your
assumption seems to contain a valid intuition: if we are constructing
pairs of distinguishable paths starting from the root, there is no
need to re-utilize an already used pair of nodes to distinguish two
new paths; any two different paths differ in an infinite quantity of
nodes, so we can leave behind all nodes already employed and go
further to fetch a fresh pair of nodes able to distinguish the new
paths. Is that what you mean?
[/quote]
Yes, that is right. But in my recent post I have also proved (again)
my assertion that every path can be mapped by a node that is not
related to any other path.
[quote]
But I think you>re assuming this implies we can identify each pair of
paths by one pair of nodes, so that there is an injection from the set
of pairs of paths into the set of pairs of nodes. This does not
follow.
[/quote]
See the proof for all existing paths below.
[quote]
It follows indeed that we will always find a new pair of nodes to
distinguish any two paths we can ever come to distinguish. But note
that the gist of the uncountable is that it goes beyond any such
constructive setting: there are more paths than we could ever come to
distinguish; most paths are absolutely indistinguishable from a
constructive point of view.
[/quote]
That may hold for a certain opinion about the real numbers. It is not
true for the paths of the binary tree.
Undistinguishable paths do not exist in a tree consisting of nodes.
Two paths can always be distinguished. Otherwise they are not
different. The point of distinction is a pair of nodes.
[quote]
From the fact that, given any amount of already effectively
distinguished paired paths, we can always use a new pair of nodes to
distinguish from one another the paths in the next pair, does not
follow that for any different pair of paths there is a different pair
of nodes able to univocally identify it.
[/quote]
If you talk about a pair of paths then you imply already that pair of
nodes that you deny.
[quote]
That would only be the case if the whole set of path couples could be
constructively exhausted. But, of course, assuming this is so would
simply beg the question since the constructive remains within the
countable.
[/quote]
The binary tree cannot exist other than by construction.
[quote]
I feel that most of your arguments share this trait: you assume that
all is constructive and you reason from that viewpoint.
[/quote]
Again: The binary tree is a construction. Of course the *real* real
numbers are constructive too. (cp. Dedekind) And that is also Cantor>s
approach. Accidentally, it was just today when I told my students
Cantor>s famous definition: "Unter einer Menge verstehen wir jede
Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer
Anschauung oder unseres Denkens zu einem Ganzen." (G. Cantor, 1895)
"wohlunterschieden", that means well distinguished. Hence, there
cannot be a set of real numbers that cannot be distinguished -
according to Cantor.
Anyhow, the binary tree is a crystal-clear construction that avoids
the confusing opinion of undistinguishable numbers. It does never
insert its roots into the mud of the continuum (Kontinuumssauce).
Therefore all its paths are and remain countable, whatever the
magicians of set-theory may fantasize about R.
[quote]
Excuse me for trying to psychoanalize you :) and excuse me if I have
misunderstood you.
[/quote]
No matter. I think you understood well. For your convenience, you can
find my argument below again. Of course it is a construction, because
the binary tree is a construction (and the real numbers are a
construction too - at least those numbers that can be used in
mathematics).
Regards, WM
It is very easy to see that there are not more paths than nodes in
the
binary tree. For the sake of simplicity we will add one node to start
with. This node is mapped on one of the infinite paths, no matter
which one, say that one always turning left, i.e., 0.000....
o
|
/
/
/
....
The next node is mapped on another path, no matter which one, say one
always turning right, i.e., 0.111...
o
|
o
/ \
/ \
/ \
....
The next node is mapped on another path, no matter which one, say one
always changing direction, i.e., 0.010101...
o
|
o
/ \
o \
/ \ \
/ / \
/ \ \
/ / \
....
And so on.
Drawing gets difficult with increasing number of nodes, because space
becomes narrow. But it is clear, that every infinite path that exists
in the infinite binary tree has one node mapped onto it.
Of course we could also have selected the path pi-3 or any other one
to start with. There is no path existing (!) in the tree being left
out by
the mapping. |
|
| |
|
| Back to top |
David C. Ullrich
Guest
|
| Posted: Wed Oct 08, 2008 4:58 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Tue, 7 Oct 2008 04:49:57 -0700 (PDT), WM
<mueckenh@rz.fh-augsburg.de> wrote:
[quote]On 7 Okt., 13:03, David C. Ullrich <dullr...@sprynet.com> wrote:
On Mon, 6 Oct 2008 11:25:34 -0700 (PDT), WM
mueck...@rz.fh-augsburg.de> wrote:
A path in an infinite binary tree is the representation of a real
number of the interval [0, 1]. (Terminating rational numbers have two
representations each.)
Two paths A and B in the infinite binary tree can be distinguished by
at least one pair of nodes a and b where a belongs to A but not to B,
and b belongs to B but not to A.
Assumption: For every pair of paths we can find a distinguishing pair
of nodes where no node is used to distinguish another pair of path.
"is used to distinguish" is unclear. I>m going to assume you meant
"distinguishes", or "can be used to distinguish".
The nodes that distinguish paths can be mapped onto those paths, in
the example above a can be mapped on A and b can be mapped on B. The
assumption is that a node mapped on a path is not needed to be mapped
on another path.
Conclusion: The number of paths is not larger than the number of
nodes. The number of nodes is countable. As the number of paths is not
less than the number of reals in the interval [0, 1], the number of
reals in the interval [0, 1] is countable.
Or: The assumption is wrong.
That>s correct, the assumption is wrong. (Obviously wrong,
in fact).
There are at least two pairs of paths
that cannot be distinguished by different nodes.
Wow. No, that>s not the negation of the assumption.
The negation of the assumption would be that there
is a pair of paths such that every pair of nodes
distinguishing those two paths also distinguishes
another pair of paths.
There is no reason for a "Wow". Your statement implies mine. Therefore
the negation of the assumption implies my statement: There are at
least two pairs of paths that cannot be distinguished by different
nodes.
And that>s obviously so. Say P_1 and P_2 are
any two paths, distinguished by nodes a and b.
If P_1' and P_2' are the same as P_1 and P_2
down to the level of a and b but then go off
in different directions from P_1 and P_2 then
a and b also suffice to distinguish P_1' and P_2'.
The question is not about being sufficient, but about being
*required*. Cp. the assumption. In short: Can we establish a bijective
mapping between nodes and paths?
I gather all this started when someone pointed
out some elementary errors in some publication
of yours.
Please stop suspecting things you do not know of - try to understand
my argument.
[/quote]
Sorry, I>m not going to try to understand an argument
that purports to show that there are only countably
many paths in an infinite binary tree. The only possible
reason for that would be to try to explain to the
author where the error is. I>ve done that - your
comment "Your statement implies mine." is
simply wrong. No point in going further since you
don>t seem to have an adequate grasp of simply logic.
[quote]But thank you for the atempt. (No, I never tried to
publish the binary tree other than where it has been printed already.
I do not see any necessity to use the limited audience of a printed
medium because the audience of the internet is much broader.)
[/quote]
Giggle. Of course the fact that anyone can say anything
they want on the internet has nothing to do with it.
[quote]You>re taking a very curious approach
to fixing that, making hundreds of posts containing
similar elementary errors.
There is nothing to fix. Obviously there cannot be more paths than
nodes in the binary tree.
[/quote]
Obvious or not, it>s not so.
[quote]Regards, WM
[/quote]
David C. Ullrich
"Understanding Godel isn>t about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.) |
|
| |
|
| Back to top |
MoeBlee
Guest
|
| Posted: Wed Oct 08, 2008 5:53 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 8, 5:54 am, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]every
infinite path that exists in the infinite binary tree has one node
mapped onto it.
[/quote]
What your argument and illustrations suggest is that the set of nodes
injects into the set of paths. For every node there is a unique path
that we can associate with that node. Yes. But that doesn>t gives a
BIjection of the set of nodes ONTO the set of paths.
MoeBlee |
|
| |
|
| Back to top |
LauLuna
Guest
|
| Posted: Wed Oct 08, 2008 8:21 pm Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 8, 6:24 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]On 8 Okt., 17:19, LauLuna <laureanol...@yahoo.es> wrote:
I>m not sure I>ve understood you but as far as I>ve done so your
assumption seems to contain a valid intuition: if we are constructing
pairs of distinguishable paths starting from the root, there is no
need to re-utilize an already used pair of nodes to distinguish two
new paths; any two different paths differ in an infinite quantity of
nodes, so we can leave behind all nodes already employed and go
further to fetch a fresh pair of nodes able to distinguish the new
paths. Is that what you mean?
Yes, that is right. But in my recent post I have also proved (again)
my assertion that every path can be mapped by a node that is not
related to any other path.
But I think you>re assuming this implies we can identify each pair of
paths by one pair of nodes, so that there is an injection from the set
of pairs of paths into the set of pairs of nodes. This does not
follow.
See the proof for all existing paths below.
It follows indeed that we will always find a new pair of nodes to
distinguish any two paths we can ever come to distinguish. But note
that the gist of the uncountable is that it goes beyond any such
constructive setting: there are more paths than we could ever come to
distinguish; most paths are absolutely indistinguishable from a
constructive point of view.
That may hold for a certain opinion about the real numbers. It is not
true for the paths of the binary tree.
Undistinguishable paths do not exist in a tree consisting of nodes.
Two paths can always be distinguished. Otherwise they are not
different. The point of distinction is a pair of nodes.
From the fact that, given any amount of already effectively
distinguished paired paths, we can always use a new pair of nodes to
distinguish from one another the paths in the next pair, does not
follow that for any different pair of paths there is a different pair
of nodes able to univocally identify it.
If you talk about a pair of paths then you imply already that pair of
nodes that you deny.
That would only be the case if the whole set of path couples could be
constructively exhausted. But, of course, assuming this is so would
simply beg the question since the constructive remains within the
countable.
The binary tree cannot exist other than by construction.
I feel that most of your arguments share this trait: you assume that
all is constructive and you reason from that viewpoint.
Again: The binary tree is a construction. Of course the *real* real
numbers are constructive too. (cp. Dedekind) And that is also Cantor>s
approach. Accidentally, it was just today when I told my students
Cantor>s famous definition: "Unter einer Menge verstehen wir jede
Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer
Anschauung oder unseres Denkens zu einem Ganzen." (G. Cantor, 1895)
"wohlunterschieden", that means well distinguished. Hence, there
cannot be a set of real numbers that cannot be distinguished -
according to Cantor.
Anyhow, the binary tree is a crystal-clear construction that avoids
the confusing opinion of undistinguishable numbers. It does never
insert its roots into the mud of the continuum (Kontinuumssauce).
Therefore all its paths are and remain countable, whatever the
magicians of set-theory may fantasize about R.
Excuse me for trying to psychoanalize you :) and excuse me if I have
misunderstood you.
No matter. I think you understood well. For your convenience, you can
find my argument below again. Of course it is a construction, because
the binary tree is a construction (and the real numbers are a
construction too - at least those numbers that can be used in
mathematics).
Regards, WM
It is very easy to see that there are not more paths than nodes in
the
binary tree. For the sake of simplicity we will add one node to start
with. This node is mapped on one of the infinite paths, no matter
which one, say that one always turning left, i.e., 0.000....
o
|
/
/
/
...
The next node is mapped on another path, no matter which one, say one
always turning right, i.e., 0.111...
o
|
o
/ \
/ \
/ \
...
The next node is mapped on another path, no matter which one, say one
always changing direction, i.e., 0.010101...
o
|
o
/ \
o \
/ \ \
/ / \
/ \ \
/ / \
...
And so on.
Drawing gets difficult with increasing number of nodes, because space
becomes narrow. But it is clear, that every infinite path that exists
in the infinite binary tree has one node mapped onto it.
Of course we could also have selected the path pi-3 or any other one
to start with. There is no path existing (!) in the tree being left
out by
the mapping.
[/quote]
Concerning the proof you were kind enough to reproduce I must say I
find it puzzling. Anytime you map a node on a path you say 'no matter
which one', so giving no criterium and defining no bijective function
between the set of paths and the set of nodes. All you say is: 'take a
node in turn and map it on a path; when the nodes are exhausted,
you>ll have exhausted the paths too'; but this is just equivalent to
postulating the equicardinality of both sets without defining a
bijection to prove it.
You say:
[quote]But it is clear, that every infinite path that exists
in the infinite binary tree has one node mapped onto it.
[/quote]
How could it possibly be clear when you do not even define the
intended bijection?
On the other hand, it>s of course your right to reject whatever is not
constructive in mathematics, but if you wish to prove an internal
inconsistency in the transfinite set theory you cannot assume
constructivity (in the usual sense); it would beg the question, since
the constructive, as usually understood, does not transcend the
countable.
I confess you have me wondering in what sense the infinite binary tree
is constructive; it seems easy to give a recipe to construct it but it
is not constructive in the sense that it>s the output of some
algorithm: it cannot be reduced to a unidimensional sequence.
I guess this question is important for the possibility of defining an
injection from the set of all pairs of paths into the set of all pairs
of nodes.
Let me give it a second thought.
Regards |
|
| |
|
| Back to top |
george
Guest
|
| Posted: Thu Oct 09, 2008 3:39 am Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 7, 7:55 am, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]You misunderstand the binary tree.
0.
/ \
0 1
/ \ / \
0 1 0 1
...
The paths you give above can be distinguished by infinitely many
nodes.
[/quote]
ALL [pairs of] paths can be distinguished by infinitely many nodes.
Any two paths have some initial path-segment in common (it may
be the empty segment if their first digits are different). After
that,
EVERY node in one path is different from EVERY node in the other path;
once paths split, they never re-cross or re-intersect or re-combine.
So any one of the infinitely many nodes after the split-point on the
left path
can be paired with any one of infinitely many nodes on the split-point
after
the right path to produce a distinguishing pair. But the number of
differing
paths below the split is still uncountable, and the number of node-
pairs below
the split is still countable.
One can without loss of generality just throw away the shared prefix
in any
case if one is talking about distinguishing different paths. |
|
| |
|
| Back to top |
george
Guest
|
| Posted: Thu Oct 09, 2008 3:53 am Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
On Oct 8, 8:54 am, WM <mueck...@rz.fh-augsburg.de> wrote:
[quote]It is very easy to see that there are not more paths than nodes in the
binary tree.
[/quote]
Come ON.
That is very obviously BULLSHIT.
The fact that nobody has refuted your proof PROPERLY yet
has more to do with your inability to understand a proper refutation
than the inability of anybody here to state one.
The diagonal argument will do quite well for refuting your conjecture
here,
if anybody can figure out the natural relationship for diagonalizing
the path-
pairs and the node-pairs. Every path-pair already "includes" every
node-pair
so it is not immediately obvious what to complement to "anti"-diag.
But you know it>s going to be something.
[quote]For the sake of simplicity we will add one node to start
with. This node is mapped on one of the infinite paths, no matter
which one, say that one always turning left, i.e., 0.000....
o
|
/
/
/
...
The next node is mapped on another path, no matter which one, say one
always turning right, i.e., 0.111...
o
|
o
/ \
/ \
/ \
...
The next node is mapped on another path, no matter which one, say one
always changing direction, i.e., 0.010101...
o
|
o
/ \
o \
/ \ \
/ / \
/ \ \
/ / \
...
And so on.
Drawing gets difficult with increasing number of nodes, because space
becomes narrow. But perhaps you have understood already, that every
infinite path that exists in the infinite binary tree has one node
mapped onto it.
[/quote]
You could map the root to every path if that were the only constraint.
You need to add something like ONLY ONE node gets mapped to any path.
And if you do that, then
You CAN>T DO this, because there are MORE paths than nodes!
THIS way is probably EASIERto diagonalize than your original
problem of path-pairs and node-pairs! |
|
| |
|
| Back to top |
Ross A. Finlayson
Guest
|
| Posted: Thu Oct 09, 2008 7:55 am Post subject: Re: Binary Tree and Pairs of Nodes |
|
|
george wrote:
[quote]On Oct 8, 8:54 am, WM <mueck...@rz.fh-augsburg.de> wrote:
It is very easy to see that there are not more paths than nodes in the
binary tree.
Come ON.
That is very obviously BULLSHIT.
[/quote]
It>s so simply a matter of perspective.
[quote]The fact that nobody has refuted your proof PROPERLY yet
has more to do with your inability to understand a proper refutation
than the inability of anybody here to state one.
The diagonal argument will do quite well for refuting your conjecture
here,
if anybody can figure out the natural relationship for diagonalizing
the path-
pairs and the node-pairs. Every path-pair already "includes" every
node-pair
so it is not immediately obvious what to complement to "anti"-diag.
But you know it>s going to be something.
For the sake of simplicity we will add one node to start
with. This node is mapped on one of the infinite paths, no matter
which one, say that one always turning left, i.e., 0.000....
o
|
/
/
/
...
The next node is mapped on another path, no matter which one, say one
always turning right, i.e., 0.111...
o
|
o
/ \
/ \
/ \
...
The next node is mapped on another path, no matter which one, say one
always changing direction, i.e., 0.010101...
o
|
o
/ \
o \
/ \ \
/ / \
/ \ \
/ / \
...
And so on.
[/quote]
As we have discussed before, these tree graph diagrams of the
relationships of the nodes in the tree with the numeric expansion along
the scalar lines to the parallel, those progress along node path lines,
in the balanced trees that are used to represent the numeric expansions
as real numbers.
[quote]Drawing gets difficult with increasing number of nodes, because space
becomes narrow. But perhaps you have understood already, that every
infinite path that exists in the infinite binary tree has one node
mapped onto it.
You could map the root to every path if that were the only constraint.
You need to add something like ONLY ONE node gets mapped to any path.
And if you do that, then
You CAN>T DO this, because there are MORE paths than nodes!
THIS way is probably EASIERto diagonalize than your original
problem of path-pairs and node-pairs!
[/quote]
If the point is diagonalization, then there is the consideration of the
matrix algebra of the products, linear differential analysis and so on.
Thanks,
Ross F. |
|
| |
|
| Back to top |
|
