Thread: Prove that f is injective

Hello,
I need to prove that function defined like this for any two given sets X,Y is one-to-one if and only if , where .

What do I need to do to prove this?

EDIT:

I've figured out how to prove that when f is injective. I still do not know how to conclude that f is injective when .

Originally Posted by MachinePL1993

Hello,
I need to prove that function defined like this for any two given sets X,Y is one-to-one if and only if , where .
What do I need to do to prove this?

It is well known that for any function .

So you must show that equality holds if and only if the function is injective.

So assume it is injective and show equality holds. Then the converse.

Now how to prove that f is injective if the above equality holds?

In general, we always have f(AnB) included in f(A)nf(B), proof by contradiction:

let A,B subsets of X. Since f(AnB) =/= f(A)nf(B) there is an element (let's call it x) in AnB such that f(x) does not belong to f(A)nf(B). Because f(x) does not belong to f(A)nf(B), x is not in A or x is not in B. So we have an element x in AnB such that f(x) is not in A or not in B this is a contradiction.

Now let f be injective. let c be an element of f(A)nf(B). There exists c_a in A such that f(c_a)=c. And there exists c_b in B such that f(c_b)=c. Because f is injective c_a=c_b. So c is the image of an element in both A and B, so he belongs to f(AnB).

Is this correct?
Let's assume indirectly that the function is not injective

Let's choose some such that where and where , and . Then , because , and , which is a contradiction with the assumption because , so the function must be injective.

it seems correct.

Originally Posted by MachinePL1993

Is this correct?
Let's assume indirectly that the function is not injective

That proof is a bit rough. But it is the correct idea.
If we assume that equality holds, but the function is not injective then such that but .

Define .

Then but .

There is the contradiction.