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