Notes II: Sets and Functions: problems and solutions

Let f: X \rightarrow Y, let A \subseteq X, let B \subseteq Y. Then,

f(A) = \{f(x): x \in A \}

f^{-1}(B) = \{ x: f(x) \in B\}

I. The main properties of the first set mapping are:

1a) f(\phi) = \phi, f(X) \subseteq Y

1b) A_{1} \subseteq A_{2} \Longrightarrow f(A_{1}) \subseteq A_{2}

1c) f(\bigcup_{i}A_{i}) = \bigcup_{i}f(A_{i})

1d) f(\bigcup_{i}A_{i}) \subseteq \bigcap_{i} f(A_{i})

Answer I:

1a: obvious by definition of f(A) or f.

1b: obvious by definition of f

1c: Let x_{0} \in \bigcup_{i}A_{i} so that for some one i we have f(x) \in f(A_{i}). That is, f(\bigcup_{i}A_{i}) \subseteq \bigcup_{i}f(A_{i}). Reversing the arguments, we get the other subset relation. So that f(\bigcup_{i}A_{i}) = \bigcup_{i}f(A_{i}). The image of the union is the union of images.

1d: Let x_{0} \in \bigcap_{i}A_{i} so that x_{0} belongs to each A_{i}. So that LHS is clearly a subset of \bigcap_{i}f(A_{i}).

II) Now, we want to verify the following useful/famous relations of the second set mapping:

2a) f^{-1}{(\phi)} = \phi, f^{-1}(Y) = X

2b) B_{1} \subseteq B_{2} \Longrightarrow f^{-1}(B_{1}) \subseteq f^{-1}(B_{2})

2c) f^{-1}(\bigcup_{i}B_{i}) = \bigcup_{i}f^{-1}(B_{i})

2d) f^{-1}(\bigcap_{i}B_{i}) = \bigcap_{i}f^{-1}(B_{i})

