Exercises on images像ぞう and preimages逆像ぎゃくぞう

1Corresponding lectures講義こうぎ

2Problem 1: find an image像ぞう

Let $$A=\{1,2,3,4\}$$A=\{1,2,3,4\} and $$B=\{0,1\}$$B=\{0,1\}. Define the map写像しゃぞう $$f:A\to B$$f:A\to B by letting $$f\left(x\right)$$f(x) be the remainder when $$x$$x is divided by $$2$$2. Find the image像ぞう $$f\left(S\right)$$f(S) of $$S=\{1,2,4\}$$S=\{1,2,4\}.

2.1Answer

Since $$f\left(1\right)=1$$f(1)=1, $$f\left(2\right)=0$$f(2)=0, and $$f\left(4\right)=0$$f(4)=0,

2.2Explanation

The image像ぞう is the set集合しゅうごう actually obtained by applying the map to each element元げん of the subset部分集合ぶぶんしゅうごう. If several inputs give the same value, that value appears only once in the set.

3Problem 2: find a preimage逆像ぎゃくぞう

For the map写像しゃぞう $$f$$f in Problem 1, find the preimage逆像ぎゃくぞう $$f^{-1}\left(T\right)$$f^{-1}(T) of $$T=\left\{0\right\}$$T=\{0\}.

3.1Answer

The inputs with $$f\left(x\right)=0$$f(x)=0 are $$x=2,4$$x=2,4. Therefore

3.2Explanation

A preimage逆像ぎゃくぞう is the set of all inputs入力にゅうりょく whose outputs出力しゅつりょく lie in the specified codomain終域しゅういき-side set. It is different from an inverse map逆写像ぎゃくしゃぞう, so a preimage can be found even when the map is not a bijection全単射ぜんたんしゃ.

4Problem 3: prove that preimages逆像ぎゃくぞう preserve complements補集合ほしゅうごう

Let $$f:A\to B$$f:A\to B and $$T\subseteq B$$T\subseteq B. Prove

4.1Answer

For arbitrary $$x\in A$$x\in A,

Since the membership conditions are equivalent for every $$x\in A$$x\in A, the two sets集合しゅうごう are equal.

4.2Explanation

For a complement補集合ほしゅうごう, the ambient set matters. The set $$B\setminus T$$B\setminus T is the output-side complement, and its preimage逆像ぎゃくぞう is the input-side complement $$A\setminus f^{-1}\left(T\right)$$A\setminus f^{-1}(T).

5Proof exercise: round trips through images像ぞう and preimages逆像ぎゃくぞう

5.1Problem

Let $$f:A\to B$$f:A\to B. Prove the following statements.

1. For every $$S\subseteq A$$S\subseteq A, $$S\subseteq f^{-1}\left(f\right(S\left)\right)$$S\subseteq f^{-1}(f(S)). Equality holds for every $$S\subseteq A$$S\subseteq A if and only if $$f$$f is an injection単射たんしゃ.
2. For every $$T\subseteq B$$T\subseteq B, $$f\left(f^{-1}\right(T\left)\right)=T\cap f\left(A\right)\subseteq T$$f(f^{-1}(T))=T\cap f(A)\subseteq T. The equality $$f\left(f^{-1}\right(T\left)\right)=T$$f(f^{-1}(T))=T holds for every $$T\subseteq B$$T\subseteq B if and only if $$f$$f is a surjection全射ぜんしゃ.

5.2Answer

1. If $$x\in S$$x\in S, then $$f\left(x\right)\in f\left(S\right)$$f(x)\in f(S), so $$x\in f^{-1}\left(f\right(S\left)\right)$$x\in f^{-1}(f(S)). Hence $$S\subseteq f^{-1}\left(f\right(S\left)\right)$$S\subseteq f^{-1}(f(S)).

Suppose $$f$$f is injective and $$x\in f^{-1}\left(f\right(S\left)\right)$$x\in f^{-1}(f(S)). There exists $$s\in S$$s\in S with $$f\left(x\right)=f\left(s\right)$$f(x)=f(s). Injectivity gives $$x=s\in S$$x=s\in S, so equality holds for every $$S$$S.

Conversely, suppose equality holds for every $$S$$S. If $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2), set $$S=\left\{x_1\right\}$$S=\{x_1\}. Then $$x_2\in f^{-1}\left(f\right(S\left)\right)=S$$x_2\in f^{-1}(f(S))=S, so $$x_2=x_1$$x_2=x_1. Thus $$f$$f is injective.

1. If $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)), there exists $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T) with $$y=f\left(x\right)$$y=f(x). By the definition of preimage, $$f\left(x\right)\in T$$f(x)\in T, and $$y=f\left(x\right)\in f\left(A\right)$$y=f(x)\in f(A), so $$y\in T\cap f\left(A\right)$$y\in T\cap f(A).

Conversely, if $$y\in T\cap f\left(A\right)$$y\in T\cap f(A), there exists $$x\in A$$x\in A with $$f\left(x\right)=y$$f(x)=y. Since $$y\in T$$y\in T, one has $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T) and hence $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)). Therefore

Suppose $$f$$f is surjective and $$y\in T$$y\in T. There exists $$x\in A$$x\in A with $$f\left(x\right)=y$$f(x)=y. Then $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T), so $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)). Thus equality holds for every $$T$$T.

Conversely, suppose equality holds for every $$T$$T. Taking $$T=B$$T=B gives

so $$f$$f is surjective.

5.3Explanation

Starting on the input side, taking an image像ぞう and then pulling it back by a preimage逆像ぎゃくぞう may add inputs that share an output. Injectivity単射性たんしゃせい is exactly the condition preventing this addition.

Starting on the output side, taking a preimage and then pushing it forward by an image may lose elements that the map never reaches. Surjectivity全射性ぜんしゃせい is exactly the condition preventing this loss.

The condition equivalent to injectivity or surjectivity is not equality for one particular subset, but equality for every subset. Keep this difference in quantification explicit.

6Next lecture講義こうぎ