# Homework Help: Functions, one to one, subsets, intersections

1. Aug 6, 2009

### zacharyh

The problem statement, all variables and given/known data
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?

2. Aug 6, 2009

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

3. Aug 6, 2009

### VietDao29

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

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

4. Aug 6, 2009

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

5. Aug 6, 2009

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

6. Aug 6, 2009

### mathie.girl

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.

7. Aug 6, 2009

### Landau

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).
Not much better, but the only right way. The first attempt was just wrong.

8. Aug 8, 2009

### VietDao29

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

9. Aug 8, 2009

### zacharyh

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

... was it that easy?

10. Aug 9, 2009

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

11. Aug 9, 2009

### VietDao29

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

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