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