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$:

$$R(A) := \{ t \in T \, | \, \exists s \in A: s \, R \, t \}$$

(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:

$$f(A) = \{ t \in T \, | \, \exists s \in A : f(s) = t \}$$

or, more simply,

$$f(A) = \{ f(a) \, | \, a \in A \}$$

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:

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