edited by
5,888 views
14 votes
14 votes

Let $f: A \rightarrow B$ be an onto (or surjective) function, where $A$ and $B$ are nonempty sets. Define an equivalence relation $\sim$ on the set $A$ as
\[
a_{1} \sim a_{2} \text { if } f\left(a_{1}\right)=f\left(a_{2}\right),
\]
where $a_{1}, a_{2} \in A$. Let $\mathcal{E}=\{[x]: x \in A\}$ be the set of all the equivalence classes under $\sim$. Define a new mapping $F: \mathcal{E} \rightarrow B$ as
\[
F([x])=f(x), \quad \text { for all the equivalence classes }[x] \text { in } \mathcal{E} \text {. }
\]
Which of the following statements is/are $\text{TRUE}?$

  1. $F$ is NOT well-defined.
  2. $F$ is an onto (or surjective) function.
  3. $F$ is a one-to-one (or injective) function.
  4. $F$ is a bijective function.
edited by

3 Answers

16 votes
16 votes
Here, equivalence relation $\sim$ on the set $A$ is defined as:
$$a_1 \sim a_2 \ \ if \ \ f(a_1)=f(a_2) $$

where $a_1,a_2 \in A$

So, consider $a_i,b_i,c_i,..\in A$ and $\alpha,\beta,\gamma,...\in B$ and the mapping as:

$a_1 \mapsto \alpha$, $a_2 \mapsto \alpha $,  $a_3 \mapsto \alpha,...$, $a_m \mapsto \alpha$

Similarly,

$b_1 \mapsto \beta$, $b_2 \mapsto \beta$,  $ \ b_3 \mapsto \beta,$$...$$,b_n \mapsto \beta$

$c_1 \mapsto \gamma$, $c_2 \mapsto \gamma$,  $\ c_3 \mapsto \gamma,$$...$$,c_p \mapsto \gamma$

and so on for the non-empty sets $A$ and $B$ and it is given that $f: A \rightarrow B$ is an onto function.

According to the definition of Equivalence relation, Equivalence class is:

$[a_1]=[a_2]=[a_3]=...=[a_m]$

$[b_1]=[b_2]=[b_3]=...=[b_n]$

$[c_1]=[c_2]=[c_3]=...=[c_p]$

and so on.

Now, set of equivalence classes under relation $\sim$ is defined as:

$\mathcal{E}= \{[a_1],[b_1],[c_1],...\}$

Now, given the new mapping $F: \mathcal{E} \rightarrow B$ as:

$F([x]) = f(x)$ for all $[x] \in \mathcal{E}$

It means mapping would be:

$a_1 \mapsto \alpha$

$b_1 \mapsto \beta$

$c_1 \mapsto \gamma$

and so on.

Since, all distinct $a_1,b_1,c_1,...$ maps to different elements of set $B$ and so, $F$ is an injective function. Here, we have taken $a_1,b_1,c_1,...$ as a leader for their own equivalence classes, you can take $a_2,b_2,c_2,... $ so on.

It is cleared from the mapping of $F$ that all the elements of set $B$ are covered,so, $F$ is surjective function because each element from their own equivalence class maps to according to the mapping of $f.$ We have taken one element from the group of $a's$ and maps to $\alpha$ and similarly for other groups of $b's, c's$ and so on.

Since, $F$ is both injective and surjective and hene $F$ is bijective function.

Here, we say, function $F$ well-defined or single-valued when:

$1)$ $F \subseteq [x] \times f(x)$

$2)$ The domain of $F$ is $[x]$

$3)$ if $([x],y), ([x],z)$ then $y=z$

Since from the mapping of $F$, it is cleared all the above three conditions are true because we have taken one element from the group of $a's,b's,c's,...$ and maps to $\alpha, \beta,\gamma,...$ and so, $f$ is well-defined function.

$\textbf{Therefore, (B),(C),(D)}$
9 votes
9 votes
It is given that $f$ is function defined from domain $A$ to co-domain $B$, $f:A \rightarrow B$, and $f$ is surjective, in other and simple words, $\text{“every element of $B$ has pre-image or is mapped by some element(s) in $A$”}$. Mathematically this can be defined as $$\displaystyle \mathbf{\forall}_{y \ \in B} \ \mathcal{\exists}_{x \ \in A} \ y = f(x) \tag{1}$$ Since $f$ is function, so no element in $A$ can be left unmapped to some element in $B$.

