From: "Alberto Monteiro"
> Robert Shaw wrote:
> >
> > Actually, this is basically the continued fraction expansion.
> >
> I knew O:-)
>
> >
> > That means any real can be produced by some infinite
> > sequence of button presses, which wasn't self-evident.
> >
> This is another, similar, problem. Which numbers can be
> *approximated* by an infinite sequence of two funcions?
>
> For example, if you just have x -> x! and x -> sqrt(x),
> can you get as close as you want to any number? This is
> an extreme case, because you can't ()! non-integer numbers
> [calling x! = Gamma(x + 1) is cheating!!!]
Well, if you start with 0 or 1, you can only reach 0 or 1
respectively. Start with 2 and you can a single sequence of
numbers between 1 and 2
If you start with 3 you can only generate a countable infinity
of numbers. Take the factorial n times, then the square root
m times. Because of the sparsity of the factorials I'd suspect
this set isn't dense.
Generally, composing just two functions will give an uncountable
infinity of numbers which I think means the set of numbers
must be dense over a nonzero interval.
>
> > Which numbers can be reached with a finite sequence is
> > a harder question, but I don't think it's a well known set.
> >
> I think the toughest part is proving that some number
> *can't* be reached. I mean, we know [countability arguments]
> that such numbers exists, but can we point to some number,
> [say, "the solution of x = cos(x)"] and *prove* that it
> can't be reached?
>
Sometimes.
Galois proved that from x+1, x^(1/2), x^(1/3) and x^(1/5)
you can't get the solution of x^5+x=1.
That proof wasn't straightforwards, and relied on properties
of the particular functions allowed.
I wouldn't know how to start looking for proofs of constructability
in this case, but it doesn't seem likely to be easy.
.
I'm also reminded of the proofs that certain integrals aren't
compositions of functions in a particular set. The techniques
used to prove e^(-x*x) can't be integrated in terms of elementary
functions may also be usable to prove that no sequence of
compositions of the calculator functions can produce 5*x
though again I wouldn't know how.
> > The largest standard countable set is the algebraic numbers,
> > the other infinite countable sets being subsets of that.
> >
> "Largest standard"?
Well all countably infinite sets are the same size but
the algebraic numbers are a natural set that includes
all the other sets that don't include transcendental numbers
in their defintion, e.g Q, Q[sqrt(2)], and the quadratic irrationals.
As with Q, but unlike most other sets, the defintion of
algebraic numbers doesn't single out any specific number.
That makes it a natural target to prove the constructability of.
>
> > For the set of constructable numbers to be that set you'd
> > have to be able to take nth roots of any number with these
> > operations (and solve more general polynomials) but thats
> > equivalent to deviding or multiplying by an arbitary integer.
> > I don't see any way of doing that so I suspect the constructable
> > set is not the algebraic numbers, but I don't see any proof.
> >
> Yep, I can't see how to get n * x from x either, because
> there's no recursive operation to get (n + 1) * x from
> n * x short of rebuilding x again - and we can't store
> stuff.
>
We can add one because of the trigometric identities
but multiplying would seem to require an infinite
set of such identities. I'd suspect there isn't any finite
set of functions whose compositions include n*x for
all integer n.
> > The constructable set does include all quadratic and cubic
> > irrationals, e, pi, and the log of every integer, so it includes
> > most of the best known transcendentals.
> >
> Can you claim that some number is *not* constructable?
>
I'd claim 5^(1/5) isn't constructable, but I don't know
how to prove it.
--
Robert
