GATE CSE 2001 | Question: 2.3

Question

Let $f: A \rightarrow B$ a function, and let E and F be subsets of $A$. Consider the following statements about images.

• $S_1: f(E \cup F) = f(E) \cup f(F)$
• $S_2: f(E \cap F)=f(E) \cap f(F)$

Which of the following is true about S1 and S2?

• A. Only $S_1$ is correct
• B. Only $S_2$ is correct
• C. Both $S_1$ and $S_2$ are correct
• D. None of $S_1$ and $S_2$ is correct

Comments

 

Statement 1:

$$f(E \cup F) = f(E) \cup f(F)$$

Proof

LHS : ($f(E \cup F) \subseteq f(E) \cup f(F)$)

Take any  element $y \in f(E \cup F)$.

By definition, there exists some $x \in (E \cup F)$ such that $y = f(x)$.

Since $x \in (E \cup F)$,  either:

$x \in E$, or

$x \in F$.

If $x \in E$, then $y \in f(E)$. If $x \in F$, then $y \in f(F)$.

Thus, $y \in f(E)$ or $y \in f(F)$, which means:

$$y \in f(E) \cup f(F)$$

Therefore:

$$f(E \cup F) \subseteq f(E) \cup f(F)$$

RHS :  ($f(E) \cup f(F) \subseteq f(E \cup F)$)

Take any element $y \in f(E) \cup f(F)$. This implies either:

$y \in f(E)$, meaning $y = f(x)$ for some $x \in E$, or

$y \in f(F)$, meaning $y = f(x)$ for some $x \in F$.

In either scenario, the element $x$ belongs to the combined set, so $x \in (E \cup F)$.

Consequently, $y = f(x)$ means $y \in f(E \cup F)$.

Therefore:

$$f(E) \cup f(F) \subseteq f(E \cup F)$$

Combining both LHS and RHS :

$$\boxed{f(E \cup F) = f(E) \cup f(F)}$$

 

Statement 2: 

$${f(E \cap F) \subseteq f(E) \cap f(F)}$$

Proof : 

Take any element $y \in f(E \cap F)$.

This means $y = f(x)$ for some specific element $x \in (E \cap F)$.

Since $x$ belongs to the intersection, it must  satisfy $x \in E$ and $x \in F$.

This directly leads to:

$$y \in f(E) \quad \text{and} \quad y \in f(F)$$

Therefore, by definition of intersection:

$$y \in f(E) \cap f(F)$$

Hence:

$$f(E \cap F) \subseteq f(E) \cap f(F)$$

 

---

@legend_of_cse nicely written :)

---

Caption

Answer 1

Say $E=\{1,2\}$ and $F=\{3,4\}.$

• $f(1)=a$
• $f(2)=b$
• $f(3)=b$
• $f(4)=d$

$f(E\cup F)=f(1,2,3,4)=\{a,b,d\}$
$f(E)\cup f( F)=f(1,2)\cup f(3,4)=\{a,b\}\cup \{b,d\}=\{a,b,d\}$

Now, $E\cap F=\emptyset$
$f(E\cap F)=f(\emptyset)=\emptyset$

But, $f(E)\cap f(F)=f(1,2)\cap f(3,4)=\{a,b\}\cap \{b,d\}=\{b\}$

So, $S_2$ is not true. $S_1$ is always true (no counter example exists)

Correct Answer: $A$

Comments

For this type of question we need to find only one counter example to prove this statement wrong ?

---

@saswata_m

If function $f$ is defined like this, $f: A \rightarrow B$

When we write $f(S)$ where $S$ is a subset of set $A$ (domain of function $f$), we're actually using what's called the image of a set under function $f$. This is a standard notation in set theory defined as:

$f(S) = \{ f(x) | x \in S \}$

In other words, when we apply function $f$ to a set $S$, we're getting the set of all outputs $f(x)$ where $x$ is any element in set $S$.

So, here $\phi \subseteq A$. hence, $\boxed{f(\phi) = \phi}$ is a valid mathematical statement.