Let,

$$\begin{align}A &= \{x_1, x_2, \dots, x_a, \dots, x_b, \dots, x_n\} \cr B &= \{y_1, y_2,\dots, y_n\}\end{align}$$

It is given that $\forall _{a_1, a_2 \in A} \ f(a_1) = f(a_2) \Rightarrow a_1R_Ea_2$, where $R_E$ is equivalence relation, so instead of $\sim$ I’m using that notation.  

Now, according to defintion $(1)$, some elements of $A$ (say) $x_1,x_2,x_3$ would map to $y_i \in B$, similarly (say) $x_4, x_5$ would map to $y_j \in B$, hence sets of $x$ values forms a disjoint set while mapping to $y_i$ and $y_j$. So there are $|B|-1$ partitions or $|B|$ parts of $A$ and all of them are disjoint.

Let,

$$\begin{align}A_1 &= \{x_1, \dots, x_a\}; \ \forall _{x_i \in A_1} f(x_i) = y_1 \cr A_2 &= \{x_{a+1}, \dots, x_b\}; \ \forall _{x_i \in A_2} f(x_i) = y_2 \cr & \quad \vdots \cr A_n &= \{x_{m+1}, \dots, x_n\}; \ \forall _{x_i \in A_n} f(x_i) = y_n\end{align}$$

Let, $$\begin{align}& \ \ \ \ \ \forall_{a_1 \in A_1, a_2 \in A_2} \ f(a_1) \neq f(a_2) \Rightarrow a_1R_Ea_2 \cr &\equiv \forall_{a_1 \in A_1, a_2 \in A_2} \ False \Rightarrow a_1R_Ea_2 \cr &\equiv \forall_{a_1 \in A_1, a_2 \in A_2} \ True \cr &\equiv True\end{align}$$Although, whole first order logic expression is $True$ but it doesn't tell us about the truth value of $a_1R_Ea_2$, expression would be $True$ even if $a_1R_Ea_2$ or $a_1\cancel{R_E}a_2$, but we are actually concerned with $a_1R_Ea_2$. So lets’ make $a_1R_Ea_2 \equiv True$, then to make FOL expression $True$, $f(a_1)=f(a_2) \equiv True$. But this can only be $True$ when $a_1, a_2 \in A_i$. Using this we can say that $[a_j] = [a_k]: a_j,a_k \in A_i$, where $[.]$ is equivalence class.

So we get this,
$$\begin{align}\mathcal{Q} &= \{[x]: x \in A_j;  1 \leq j \leq n\}\cr &= \{[x]: x \in A_1 \cup A_2 \cup \dots \cup A_n\} \cr &= \{[x]: x \in A\}\end{align}$$

Now $\mathcal{Q}$ is similar to given set $\mathcal{E} = \{[x]: x \in A\}$ where $\mathcal{E}$ is set of all equivalance classes under $R_E$. New function $F$ has been defined as $F([x]) = f(x)$, and $F: \mathcal{Q} \rightarrow B$.
We can also write $\mathcal{Q}$ as, $$\mathcal{Q} = \{[x \in A_1], [x \in A_2], \dots, [x \in A_n]\} \tag{2}$$ $$\mathcal{Q} = \{\{x_1, x_2, \dots, x_a\}, \{x_{a+1}, \dots, x_b\}, \dots, \{x_{m+1}, \dots, x_n\}\} \tag{3}$$

If we look closely to $F$ then $F$ is taking $q \in \mathcal{Q}$ as an argument and we already know that $\exists_{y \in B}\forall_{x \in q} \ y = f(x)$ where $y$ is unique, hence $F(q)$ is unique. This shows that $\forall_{q_1, q_2 \in \mathcal{Q}} \ q_1 \neq q_2 \Rightarrow F(q_1) \neq F(q_2)$ which is definition of $\textbf{one-one}$ function.

In the beginning of the answer, we found the number of partitions sets or number of equivalence classes as $|B|$, this means $|\mathcal{Q}| = |B|$, here we can observe number of elements in domain is same as number of elements in co-domain and we already found $F$ to be one-one, so from here we can conclude $F$ is $\textbf{onto}$ function too.
 

$F$ is $\textbf{one-one}$ and $\textbf{onto}$, hence $F$ is $\textbf{bijective}$.

Since its MSQ type question,

$\textbf{(B), (C), (D)}$ are correct options.
edited by
Answer:

Related questions