Proof involving functions.

I have a statement to prove:

If f: A-->B is onto ... then prove that there exists a function g: B-->A such that g is one-to-one.

.

.

What i've come up with as a proof is the following:

Let xeA, and yeB, and f(x)=y, and g(y)=x (e is "element of")

Then suppose f is onto.

Thus: For all y there exists some x s.t. f(x)=y

Thus: There exists a y s.t. f(x*)=y or there exists a y s.t. f(x**)=y

Thus: If there exists a y s.t. f(x*)=y=f(x**); then by definition of a function, we know that x*=x**

Thus: for all x s.t. f(x)=y, then f(x*)=f(x**) means that x*=x**

...Aplying the equivalences given at the beggining:

if y*=y** then we can deduce that g(y*)=g(y**)

Thus: (with insecurity =( ...) There exists a function g: B-->A such that g is one-to-one.

I know i am commiting logical errors, but i cant seem to find another way to do this proof. Any suggestions will be greatly appreciated!

Re: Proof involving functions.

Quote:

Originally Posted by

**Arturo_026** prove:

If f: A-->B is onto ... then prove that there exists a function g: B-->A such that g is one-to-one.

$\displaystyle {\forall t \in B}$ define $\displaystyle A_t$ such that $\displaystyle x\in A_t$ if and only if $\displaystyle f(x)=t.$

Because $\displaystyle f$ is onto, each $\displaystyle A_t\not=\emptyset$.

Moreover if $\displaystyle t\in B~\&~s\in B$ such that $\displaystyle t\ne s$ then $\displaystyle A_t\cap A_s=\emptyset.$

Now use those sets to construct a one-to-one function $\displaystyle g:B\to A$.

Re: Proof involving functions.

Plato's idea is correct. I'd like to comment on your proof.

Quote:

Thus: If there exists a y s.t. f(x*)=y=f(x**); then by definition of a function, we know that x*=x**

The definition of a function says that if f(x) = y* and f(x) = y**, then y* = y**. What you wrote is true only if f is one-to-one.

Concerning the rest, writing a proof should be similar to writing a computer program, which is a sequence of instructions for building certain objects. In a program, it is important that every object that you use has already been built, and it is important to know the *scope* of each object, i.e., places where you can refer to it.

Quote:

Originally Posted by

**Arturo_026** Let xeA, and yeB, and f(x)=y, and g(y)=x (e is "element of")

Quote:

Originally Posted by

**Arturo_026** Thus: There exists a y s.t. f(x*)=y or there exists a y s.t. f(x**)=y

Here you used g, x* and x** without defining them. Using g is especially problematic because this is what the problem asks to construct in the first place.

Typically, ways to introduce a variable x are:

(1) "for all x ..."

(2) "there exists an x such that ..."

(3) "let x = ..."

(4) "fix some x from the set ..."

In (1) and (2), the scope of x is the current sentence, which means that you usually can't refer to x in the following sentences. In (3) and (4), the scope of x is the rest of the proof. In those cases, of course, it is not good to introduce other objects later with the same names.

Usually if a variable is used without such introductions, it is assumed that it is introduced by "for all". E.g.,

"Since f is onto, if y ∈ B, then there exists an x ∈ A such that f(x) = y"

means

"Since f is onto, *for all* y, if y ∈ B, then there exists an x ∈ A such that f(x) = y."

So, in your future proofs, ask yourself for each variable that you use, how this variable was introduced and what its scope is.

Re: Proof involving functions.

Quote:

Originally Posted by

**emakarov** So, in your future proofs, ask yourself for each variable that you use, how this variable was introduced and what its scope is.

This was, and will be tremendously helpful. Thank you so much!

Re: Proof involving functions.

Quote:

Originally Posted by

**Plato** $\displaystyle {\forall t \in B}$ define $\displaystyle A_t$ such that $\displaystyle x\in A_t$ if and only if $\displaystyle f(x)=t.$

Because $\displaystyle f$ is onto, each $\displaystyle A_t\not=\emptyset$.

Moreover if $\displaystyle t\in B~\&~s\in B$ such that $\displaystyle t\ne s$ then $\displaystyle A_t\cap A_s=\emptyset.$

Now use those sets to construct a one-to-one function $\displaystyle g:B\to A$.

I am very surprised and also scared to know that I was supposed to come up with something like this.

Anyways, taking your guidence, I've spent a lot of time trying to construct g s.t. it is 1-1.

And this is what I was able to think of:

Let A be a set s.t A=A_t U A_s

Thus we can construct a function g:B-->A s.t. if teB & seB such that s "not equal to" t, then there exists A_t "subset of" A & A_s "subset of" A s.t. A_t "not equal to" A_s.

Therefore there exists a g s.t. this is one-to-one.

How close (or far) was I?

Thank you

Re: Proof involving functions.

Quote:

Originally Posted by

**Arturo_026** Thus we can construct a function g:B-->A

By the *choice axiom* we can choose one element from each $\displaystyle A_t$ call it $\displaystyle \mathbf{c}_t$

Then if $\displaystyle t\in B$ define $\displaystyle g(t)=\mathbf{c}_t$