a theorem about one to one functions

hi

I am trying to prove the following theorem.

Suppose A,B,C are sets and

Suppose that and for all functions and

from

Prove that 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 ? (Emo)

Re: a theorem about one to one functions

Quote:

Originally Posted by

**issacnewton** Suppose A,B,C are sets and

Suppose that

and for all functions

and

from

Prove that

is one-to-one.

Suppose that and but .

Define .

What happens now?

Re: a theorem about one to one functions

thanks plato for replying

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.

so in the case when , 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

will always be satisfied.

Next, consider the case where

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 ,

here the only relation from B to C is an empty relation, which is not a function.

since the problem states that , we need not consider this case.

So we finally come to the case where ,

now here I have problem with your reply. Whenever we have a statement of the

form , we immediately use existential statement

and we then do existential instantiation. But you

say

"Suppose "

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

Re: a theorem about one to one functions

Quote:

Originally Posted by

**issacnewton** So we finally come to the case where ,

"Suppose

"

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

If set has only one element then any is one-to-one.

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.

Re: a theorem about one to one functions

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.

Re: a theorem about one to one functions

Quote:

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..........

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.

Re: a theorem about one to one functions