Alberto Monteiro wrote
> Robert Shaw wrote:
> >
> >> But this is the problem that we are trying to discuss. Or,
> >> there are two problems:
>
> I'm glad you didn't correct me and mention that there
> is an uncountable number of such problems! :-)
>
Now that depends how you count them.
> >> which numbers can be constructed
> >> in an exact way, and which numbers are the accumulation
> >> points of the set of numbers that can be constructed in an
> >> exact way. The first set is enumerable, maybe finite. The
> >> second set might be anything.
> >
> > We know the second set is uncountable, and includes the
> > rationals.
> >
> > Their are five sets involved, so for clarity they need names.
> > We've got the set of calculator functions Ca={cos,sin,tan,exp etc)
> >
> Ok, but maybe we might extend this to the "binary" functions.
>
Yes.
For that matter the calculators we used could calculate trigometric
functions in radians, degrees, or grades, effectively allowing
multiplication
and division by pi/180 and 0.9. All these sets have a G(S) which includes
the rationals.
> > Second, the set of all finite sequences of calculator functions, S.
> > S is countable, with elements s of the form (fn,....f3,f2,f1) with
> > each fm being an element of Ca.
> > We have a mapping G from S to K=R U{_error_} given
> > by G(s) =fn(...f3(f2(f1(0)..)
> > Define fn(_error_)=_error_ for all fn in Ca
> >
> > G(S) is the set of all finitely constructable number starting
> > with 0.
> >
> Maybe it might be better to "extend" this definition
> to something like Constr(Ca, K0), the set of all
> finitely constructable numbers starting with an element
> of K0 and using functions from the set of functions Ca.
>
Yes. G is actually a mapping from an ordered triple
(Ca, an element of the power set of all sets of suitable functions,
S, the the of finite sequences has defined above,
K0, the set of possible starting numbers)
to K, in this case R U {_error_}
Since we are principally discussing a specific set Ca and a
specific starting element 0, its simplest to leave them as
implicit parameters as long as we don't forget they are there.
> > For arbitary set Ca G(S) is not automatically countable. If
> > c={1/x,x^2}then G(S)={0,_error_}
> >
> > For this C we know Q is a subset of G(S), as you proved,
> ^
> Ca, isn't it?
Yes. That comes of changing names midstream. C might get
confused with the complex numbers.
>
> > so G(S) is countably infinite and dense.
> > We don't know what G(S) is, though we think the
> > algebraic numbers A are not a subset of G(S)
> >
> > Next we've got the set Si of all infinite sequences of functions
> > in Ca. By Cantor's diagonal argument we know Si is
> > an uncountable set if at least one pair of functions in Ca does
> > not commute.
> >
> Hmmmm... Commuting is irrelevant, since we are just taking
> the functions, and not operating them - because it's
> meaningless to write an expression like x = f0 f1 f2 ... for
> an infinite sequence of functions.
You're right.
If all the functions in Ca commute we know G(Si) is at most countable.
>
> > We also have the set G(Si), which includes all the accumulation
> > points of G(s). For sequences si in Si such that G(si) isn't
> > in R (e.g 1/x,1/x,1/x ....) we can reasonably define G(si) as
> > being _error_ For arbitary sets of functions G(Si) needn't
> > be uncountable, and can even be finite nor does G(S) have to be
> > a subset of G(Si).
> >
> Ok - because there might not be any "loop" (f1 f2 ... fn)(x) = x
>
> > We don't know much about G(S) or G(Si) for the particular set
> > Ca of calculator functions, and less for arbitary sets of functions.
> > Even for Ca we don't know if G(Si) includes Q.
> >
> Uh? Wasn't this proven before?
I was implicitly assuming Ca includes the identity function.
If it does G(S) is a subset of G(Si).
If it doesn't things are less clear. There are arbitarily long
finite sequences that correspond to any rational but it's
not entirely clear that there are infinitely long sequences
that do.
It may be simpler to include the identity function in Ca.
>
> > The obvious way to prove G(Si) uncountable is to look at
> > how many elements of Si map to each element of G(Si).
> > If only a countable number do so then we know G(Si)
> > can't be countable else Si would be a countable union
> > of countable sets, which is not possible.
> >
> Ok.
>
To get further with this we need to consider when different
elements of Si map to the same element of G(Si).
That happens if some element of S is equivalent to the identity
under G. E.g we can insert ln exp at any point in a sequence
without changing its image under G.
This gives a countably infinite subset of Si mapping to each element
of G(Si) but there may be other conditions under which different
elements have the same image that leave us with uncountably many
elements of Si for each element of G(Si)
> > Because a subset of Ca maps the positive reals to themeselves
> > by considering this subset, which produces a subset of G(Si)
> > which doesn't include _error_ , we can place a lower bound on
> > the cardinality of G(Si) without having to consider _error_.
> > If the restricted subset can be proved uncountable then G(Si)
> > is also uncountable.
> >
> Ok.
--
Robert
