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.