The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: The uncountability infinite binary tree.
Replies: 118   Last Post: Dec 17, 2012 8:49 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Rupert

Posts: 3,810
Registered: 12/6/04
Re: The uncountability infinite binary tree.
Posted: Dec 16, 2012 12:28 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Dec 16, 6:18 pm, "Ross A. Finlayson" <ross.finlay...@gmail.com>
wrote:
> On Dec 16, 9:01 am, Rupert <rupertmccal...@yahoo.com> wrote:
>
>
>
>
>
>
>
>
>

> > On Dec 16, 5:55 pm, "Ross A. Finlayson" <ross.finlay...@gmail.com>
> > wrote:

>
> > > On Dec 16, 7:54 am, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > > On Dec 16, 1:30 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
>
> > > > > On 16 Dez., 11:54, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > > > > On Dec 16, 11:32 am, WM <mueck...@rz.fh-augsburg.de> wrote:
>
> > > > > > > On 16 Dez., 11:02, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > > > > > > On Dec 15, 7:07 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
>
> > > > > > > > > On 15 Dez., 16:54, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > > > > > > > > On Dec 15, 12:35 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
>
> > > > > > > > > > > On 15 Dez., 11:21, Rupert <rupertmccal...@yahoo.com> wrote:
>
> > > > > > > > > > > > On Dec 15, 10:56 am, WM <mueck...@rz.fh-augsburg.de> wrote:
> > > > > > > > > > > > > > Thus the Infinite binary tree is UNCOUNTABLE.
>
> > > > > > > > > > > > > Since it can be proved to be countable, there is a contradiction.
>
> > > > > > > > > > > > How do you prove that it is countable?
>
> > > > > > > > > > > First: A Tree that contains all nodes also contains all reals of the
> > > > > > > > > > > unit interval.

>
> > > > > > > > > > > I constrcut the tree, i.e., all nodes, by countably many infinite
> > > > > > > > > > > paths.

>
> > > > > > > > > > Tell us more about this construction.
>
> > > > > > > > > I use all finite paths. Every node of the Binary Tree is the end of a
> > > > > > > > > path. Then I append these countably many paths by a tail according to
> > > > > > > > > my choice. For instance I can use the tail
> > > > > > > > > 000...
> > > > > > > > > or
> > > > > > > > > 010101...
> > > > > > > > > or
> > > > > > > > > the bit sequence of pi
> > > > > > > > > or anything else, for instance a mix of many tails.

>
> > > > > > > > > In order to show you that you are dreaming if you think that infinite
> > > > > > > > > paths could be identified by their nodes, I don't tell you what tails
> > > > > > > > > I have used. If you don't sleep to deep, then you will wake up and
> > > > > > > > > recognize that infinite paths are merely defined by finite
> > > > > > > > > definitions, and hence belong to a countable set.

>
> > > > > > > > > Regards, WM
>
> > > > > > > > Okay, so you seem to be saying that you would take all the finite
> > > > > > > > paths and append an infinite tail to each one, thereby obtaining a
> > > > > > > > countably infinite collection of infinite paths. Is the claim then
> > > > > > > > that this would be equal to the collection of all infinite paths? Or
> > > > > > > > not?-

>
> > > > > > > It is equal to the collection of all paths that are defined solely by
> > > > > > > their nodes. It is equal to all finite initial strings of digits that
> > > > > > > can be applied in a Cantor-list. (Every digit changed there has a
> > > > > > > finite index.)

>
> > > > > > > Actually infinite paths like that of 0.010101... = 1/3 (in binary)
> > > > > > > cannot be defined by nodes. No infinite sequence has ever been defined
> > > > > > > by its terms. Those things have to be defined by finite definitions
> > > > > > > like "0.010101..." or "1/3".

>
> > > > > > Okay. That all sounds fair enough.
>
> > > > > > So, you were going to show us that there are only countably many
> > > > > > paths. When are you going to do that?-

>
> > > > > First I showed you that there are only countably many paths that are
> > > > > defined by nodes. You seemed to agree. Call them the set A.

>
> > > > > Well, the other "paths" cannot be defined by nodes. Call them the set
> > > > > B. They need definitions by finite words. And there are only countably
> > > > > many finite words.

