# Functions, one to one, subsets, intersections

• zacharyh
In summary: Now, working on the forward direction:(=>)Assume f(X \cap Y) = f(X) \cap f(Y). Let a,b \in A such that f(a) = f(b). Then, f(a) = f(b) \in f(X) \cap f(Y). Then, f(a) \in f(X \cap Y). This means that there exists c \in X \cap Y such that f(a) = f(c). Then, a = c. Similarly, f(b) \in f(X \cap Y) \Rightarrow b = c. Therefore, a = b, proving that f is one-to-one. In summary, we have shown
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?

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.

zacharyh said:
(<=)
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. :)

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.

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.

snipez90 said:
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.

mathie.girl said:
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.

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

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

... was it that 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.

zacharyh said:

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

zacharyh said:
(=>)
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$$

## 1. What is a function?

A function is a mathematical concept that relates one input value to one output value. It can be represented as a mapping between the domain (input) and range (output) of the function. In simpler terms, it takes an input and produces a specific output.

## 2. What does it mean for a function to be one-to-one?

A one-to-one function, also known as an injective function, is a function where each input value has a unique output value. In other words, no two different input values can produce the same output value. This is often represented by the horizontal line test, where a horizontal line can only intersect the graph of a one-to-one function at most once.

## 3. What are subsets and how are they related to functions?

A subset is a set that contains elements from another set. In the context of functions, subsets are often used to describe the domain and range of a function. The domain of a function is a subset of the set of all possible input values, while the range is a subset of the set of all possible output values.

## 4. What is the intersection of two functions?

The intersection of two functions is the set of all input values that produce the same output value for both functions. In other words, it is the set of all common elements between the domain of one function and the domain of the other function.

## 5. How can I determine if two functions have the same intersection?

If two functions have the same intersection, it means that they have at least one input value that produces the same output value for both functions. To determine this, you can set the two functions equal to each other and solve for the input value. If the solution is valid for both functions, then it is a common element in the intersection. Alternatively, you can graph the two functions and see where they intersect on the graph.

Replies
20
Views
3K
Replies
8
Views
476
Replies
4
Views
934
Replies
6
Views
524
Replies
2
Views
631
Replies
1
Views
787
Replies
19
Views
533
Replies
6
Views
4K
Replies
18
Views
2K
Replies
5
Views
959