
Re: On the infinite binary Tree
Posted:
Dec 14, 2012 9:30 AM


On Dec 14, 12:32 am, WM <mueck...@rz.fhaugsburg.de> wrote: > On 13 Dez., 21:02, Zuhair <zaljo...@gmail.com> wrote: > > > On Dec 13, 3:56 pm, WM <mueck...@rz.fhaugsburg.de> wrote: > > > > No? Nearly every real number is undefinable. The measure of definable > > > reals is 0. If most reals are nondefinable, 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 ONEONE, 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 ONEONE, it can be MANYONE.
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 ONEONE. 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