PS: for $f(S)$ to be defined, $S$ should be necessarily a subset of set $A$ (domain of function $f$). If $S$ contained elements not in $A$, we couldn't evaluate $f(S)$ because $f$ isn't defined for those elements.

---

basically in this question, there are 4 scenarios possible:

1) $S_1 \cap S_2 = \phi$  and  $f(S_1) \cap f(S_2) = \phi$

• $f(S_1 \cup S_2) = f(S_1) \cup f(S_2) \quad \text{:} \quad \text{True}$
• $f(S_1 \cap S_2) = f(S_1) \cap f(S_2) \quad \text{:} \quad \text{True}$

2) $S_1 \cap S_2 \neq \phi$  and  $f(S_1) \cap f(S_2) = \phi \quad \text{:} \quad \text{Not Possible}$

3) $S_1 \cap S_2 = \phi$  and  $f(S_1) \cap f(S_2) \neq \phi$

• $f(S_1 \cup S_2) = f(S_1) \cup f(S_2) \quad \text{:} \quad \text{True}$
• $f(S_1 \cap S_2) = f(S_1) \cap f(S_2) \quad \text{:} \quad \text{False}$
  proof (by counter-example): suppose, $S_1 = \{ a,b, c\}$ and $S_2 = \{ d, e, g\}$
  $f(S_1) = \{ 1, 2, 3\}$
  $f(S_2) = \{ 3, 4, 2\}$
  $f(S_1) \cap f(S_2) = \{ 1, 2, 3\} \cap \{ 3, 4, 2\} = \{ 2, 3 \}$
  $f(S_1 \cap S_2) = f(\{ \}) = \{ \}$
  hence, $f(S_1 \cap S_2) \neq f(S_1) \cap f(S_2)$

4) $S_1 \cap S_2 \neq \phi$  and  $f(S_1) \cap f(S_2) \neq \phi$

• $f(S_1 \cup S_2) = f(S_1) \cup f(S_2) \quad \text{:} \quad \text{True}$
• $f(S_1 \cap S_2) = f(S_1) \cap f(S_2) \quad \text{:} \quad \text{May or may not be True}$
  proof 1): suppose, $S_1 = \{ a,b, c\}$ and $S_2 = \{ c, d, e, g\}$
  $f(S_1) = \{ 1, 2, 3\}$
  $f(S_2) = \{ 3, 3, 4, 2\} = \{ 3, 4, 2\}$
  $f(S_1) \cap f(S_2) = \{ 1, 2, 3\} \cap \{ 3, 4, 2\} = \{ 2, 3 \}$
  $f(S_1 \cap S_2) = f(\{ c \}) = \{ 3 \}$
  hence, $f(S_1 \cap S_2) \neq f(S_1) \cap f(S_2)$
  proof 2): suppose, $S_1 = \{ a,b, c\}$ and $S_2 = \{ c, d, e\}$
  $f(S_1) = \{ 1, 2, 3\}$
  $f(S_2) = \{ 3, 3, 4 \} = \{ 3, 4 \}$
  $f(S_1) \cap f(S_2) = \{ 1, 2, 3\} \cap \{ 3, 4 \} = \{ 3 \}$
  $f(S_1 \cap S_2) = f(\{ c \}) = \{ 3 \}$
  hence, $f(S_1 \cap S_2) = f(S_1) \cap f(S_2)$

Answer 2

Here Answer is A .

S1 is always True.

S2 is false Consider case where E & F do not intersect, i.e. Intersection is empty set. In that case , F(E) and F(F) might have some common elements.

Comments

in the proof you shared, what’s the meaning of this?

 

f 1-1→f(A∩B)=f(A)∩f(B).

what does 1-1 imply here? sorry if this is a dumb question but I see no notation like this used in Rosen.

---

@daddy_puff it means one-to-one function.

---

@indrajeet f(A) refers to a function of set of elements. Similar is the case for E U F which is also a set. 
Say, A = {1,2} where f(1)  = f(2) = a. Then, f(A) = f({1,2}) = {a,a}

Answer 3

Answer is A , becouse ...

• S1:f(E∪F)=f(E)∪f(F)
• S2:f(E∩F)<=f(E)∩f(F)

