How Does Function Composition Affect Preimage Calculation?

[r4nd0m]

I'm really stuck with my homework - it seems to be easy, but...
So the first one:
Find the most natural bijection between these two sets:
(X \times Y)^Z , X^Z \times Y^Z


The second thing I'm stuck with:
Proof for arbitrary f: X \rightarrow Y , g: Y \rightarrow Z and sets:
A \subseteq X , B \subseteq Z :
(g \circ f)^{-1} (B) = f^{-1}(g^{-1}(B))

And the last one:
Let f: X \rightarrow Y be an arbitrary function. Proof that for every A,B \subseteq X ; C,D \subseteq Y:
a) C \subseteq D \Rightarrow f^{-1}(C) \subseteq f^{-1}(D)
b) f(f^{-1}(C)) \subseteq C

 

[HallsofIvy]

Each of those looks to me to be reasonably straight forward. What have you done so far? What are the relevant definitions?

 

[r4nd0m]

Well in the first one I don't really know what kind of answer they are expecting.

I found out that the second one is really easy.

In the third one I don't understand why there is inclusion instead of equality (because an inverse function exist only when the original function is bijective, therefore in b) there should be equality I think)

 

[r4nd0m]

can anyone help me at least with the first one?
Please

 

[Hurkyl]

For (1):

If someone said "Please write down a bijection (X \times Y)^Z \rightarrow X^Z \times Y^Z", what bijection would you write down? That is almost certainly the one they're asking for.


For (2):

For any binary relation f (in particular, a function is a binary relation), the relation f^{-1} is defined. (But is not usually a function)

Recall that for any binary relation R on (S, T), we can define, for A \subseteq S:

<br /> R(A) := \{ t \in T \, | \, \exists s \in A: s \, R \, t \}<br />

(The notation for this isn't really standard -- for example, I would really prefer to write it as A \cdot R, maybe without the dot)

For a function f : S \rightarrow T, recall that f is merely a binary relation on (S, T). Thus, we obtain the direct image of a subset A of S:

<br /> f(A) = \{ t \in T \, | \, \exists s \in A : f(s) = t \}<br />

or, more simply,

<br /> f(A) = \{ f(a) \, | \, a \in A \}<br />

The inverse relation just does things in the opposite order. t \, R^{-1} \, s if and only if s \, R \, t. For f, Plugging into the definition, we obtain the inverse image of a subset B of T:

<br /> f^{-1}(B) = \{ s \in S \, | \, \exists t \in B : t \, f^{-1} \, s \}<br /> = \cdots = \{ s \in S \, | \, f(s) \in B \}<br />