Bijection Proof for Sets and Functions - A Comprehensive Guide

[roam]

Homework Statement

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.

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.

 

[Hurkyl]

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

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?

 

[mathie.girl]

Show that if $$f$$ is a bijection then h is a bijection.

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

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.

 

[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

 

[mathie.girl]

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

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.