Bijection Proof (hard)

1. Aug 17, 2009

roam

1. The problem statement, all variables and given/known data

Let A and B be sets and let $$f: A \rightarrow B$$ be a function. Define a function

$$h: \mathcal{P} (B) \rightarrow \mathcal{P} (A)$$ by declaring that for $$Y \in\mathcal{P} (B)$$, $$h(Y)= \{ x \in A: f(x) \notin Y \}$$. Show that if $$f$$ is a bijection then h is a bijection.

3. The attempt at a solution
I'm not quite sure where to start. I could start by first showing that f is one to one & onto and then show that f = h by showing that:
dom(f) = dom(h)
cod(f) = cod(h)
And, $$\forall x \in dom(f), f(x)=h(x)$$

Of course, I can't do this because the question doesn't define function f (it only gived domain & codomain)! Does anyone know how to prove this question?

P.S. the notation $$\mathcal{P} (A)$$ and $$\mathcal{P} (B)$$ are supposed to represent the power set of A & B.

Last edited: Aug 17, 2009
2. Aug 17, 2009

Hurkyl

Staff Emeritus
Well, let's start with this. You know several of those subexpressions, don't you? e.g. you know what dom(h) is. What happens when you substitute those values into those equations?

3. Aug 18, 2009

mathie.girl

No, this won't work. For one thing, you don't have to show that f is one to one and onto. That would be showing that f is a bijection and your question starts with the assumption that f is a bijection. You don't have to prove it.

Also, $$f \neq h$$! You mention showing that their domains are the same, but that's not true. That's actually written in your question statement also. The domain of f is $$A$$, but the domain of $$h$$ is $$P(B)$$. So f acts on elements of the set $$A$$, whereas h acts on subsets of the set $$B$$. Totally different.

You need to assume that f is a bijection (i.e. one to one and onto) and then show that h must be as well. Just go through the proofs for each of these requirements. For one to one, assume $$h(Y_1) = h(Y_2)$$, then looking at the definitions of $$h(Y)$$ in the question (using that f is bijective), you should be able to conclude that $$Y_1 = Y_2$$. Then for onto, select an arbitrary subset of $$A$$, say $$A_0$$, then try to determine a subset of $$B$$ that must map to it.

4. Aug 19, 2009

roam

Hi mathie girl, your method sounds good. Suppose f is a bijection,

for $$Y_1 , Y_2 \in \mathcal{P}(B) = dom(h)$$

Here's the problem: I really can't figure out how to show $$h(Y_1) = h(Y_2) \Rightarrow Y_1 = Y_2$$ using what is given in the question, I don't know what steps to take. What would you propose? I'm very confused atm

5. Aug 19, 2009

mathie.girl

Okay, you're assuming that $$h(Y_1) = h(Y_2)$$, right? So $$h(Y_1)= \{ x \in A: f(x) \notin Y_1 \}= \{ x \in A: f(x) \notin Y_2 \} = h(Y_2)$$. Then I'd probably do it by contradiction, assuming that $$Y_1 \neq Y_2$$, so WLOG (without loss of generality) there's some element $$b \in Y_1 \setminus Y_2$$. Then using the bijectivity of $$f$$ and the definition of $$h$$ to figure out something about $$h(Y_1), h(Y_2)$$. Hopefully that's enough to get you started!

Also, the onto part should be much easier. So at least this is the hard part.