For S2, Consider no common elements between E and F but some element in E mapping to an element x, and some other element in F also mapping to that x. Here, LHS will be empty set while RHS will have x in it. 

Answer 4

Correct Answer (A)

---

$1.\ f(A_{1}\cup A_{2})=f(A_{1})\cup f(A_{2})$

$f(A_{1}\cup A_{2})=\{y\in B|y=f(x),x\in A_{1}\cup A_{2}\}=\{y\in B|y=f(x),x\in A_{1}\ or\ x\in A_{2}\}=\{y\in B|y=f(x),x\in A_{1}\}\cup \{y\in B|y=f(x),x\in A_{2}\}=f(A_{1})\cup f(A_{2}).$

---

$2.\ f(A_{1}\cap A_{2})\neq f(A_{1})\cap f(A_{2})$

$A=\{1,2\},B=\{3,4\}$ and $f=\{(1,3),(2,3)\}$

$A_{1}=\{1\},A_{2}=\{2\}$

$f(A_{1}\cap A_{2})=f(\phi)=\phi$ while $f(A_{1})\cap f(A_{2})=\{3\}\cap \{3\}=\{3\}$

---

Note : 

$f(A_{1}\cap A_{2})\subseteq f(A_{1})\cap f(A_{2})$

$f(A_{1}\cap A_{2})=f(A_{1})\cap f(A_{2})$ if f is ONE-ONE

Answer 5

S1:- $\mathrm{f(E} \cup \mathrm{F) = f(E) \cup f(F)}$,

Let's assume $\mathrm{x} \in \mathrm{f(E \cup F)}$, then it implies $\exists y \in \mathrm{E \cup F}$ such that $f(y) = x $.

case1:- $y \in E$, then $f(y)( = x ) \in f(E)$, which implies $f(y) \in f(E \cup F)$.

case2:- $y \in F$, then $f(y)(= x) \in f(F)$, which implies $f(y) \in f(E \cup F)$.

case3:- $y \in E \cap F$, then $f(y)( = x) \in f(E \cap F)$, which implies $f(y) \in f(E \cup F)$.

In any of those cases, if $x \in f(E \cup F)$ then $x \in f(E) \cup f(F)$.

 

Lets assume $x \in f(E) \cup f(F)$. it implies $x \in f(E)$ or $ f(F))$, $\exists y_1\in E$ such that $f(y_1) = x$ or $\exists y_2\in F$ such that $f(y_2) = x$.

in either the case at least one of $y_1, y_2 \in E \cup F$, which implies $x \in f(E \cup F)$.

if $x \in f(E) \cup f(F)$ then $x \in f(E \cup F)$ .

Now we can conclude that both sets are equals ($f(E \cup F)$ =  $f(E) \cup f(F)$)

Hence S1 is correct.

 

S2. $\mathrm{f(E} \cap \mathrm{F) = f(E) \cap f(F)}$

lets assume $\mathrm{x} \in \mathrm{f(E \cap F)}$ $\implies \exists y \in E \cap F$ such that $f(y) = x$.

since $y \in E$ and $y \in F \implies f(y)(= x) \in f(E) , f(y) \in f(F)$, it implies that $x \in f(E)\cap f(F).$

so we can conclude that $\mathrm{f(E} \cap \mathrm{F) \subset f(E) \cap f(F)}$.

so the other side consider this counter example, $\mathrm{f : R \mapsto R}$, such that $\mathrm{f(x) = x^2}$ $\forall x \in \mathrm{R}.$

let $\mathrm{E = \set{1,2}}$ and $\mathrm{F = \set{-1,-2}}$ then $f(E \cap F) = \set{}$ and $f(E) \cap f(F) = \set{1,4}$.

so we can conlude that $\mathrm{f(E} \cap \mathrm{F) \neq  f(E) \cap f(F)}$.

so S2 is incorrect.

 

Hence option A is correct.

Answer 6

The correct option is A Only S1 is correct
 

Given a function f:x→y and subsets E and F of A then we have
 

f(E∪F)=f(E)∪f(F) and
f(E∩F)⊆f(E)∩f(F)

Therefore S1 is correct and S2 is false.