>
> > > > > Now consider the union of two countable sets A and B.
>
> > > > How do you know that there exists a countable language such that every
> > > > path can be defined in this language?

>
> > > > > Regards, WM
>
> > > Well there aren't any uncountable languages.  (Thank you I'd be
> > > interested in as to where there were, with regards to then theoretical
> > > consequences.)

>
> > There are plenty of uncountable languages. For example, you can have a
> > first-order language with uncountably many predicate symbols.

>
> > >         L([01]*)
>
> > > Basically, does the Kleene (Klayn-ee) star allow infinite words?
>
> > You can have infinite words. See for example the infinitary languages
> > discussed in Chapter 10 of Drake's "Set Theory: An Introduction to
> > Large Cardinals".

>
> > But that wouldn't be covered by the Kleene star operation.
>
> > But that's neither here nor there. You don't need infinite words, you
> > just need to have an uncountable alphabet.

>
> > >        http://en.wikipedia.org/wiki/Kleene_star
>
> > > No, it doesn't.  Yet, Turing machines allow infinite programs.
>
> > No.
>
> > > As
> > > well, several of the references refer to the closure not being finite.

>
> > Closure of what? Closure in what sense?
>
> > > It's always seemed incongruous that 2^w, here the order type of
> > > BT_oo's domain, is countable.

>
> > The set of all infinite paths in a binary tree does not have an
> > ordering of order type 2^w (where you take exponentiation in the
> > ordinal sense, so that 2^w=w).

>
> The Universal Turing Machine has infinite resources, see for example
> the recent discussions on Rice's theorem.
>


The input to any Turing machine has finite length, by definition.

> Here, the set 2^w has order type 2^w > w.
>
> http://en.wikipedia.org/wiki/Order_type
>


Not if you use the standard definition of exponentiation of ordinals.
If you have some other notion in mind, you should specify which one.

> If the paths, of all of them, from the root through all non-leafs, at
> each level n, have order type 2^n, why do they not, at level or day
> omega = w, have order type 2^w?
>


Because it simply doesn't follow. Before we can even sensibly discuss
this you need to give your definition of the order type 2^w, because
it is obviously not the one that I thought you had in mind.

> Here that is a passing reference to Conway's surreal numbers.
>
> http://en.wikipedia.org/wiki/Surreal_number
>
> If at day omega as the surreal numbers may well have an initial
> construction from the infinite balanced binary tree, the paths have
> the same order type as omega, isn't there an order-preserving
> bijection between omega and the paths?


No. There is not.

I don't really know why you think there would be; your argument is not
clear enough.

> If they have order type 2^w,
> is not that yet countable?
>


I don't know what definition of 2^w you have in mind so I can't
comment.

The surreal numbers with birthday omega are not countable.

> Perhaps simply you could show how the diagonal method or nested
> intervals applies directly to the tree.
>


Have you read Zuhair's discussion?

> Regards,
>
> Ross Finlayson





Date Subject Author
12/14/12
Read The uncountability infinite binary tree.
Zaljohar@gmail.com
12/14/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/14/12
Read Re: The uncountability infinite binary tree.
William Elliot
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Rupert
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
trj
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
ross.finlayson@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Tanu R.
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Rupert
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
netzweltler
12/15/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Tanu R.
12/15/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Tanu R.
12/15/12
Read Re: The uncountability infinite binary tree.
namducnguyen
12/15/12
Read Re: The uncountability infinite binary tree.
Tanu R.
12/15/12
Read Re: The uncountability infinite binary tree.
namducnguyen
12/15/12
Read Re: The uncountability infinite binary tree.
Tanu R.
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
ross.finlayson@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
ross.finlayson@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
ross.finlayson@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
ross.finlayson@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
fom
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
m. m. m.
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Rupert
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Roland Franzius
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/17/12
Read Re: The uncountability infinite binary tree.
Virgil
12/17/12
Read Re: The uncountability infinite binary tree.
fom
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
m. m. m.
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
m. m. m.
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
ross.finlayson@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
trj
12/16/12
Read Re: The uncountability infinite binary tree.
Zaljohar@gmail.com
12/16/12
Read Re: The uncountability infinite binary tree.
mueckenh@rz.fh-augsburg.de
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/16/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Tanu R.
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil
12/15/12
Read Re: The uncountability infinite binary tree.
Virgil

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.