2e) f^{-1}(B^{'}) = f^{-1}(B)^{'}

Answer 2a: obvious from definition.

Answer 2b: obvious from definition.

Answer 2c: Let y_{0} belong to at least one B_{i} so that x_{0} = f^{-1}(y_{0}) = f^{-1}(B_{i}) for some i. In other words, f^{-1}(\bigcup_{i}B_{i}) = \bigcup_{i}f^{-1}(B_{i})

Answer 2d:

TPT: f^{-1}(B^{'}) = f^{-1}(B)^{'}.

Let y_{0} \in f^{-1}(B^{'}).

Hence, f(y_{0}) \in B^{'}.

Hence, f(y_{0}) \in U-B, where U is the universal set

Hence, f(y_{0}) \in U-f(A)

Hence, f(y_{0}) \in U-B

Hence, f(y_{0}) \in U-f(A)

Hence, f(y_{0}) \in (f(A))^{'}

Hence, y_{0} \in f^{-1}(B)^{'}. Hence, f^{-1}(B^{'}) \subseteq f^{-1}(B)^{'}

Reversing the arguments proves the other subset inequality.

Hence, f^{-1}(B^{'}) = f^{-1}(B)^{'}. QED.

More Problems :

A) Two mappings f: X \rightarrow Y and g: X \rightarrow Y are said to be equal (and we write them as f=g) if f(x) = g(x) for every x in X. Let f, g, and h be any three mappings of a non-empty set X into itself, and now prove that the multiplication of mappings is associative in the sense that (fg)h = f(gh).

Solution A:

Let f: X \rightarrow X, g: X \rightarrow X, and h: X \rightarrow X be any three mappings of X into itself. Let x_{0} \in X and let h(x_{0}) = x_{1} \in X. Now, we know that ((fg)h)(x)= (fg)(h(x)). So that now we want to find (fg)(x_{1}) = f(g(x_{1})) = f(x_{2}) assuming g(x_{1}) \in x_{2} \in X.

Now, on the other hand, (f(gh))(x) means (f)((gh)(x)) = f(g(h(x_{0})) = f(g(x_{1}))=f(x_{2}) just as in LHS. QED.

B) Let X be a non-empty set. The identity mapping i_{X} on X is the mapping of X onto itlsef defined by i_{X}(x)=x for every x. Then, i_{X} sends each element of the set X to itself; that is, leaves fixed each element of X. Prove that fi_{X}= i_{X}f=f for any mapping f of X into itself. If f is one-to-one onto, so that its inverse f^{-1} exists, show that ff^{-1} = f^{-1}f=i_{X}. Prove further that f^{-1} is the only mapping of X into itself which has this property; that is, show that if g is a mapping of X into itself such that fg=gf=i_{X}, then g=f^{-1}. Hint: g=gi_{X}=g(ff^{-1})=(gf)f^{-1} = i_{X}f^{-1}=f^{-1}, or

g=i_{X}g=(f^{-1}f)g=f^{-1}(fg) = f^{-1}i_{X}=f^{-1}

B(i) TPT: fi_{X}=i_{X}f=f for any mapping f of X into itself. Proof: Consider x_{0}\in X and such that f(x_{0}) = x_{1}. Hence, fi_{X}(x_{0}) = f(i_{X}(x_{0}))=f(x_{0}) = x_{1} \in X = f(x_{0}). Now, on the other (i_{X}f)(x_{0}) = i_{X}(f(x_{0}))=i_{X}(x_{1})= x_{1} also. QED.

B(ii): Let f be one-to-one onto such that f: X \rightarrow X. Hence, f^{-1} exists. Also, f^{-1}: X \rightarrow X. Let f(x_{0}) = x_{1} \in X. Hence, by definition and because f^{-1} is also one-to-one and onto, f^{-1}(x_{1})=x_{0}. Hence, clearly, ff^{-1} = f^{-1}f=i_{X}. QED.

B(iii) : Prove that such a f^{-1} is unique.

Solution to B(iii): Let there be another function g such that gf=fg=i_{X}. Also, we have ff^{-1}=f^{-1}f=i_{X}. Use the hint ! 🙂 QED.

Question C:

Let X and Y be non-empty sets and f a mapping of X into Y. Prove the following: (i) f is one-to-one if and only if there exists a mapping g of Y into X such that gf=i_{X} (ii) f is onto if and only if there exists a mapping h of Y into X such that fh=i_{X}.

Solution C(i) : Given f: X \rightarrow Y such that if x_{0} \neq x_{1}, then f(x_{0}) \neq f(x_{1}). Now, we want a mapping g: Y \rightarrow X such that gf=i_{X}. Let us construct a g such that g(y_{0})=x_{0} and g(y_{1}) = x_{1}. Then, (gf)(x_{0}) = g(f(x_{0}))=g(y_{0})=x_{0}. Similarly, gf(x_{1})=x_{1}. Here, we have assumed that f(x_{0})=y_{0} and f(x_{1})=y_{1}. So, knowing f to be one-to-one, we can explicitly construct a mapping g such that g: Y \rightarrow X and gf=i_{X}. QED. On the other hand, let it be given that X and Y are two non-empty sets, that f: X \rightarrow Y and g: Y \rightarrow X such that gf=i_{X}. That is, if some x^{'} \in X, then we have (gf)(x^{'}) = i_{X}(x^{'})=x^{'}. That is, g(f(x^{'})) = x^{'}. This forces, if f(x^{'}) = y^{'}, then g(y^{'})=x^{'}. Now, if there be an element x^{''} \neq x^{'}, it will force f(x^{''})=y^{''} \neq x^{'}. Hence, different inputs give rise to different outputs and so f is one-to-one. QED.

Solution C(ii) : Given f: X \rightarrow Y and f is onto, that is, f(X) = Y. We want to show a function h: Y \rightarrow X such that fh=i_{X}. Since f(X)=Y, with X as domain, Y as codomain equal to range, f is one-to-one, onto. So h=f^{-1}. QED.

Question D:

Let X be a non-empty set and f a mapping of X into itself. Show f is one-to-one onto if and only there exists a mapping g of X into itself such that gf=fg=i_{X}. If there exists a mapping g with the property, then there is one and only one such mapping. Why?

Solution D: From previous question, C we are done.

Question E:

Let X be a non-empty set, and let f and g be one-to-one mappings of X onto itself. Show that fg is also a one-to-one mapping of X onto itself and that (fg)^{-1}=g^{-1}f^{-1}.

HW. Hint: consider the action of the functions on each element.

Question F:

Let X and Y be non-empty sets and f a mapping of X into Y. If A and B are, respectively, subsets of X and Y, prove the following:

(a) ff^{-1}(B) \subseteq B, and ff^{-1}(B)=B is true for all B if and only if f is onto.

(b) A \subseteq f^{-1}f(A), and A = f^{-1}f(A) is true for all A if and only if f is one-to-one.

(c) f(A_{1} \bigcap A_{2}) = f(A_{1}) \bigcap f(A_{2}) is true for all A_{1} and A_{2} if and only if f is one-to-one.

(d) f(A)^{'} \subseteq f(A^{'}) is true for all A if and only if f is onto.

(e) If f is onto — so that, f(A)^{'} \subseteq f(A^{'}) is true for all A — then, f(A)^{'}=f(A^{'}) is true for all A if and only if f is also one-to-one.

Solution Fa: Put B=Y, so that f is onto. To prove the other subset relationship, simply reverse the arguments.

Solution Fb:

We need to apply the definition that different inputs give rise to different outputs.

;

😦 I hope to blog later)

:

Solution Fc:

It certainly implies that A_{1} \bigcap A_{2} \neq \phi.

:

(I hope to blog later).

Solution Fd:

Given that f: X \rightarrow Y and A \subseteq X and B \subseteq Y. Then, f(A)^{'} is Y-f(A), that is, Y-B, that is B^{'}, that is, f(B^{'}). Put A=X, then f is onto. Now, f(X)^{'} \subseteq f(X^{'}), that is, Y-f(X) \subseteq f(\phi). This implies Y=f(X). To prove the other subset relationship, simply reverse the arguments. QED.

Regards,

Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.