Functions, one to one, subsets, intersections

[zacharyh]

Homework Statement
General Case:

Let f:A \rightarrow B be a function. Show that f( \bigcap_{\alpha\in\Lambda} T_{\alpha}) = \bigcap_{\alpha\in\Lambda} f(T_{\alpha}) for all choices of \{T_{\alpha}\}_{\alpha\in\Lambda if and only if f is one-to-one.

Simpler Case:

Let f:A \rightarrow B be a function, and X, Y be subsets of A.
Show that f(X \cap Y) = f(X) \cap f(Y) if and only if f is one-to-one.

The attempt at a solution

I am trying to understand the simpler case first before attempting a solution for the general case.

(<=)
Assume f is one-to-one. Let b \in f(X) \cap f(Y).
Then, b \in f(X), b \in f(Y). Then, \exists a (a \in X, a \in Y, f(a) = b).
This implies that a \in X \cap Y. Therefore, f(X \cap Y) = f(X) \cap f(Y).

(=>)(Our hint here is to use contraposition -- assuming the following to show f is not one-to-one.).

Assume f(X \cap Y) \neq f(X) \cap f(Y). Let u \in f(X) \cap f(Y).
Then, u \in f(X), u \in f(Y). This implies \exists a,b (a \in X, b \in Y, f(a) = f(b) = u).

If I show that a,b \notin (X \cap Y), does that mean a \neq b?
If so, then, f(a) = f(b), so f cannot be one-to-one.

Any thoughts?

 

[snipez90]

The reverse direction looks fine. Just remember that the existence of the a in that part of the proof depends on f being one-to-one, so it might help to state that. Also, remember that the conclusion from the reverse direction is f(X \cap Y) \supset f(X) \cap f(Y).

The forward direction seems needlessly complicated. This direction is true regardless of whether f is one-to-one. If b is in f(X \cap Y), then b = f(a) for some a in A such that a is X and a is in Y.

 

[VietDao29]

(<=)
Assume f is one-to-one. Let b \in f(X) \cap f(Y).
Then, b \in f(X), b \in f(Y). Then, \exists a (a \in X, a \in Y, f(a) = b).
This implies that a \in X \cap Y. Therefore, f(X \cap Y) = f(X) \cap f(Y).

No, you should not use "assume" here.

You are trying to prove: f \mbox{ is one-to-one } \Rightarrow f(X \cap Y) = f(X) \cap f(Y)

i.e, f is already one-to-one. Don't need to assume anymore. You must use this to prove that f(X \cap Y) = f(X) \cap f(Y). So, no assumption here. :)

(=>)(Our hint here is to use contraposition -- assuming the following to show f is not one-to-one.).

Assume f(X \cap Y) \neq f(X) \cap f(Y). Let u \in f(X) \cap f(Y).
Then, u \in f(X), u \in f(Y). This implies \exists a,b (a \in X, b \in Y, f(a) = f(b) = u).

If I show that a,b \notin (X \cap Y), does that mean a \neq b?
If so, then, f(a) = f(b), so f cannot be one-to-one.

Any thoughts?

In this step, you are proving that: f(X \cap Y) = f(X) \cap f(Y) \Rightarrow f \mbox{ is one-to-one }, i.e: now you have this piece of information: f(X \cap Y) = f(X) \cap f(Y), and you need to prove that f is one-to-one.

So, to use proof by contradiction, you assume that f is not one-to-one. And try to see what error it leads to.

Hope, it's clear enough. :)

 

[snipez90]

I think it's ok for the OP to use "assume" since he is just restating the hypotheses for the reverse implication. However, I clearly misread the question, as the initial proof of the reverse implication does show set equality. Sorry.

But yes, for the actual forward direction if you assume f is not one-to-one, then you should obtain an easy contradiction.

 

[zacharyh]

Attempt #2 (<=)

And yes, I'm restating the "given" information (the assumptions) for clarity.

(<=)
Assume f is one-to-one. Let b \in f(X) \cap f(Y).
Then, b \in f(X), b \in f(Y). Then, there exists c \in X, d \in Y such that f(c) = b = f(d). Since f is one-to-one, c = d. Then, c, d \in (X \cap Y) so b \in f(X \cap Y). Therefore, f(X \cap Y) = f(X) \cap f(Y).

(=>)
Working on it.

 

[mathie.girl]

I think it's ok for the OP to use "assume" since he is just restating the hypotheses for the reverse implication. However, I clearly misread the question, as the initial proof of the reverse implication does show set equality. Sorry.

But yes, for the actual forward direction if you assume f is not one-to-one, then you should obtain an easy contradiction.

I'm not sure how the initial proof shows set equality. I'm still only seeing one inclusion, \supseteq. I would think the other inclusion would need to be stated, even if it's pretty obvious. Also, the modified proof just above my post is much better since it assumes a c and d as opposed to merely one element a.

The forward direction can be done with contrapositive/contradiction (assuming that f isn't one-to-one), but could also be done with a regular one-to-one proof. Assume that f(a) = f(b) and see what falls out when you keep in mind your assumptions.

 

[Landau]

I'm not sure how the initial proof shows set equality. I'm still only seeing one inclusion, \supseteq. I would think the other inclusion would need to be stated, even if it's pretty obvious.

You are right: now only one inclusion has been proved, the other one should also be mentioned (it is trivial, but then at least say 'the other inclusion is trivial', showing you understand that both inclusion are necessary).

Also, the modified proof just above my post is much better since it assumes a c and d as opposed to merely one element a.

Not much better, but the only right way. The first attempt was just wrong.

 

[VietDao29]

Attempt #2 (<=)
...

(=>)
Working on it.

How about, assume that f is not one-to-one. By definition:

\exists c \neq d : f(c) = f(d)

Ok, now, you have to choose X, and Y wisely, so that it leads to contradiction (i.e, f(X \cap Y) \neq f(X) \cap f(Y)).

Let's see if you can go from here. :)

 

[zacharyh]

Following from your reply.

Let X = \{c\}, Y = \{d\}. Then, f(X \cap Y) = \emptyset \neq f(X) \cap f(Y)

... was it that easy?

 

[zacharyh]

(=>)
Assume f(X \cap Y) = f(X) \cap f(Y). And, assume f is not one-to-one.
Then, \exists c \neq d such that f(c) = f(d) = z. Now, let X = \{c\}, Y = \{d\}. Then, f(X \cap Y) = \emptyset \neq f(X) \cap f(Y) = \{z\}.
So our assumption that f was not one-to-one is false. Therefore, f must be one-to-one.

I think that works. Thanks for the help.
I didn't think I was allowed to choose which sets X, Y represented.

 

[VietDao29]

Following from your reply.

Let X = \{c\}, Y = \{d\}. Then, f(X \cap Y) = \emptyset \neq f(X) \cap f(Y)

... was it that easy?

That's why everyone here told you it was easy.. :)

(=>)
Assume f(X \cap Y) = f(X) \cap f(Y). And, assume f is not one-to-one.
Then, \exists c \neq d such that f(c) = f(d) = z. Now, let X = \{c\}, Y = \{d\}. Then, f(X \cap Y) = \emptyset \neq f(X) \cap f(Y) = \{z\}.
So our assumption that f was not one-to-one is false. Therefore, f must be one-to-one.

I think that works. Thanks for the help.
I didn't think I was allowed to choose which sets X, Y represented.

Perfect, congratulations.

Well, of course you can, X, and Y just need to be subsets of A; since you have c, \ d \in A, so, that means: \{ c \} , \{ d \} \subset A