[COMP2121] Discrete Mathematics - Question on Function

Description

Let $A$ be a finite set, and let $F(A)$ be the set of all functions from $A$ to itself. Consider the relation $R$ on $F(A)$ defined by $fRg$ if and only if there exists a function $h \in F(A)$ such that $f=h \circ g$. 

The function $h \circ g: A \rightarrow A$ is defined as $(h \circ g)(x)=h(g(x))$.

(Drawing diagrams will be very helpful for this question.)

(a) (6pt) Is the relation $R$ reflexive? Is the relation $R$ transitive? Prove your answer.

(b) (4pt) For every element $a \in A$, let $f^{-1}({a}):=\left\{ x \in A | f(x)=a \right\}$ be the level set of the function $f$, that is, the set of all preimages of $a$. Let $L_f:=\left\{f^{-1}({a}) | a \in A, f^{-1}(a) \neq \varnothing \right\}$ be the set of all level sets of $f$. 

Show that, if $fRg$, then there exists a surjective function $k:L_g \rightarrow L_f$ satisfying the property that $S \subseteq k(S)$ for every $S \in L_g$.

(c) (3pt) Show that if there exists a surjective function $k:L_g \rightarrow L_f$ such that $S \subseteq k(S)$ for every $S \in L_g$, then $fRg$.

(d) (3pt) Show that if $fRg$ and $gRf$, then $L_f=L_g$.

Solution

(a) reflexive: $\forall f \in F(A),\ fRf$

Let $h=Id_A$, i.e. $h(x)=x$.

Then $\forall f \in F(A), \forall x \in A$, $f(x)=h(f(x))$, i.e. $f=h \circ f$.

Thus, $R$ is reflexive.

transitive: $\forall f_1, f_2, f_3 \in F(A),\ (f_1Rf_2 \wedge f_2Rf_3) \rightarrow f_1Rf_3$

Assume we have $f_1=h_1 \circ f_2$ and $f_2=h_2 \circ f_3$.

Let $h_3=h_1 \circ h_2$, then $\forall x \in A$, $h_3 \circ f_3 (x) = h_3(f_3(x)) = h_1(h_2(f_3(x))) = h_1(f_2(x)) = f_1(x)$, i.e. $f_1=h_3 \circ f_3$, $f_1Rf_3$.

Thus, $R$ is transitive.

(b) Things observed:

• the elements of $L$ are sets
• $L_g$ groups elements in $A$ together if they have the same output from function $g$. Same for $L_f$
• As $f=h(g(x))$, $L_f$ is formed by grouping some existing groups in $L_g$ together (if their outputs from $g$ have the same output from $h$)

Prove that $\forall S \in L_g,\ \exists S' \in L_f, S \subseteq S'$:

    Assume we have $\forall a \in S,\ g(a)=b$, and $h(b)=c$, i.e. $f(a)=c$

    Then $a \in f^{-1}({c})$, i.e. $S' = f^{-1}({c})$

Using this, we can define $k: L_g \rightarrow L_f,\ k(S)=S'$

Next, prove $k$ is surjective, i.e. $\forall S' \in L_f,\ \exists S \in L_g,\ k(S)=S'$:

    Assume we have $forall a \in S',\ g(a)=b$

    Then $a \in g^{-1}({b})$, i.e. $S=g^{-1}({b})$

(c) objective: find a function $h$ such that $f=h \circ g$

Define $h:\ \forall b \in A, g^{-1}({b}) = S \neq \o,\ a \in k(S),\ h(b) = f(a)$

Because $S \subseteq k(S)$, so $f(S)=f(k(S))$

In this way, $f = h \circ g$

(d) TBC.