Search All of the Math Forum:

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

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

Topic: On the infinite binary Tree
Replies: 64   Last Post: Dec 17, 2012 11:06 AM

 Messages: [ Previous | Next ]
 Zaljohar@gmail.com Posts: 2,665 Registered: 6/29/07
Re: On the infinite binary Tree
Posted: Dec 14, 2012 9:38 AM

On Dec 14, 5:30 pm, Zuhair <zaljo...@gmail.com> wrote:
> On Dec 14, 12:32 am, WM <mueck...@rz.fh-augsburg.de> wrote:
>
>
>
>
>
>
>
>
>

> > On 13 Dez., 21:02, Zuhair <zaljo...@gmail.com> wrote:
>
> > > On Dec 13, 3:56 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
>
> > > > No? Nearly every real number is undefinable. The measure of definable
> > > > reals is 0. If most reals are non-definable, why must all reals of
> > > > every Cantor list always be definable? If all reals of the list are
> > > > definable, then they belong to a countable set. Then we cannot prove
> > > > uncounatbility. Or can we prove that the set of definable reals is
> > > > uncountable - because it is countable but there are, somewhere else,
> > > > undefinable "reals"?

>
> > > > Regards, WM
>
> > > Cantor's list do contain non definable reals.
>
> > Which one in what line? What is the corresponding digit of the
> > diagonal?

>
> > >  Actually some diagonals
> > > of Cantor's are non definable.

>
> > Lists containing undefinable entries do not supply diagonals at all.
>
> > > The bijective function between all
> > > definable reals and the set N of all naturals is NON definable set!

>
> > That is completely without interest.
>
> > > Note: definable is short for "definable by parameter free finite
> > > formula"

>
> > No. Definable means "definable by a finite word". Everything else is
> > "undefinable".

>
> > Regards, WM
>
> Hmmm... then we are speaking about different concepts.
>
> For me when I say Definable real, it means real that is definable
> after some FINITE formula that is PARAMETER FREE.
>
> While to you it seems you mean a real that is definable after some
> finite formula.
>
> These are two different concepts, and we do need to look into those
> carefully.
>
> Generally speaking a set X is called Definable iff there is a finitary
> formula phi such that
> for all y. y in X <-> phi
>
> Now a set X is called "parameter free definable set" iff there is a
> finitary formula phi that is parameter free such that for all y. y in
> X <-> phi
>
> However customarily speaking when we say definable mostly it refers to
> parameter free definability, anyhow.
>
> So for the sake of discussion here I will give the term "definable"
> for any finitary formula, and I'll use
> "parameter free definable" if the defining formula is a finite formula
> that is parameter free, as depicted above.
>
> Now there is an important question: Is all reals parameter free
> definable?
> If the answer is yes then it is clear that we will have COUNTABLY many
> reals, since we have countably many parameter free finite formulas,
> that's obvious.
>
> One needs to be careful here, if a real is not parameter free
> definable that doesn't mean it is not definable! since there can be a
> finitary formula that is not parameter free after which it can be
> defined. A famous example is the diagonal after a bijective function
> from the set of all naturals to the set of all parameter free
> definable reals. This diagonal is DEFINABLE but not in a parameter
> free manner.
>
> There is something very important that people need to realize about
> the difference between definability and parameter free definability.
> which is the following:
>
> If one say that all reals are parameter free definable then this leads
> to saying that all reals are countable!
>
> If one say that all reals are "definable" then this does NOT lead to
> saying that all reals are countable!!!
>
> WHY?
>
> One would wonder saying what is the difference, in any case we have
> countably many formulas whether they are parameter free or not? so for
> the first glance it seems that what make all parameter free definable
> reals countable is the same thing that causes one to believe that all
> definable reals are countable, and obviously that thing is the
> countability of all finitary formulas.
>
> But the reality of the matter is that they differ greatly and the
> above reasoning is not correct. The presence of a parameter in the
> defining formula (which is of course finite as stipulated above) will
> make a big difference from its absence.
>
> Lets take the following example to show that difference:
>
> For all y. y in X <-> y in A & pi(y)
>
> so the defining formula of X here is of course the formula "y in A &
> pi(y)" where pi(y) is some
> formula that is finitary parameter free formula.
>
> Now the formula "y in A & pi(y)" is a finitary formula but it is not
> parameter free, it contains a parameter and that parameter is A.
>
> Lets go more concretely and lets stipulate pi(y) to be the formula "y
> is an even number"
>
> Now how many sets X do I have that can be defined in the above manner?
> The answer depends clearly on how many sets the symbol A can range
> over.
>
> Suppose for the sake of discussion that we have uncountably many sets
> that A can range over.
> Now for each substitution of A by a set we have a set X that
> correspond to that substitution, so it is possible to have uncountably
> many sets X defined from uncountably many substitutions of the
> variable A in the SINGLE formula "y in A & pi(y)".
>
> So we can define MANY sets after the single formula which is " y in A
> & pi(y) "
>
> So here the relationship between the number of sets defined after a
> formula having a parameter is not ONE-ONE, no it is actually MANY -
> ONE relationship.
>
> That's why even if we have countably many parameter free finitary
> formula which is of course the case as we all know, still this doesn't
> mean that the number of all sets definable after those formulas is
> also countable,

Oops, I meant ...even if we have countably many finitary formulas
which is....

why because for finitary formulas that contain
> parameters the relationship between the sets defined after those
> formulas and those formulas is not ONE-ONE, it can be MANY-ONE.
>
> So we of course can have uncountably many definable reals in this
> sense.
>
> However the situation differs for "parameter free definable" reals.
> Here matters are completely different. Lets come back again and
> analyse matters.
>
> For all y. y in X <-> phi(y)
>
> phi(y) is parameter free (i.e. have no free variables other than y).
>
> Now because of Extensionality, we know that there is only ONE set X
> than can be defined after EACH formula phi(y). So the relationship
> between the defined sets and the parameter free defining formulas is
> ONE-ONE. And since we have only countably many finitary formulas and
> parameter free formulas are all finitary by definition (see above),
> then we will definitely have countably many parameter free definable
> reals.
>
> This is a subtle difference that a lot of people usually overlook.
>
> Cantor is not afraid from ALL reals being definable. But definitely
> Cantor knew that all reals cannot be parameter free definable in a
> finitary manner. Since the later would clearly violate his diagonal,
> but the former does not.
>
> Hope that helps!
>
> Zuhair

Date Subject Author
12/12/12 Zaljohar@gmail.com
12/12/12 mueckenh@rz.fh-augsburg.de
12/12/12 Virgil
12/12/12 mueckenh@rz.fh-augsburg.de
12/12/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 trj
12/13/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Virgil
12/13/12 Virgil
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/14/12 mueckenh@rz.fh-augsburg.de
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/14/12 Zaljohar@gmail.com
12/14/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/14/12 mueckenh@rz.fh-augsburg.de
12/14/12 Tanu R.
12/14/12 Virgil
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/12/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/12/12 george
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 george
12/14/12 mueckenh@rz.fh-augsburg.de
12/14/12 Virgil
12/14/12 mueckenh@rz.fh-augsburg.de
12/14/12 Tanu R.
12/14/12 Virgil
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/15/12 Tanu R.
12/14/12 Charlie-Boo
12/14/12 forbisgaryg@gmail.com
12/15/12 ross.finlayson@gmail.com
12/15/12 forbisgaryg@gmail.com
12/15/12 ross.finlayson@gmail.com
12/16/12 forbisgaryg@gmail.com
12/17/12 ross.finlayson@gmail.com
12/16/12 Ciekaw
12/16/12 Virgil