|
|
Re: On the infinite binary Tree
Posted:
Dec 14, 2012 9:30 AM
|
|
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
|
|
