Date: Dec 14, 2012 9:38 AM Author: Zaljohar@gmail.com Subject: Re: On the infinite binary Tree 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