1. ## a theorem about one to one functions

hi

I am trying to prove the following theorem.

Suppose A,B,C are sets and $f:B\longrightarrow C$

Suppose that $A\neq \varnothing$ and for all functions $g\;$and
$h$ from $A\longrightarrow B$

$[(f\circ g=f\circ h)\Rightarrow (g=h)]$

Prove that $f$ is one-to-one.

Since a universal statement about functions g and h is given , I think we are
supposed to exploit this. I am not able to come up with functions g and h suitable for the situation. Can anybody give some hints ?

2. ## Re: a theorem about one to one functions

Originally Posted by issacnewton
Suppose A,B,C are sets and $f:B\longrightarrow C$
Suppose that $A\neq \varnothing$ and for all functions $g\;$and $h$ from $A\longrightarrow B$
$[(f\circ g=f\circ h)\Rightarrow (g=h)]$
Prove that $f$ is one-to-one.
Suppose that $\{s,t\}\subseteq B$ and $s\ne t$ but $f(s)=f(t)$.

Define $\left( {\forall x \in A} \right)\left[ {g:x \mapsto s\;\& \,h:x \mapsto t} \right]$.

What happens now?

3. ## Re: a theorem about one to one functions

I was thinking about the nature of the sets A,B,C . lets consider the cases.
first if both B and C are empty sets then only empty function is possible from B to C.
There is one condition given in the problem. Let me put that in logical format.

$\forall g\forall h[(g:A\mapsto B)\wedge(h:A\mapsto B)\Rightarrow ((f\circ g=f\circ h)\Rightarrow (g=h))]$

so in the case when $B=\varnothing \; C=\varnothing$ , the above condition is satisfied since the antecedent will always be false. Also the only empty function is also one to one since the condition

$\forall b_1 \forall b_2[(b_1\in B)\wedge(b_2\in B)\Rightarrow(f(b_1)=f(b_2)\Rightarrow b_1=b_1)]$

will always be satisfied.

Next, consider the case where $B=\varnothing \; C\neq \varnothing$

again , similar reasoning holds. the only function from B to C is an empty function, which satisfies both of the above conditions.

Now consider the case where , $B\neq \varnothing \; C=\varnothing$

here the only relation from B to C is an empty relation, which is not a function.
since the problem states that $f:B\mapsto C$ , we need not consider this case.

So we finally come to the case where , $B\neq \varnothing \;C\neq \varnothing$

now here I have problem with your reply. Whenever we have a statement of the
form $B\neq \varnothing$ , we immediately use existential statement
$\exists b\in B$ and we then do existential instantiation. But you
say

"Suppose $\{s,t\}\subseteq B$"

how do we know there are two elements in B ?. All we can do here is existential instantiation, like I said.

4. ## Re: a theorem about one to one functions

Originally Posted by issacnewton
So we finally come to the case where , $B\neq \varnothing \;C\neq \varnothing$
"Suppose $\{s,t\}\subseteq B$"

how do we know there are two elements in B ?. All we can do here is existential instantiation, like I said.
If set $B$ has only one element then any $f:B\to C$ is one-to-one.

5. ## Re: a theorem about one to one functions

so we will need to make that a special case then. so after that is done ,.... we proceed as follows..

we argue that let B have more than one element and I think your reply now makes sense and I will think about it.

6. ## Re: a theorem about one to one functions

Originally Posted by issacnewton
so we will need to make that a special case then. so after that is done ,.... we proceed as follows..
we argue that let B have more than one element and I think your reply now makes sense and I will think about it.
I really think you are making far to much out of a simple problem.
$f:B\to C$ is injective if and only if $f(s)=f(t) \Rightarrow \,s = t$.

Equivalently $f:B\to C$ is injective if and only if $s\ne t \Rightarrow \,f(s)\ne f(t)$.

7. ## Re: a theorem about one to one functions

It's quite simple (using Plato's hint):

Suppose, toward a contradiction, that f is not 1-1.

So there is an s in B and a t in B such that ~s=t but f(s) = f(t).

Let g = {<x s> | x is in A} and h = {<x t> | x is in A}.

Both g and h are functions from A into B.

And for all x in A, we have f(g(x)) = f(s) = f(t) = f(h(x)).

So g=h.

Let x be in A. So <x s> = <x t>. So s=t. Contradiction.

/

That does it. There's no need for fussing about whether B is empty or not, and no need for any queries as to the nature of C in any way at all.

8. ## Re: a theorem about one to one functions

Originally Posted by Plato
I really think you are making far to much out of a simple problem.
probably. But since the problem is from Velleman's "How to prove it", I am just trying to be logically rigorous. The book emphasizes that point. But the author states that these logical steps are for us to understand the logical structure of the proof. In actual proof, we skip these steps and shorten the proof.

Moeblee, that was the line on which I was thinking. But problem just states that B, C are sets , so I was wondering the consequences of their being empty. Since empty function is possible , I just wanted to explore where it leads to..........

$\smile$

9. ## Re: a theorem about one to one functions

Of course, no harm in exploring where things lead. My only point is that for the proof, it's not required to wonder what happens when B is empty nor is any wondering whatsoever about C needed.

When we take the reductio ad absurdum assumption that f is not 1-1, we get that B has at least two distinct members, call them 's' and 't'. And, as to C, the proof doesn't rely on mentioning anything particular about C. Indeed the problem doesn't even have to mention C or even B. It could just be:

Suppose f is a function.

Suppose A is nonempty.

Suppose, for all g and h, if g is function from A into the domain of f, and h is a function from A into the domain of f, and fog = foh, then g=h.

Show: f is 1-1.

gotcha