Re: ~ Proof techniques for surjectivity.

From: Adam (addam_at_rogers.com)
Date: 07/21/04 

Date: Wed, 21 Jul 2004 17:45:38 GMT

"Bruce Ikenaga" <bikenaga@bellatlantic.net> wrote in message
news:pan.2004.07.21.02.52.34.906000@bellatlantic.net...
> The method you use depends on the particular case. Other
> people have provided some good ideas which will often
> work to prove surjectivity using counting arguments and
> other indirect means. But maybe you were thinking of
> situations where you have a particular function and you
> want to show it's surjective directly, using the definition.
> Here's an example.
>

    I usually have a definition for the function I wish to show is
surjective, but often it is made up of functions from sets of function to
sets of functions. With all the parentheses and things, the functions aren't
very nice to work with. So trying to find an inverse for them gives me
pains.

    Your example was very well put together. I thank you for it. I will use
it for polynomial functions and things, but for sets of functions, I am not
sure if it will be so simple. However, I will give it a try.

> You wrote elsewhere that "the author of my book frequently
> uses this technique, but I am at a loss as to how he finds
> the element that is mapped". The procedure above shows how
> this is done: Take an arbitrary element of the target set,
> *assume* that it's f(some input), then solve for (some
> input) in terms of the arbitrary element. If you think
> about it, this is exactly what you did to find the inverse
> of a function back in algebra/precalculus/calculus/wherever
> you learned about inverse functions. Here you're finding
> a formula for a right inverse (if there is one); in the
> case where the function is bijective, it will turn out to
> be a left inverse as well.
>
    Yes, the author initially was showing his "scratchwork," but then states
that he will no longer do so and that many of the proofs will seem to come
out of nowhere, but that is just because the readers can not see his
reasoning and scratchwork. I take that is the case when he defines an
element to prove surjectivity.

> Note that the "solving for the input in terms of the
> output" really is working backwards, and a proper
> proof requires that you check that your guess really
> works.

    I am aware. The author emphasized the errors of backwards proofs. I had
no idea that I was doing backwards proofs all throughout highscool! None of
my teachers said otherwise when we submitted math answers.

    Thank you, Adam.