1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bijection Proof (hard)

  1. Aug 17, 2009 #1
    1. The problem statement, all variables and given/known data

    Let A and B be sets and let [tex]f: A \rightarrow B[/tex] be a function. Define a function

    [tex]h: \mathcal{P} (B) \rightarrow \mathcal{P} (A)[/tex] by declaring that for [tex]Y \in\mathcal{P} (B)[/tex], [tex]h(Y)= \{ x \in A: f(x) \notin Y \}[/tex]. Show that if [tex]f[/tex] 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, [tex]\forall x \in dom(f), f(x)=h(x)[/tex]

    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 [tex]\mathcal{P} (A)[/tex] and [tex]\mathcal{P} (B)[/tex] are supposed to represent the power set of A & B.
    Last edited: Aug 17, 2009
  2. jcsd
  3. Aug 17, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
  4. Aug 18, 2009 #3
    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, [tex]f \neq h[/tex]! 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 [tex]A[/tex], but the domain of [tex]h[/tex] is [tex]P(B)[/tex]. So f acts on elements of the set [tex]A[/tex], whereas h acts on subsets of the set [tex]B[/tex]. 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 [tex]h(Y_1) = h(Y_2)[/tex], then looking at the definitions of [tex]h(Y)[/tex] in the question (using that f is bijective), you should be able to conclude that [tex]Y_1 = Y_2[/tex]. Then for onto, select an arbitrary subset of [tex]A[/tex], say [tex]A_0[/tex], then try to determine a subset of [tex]B[/tex] that must map to it.
  5. Aug 19, 2009 #4
    Hi mathie girl, your method sounds good. Suppose f is a bijection,

    for [tex]Y_1 , Y_2 \in \mathcal{P}(B) = dom(h)[/tex]

    Here's the problem: I really can't figure out how to show [tex]h(Y_1) = h(Y_2) \Rightarrow Y_1 = Y_2[/tex] using what is given in the question, I don't know what steps to take. What would you propose? I'm very confused atm :confused:
  6. Aug 19, 2009 #5
    Okay, you're assuming that [tex]h(Y_1) = h(Y_2)[/tex], right? So [tex]h(Y_1)= \{ x \in A: f(x) \notin Y_1 \}= \{ x \in A: f(x) \notin Y_2 \} = h(Y_2)[/tex]. Then I'd probably do it by contradiction, assuming that [tex]Y_1 \neq Y_2[/tex], so WLOG (without loss of generality) there's some element [tex]b \in Y_1 \setminus Y_2[/tex]. Then using the bijectivity of [tex]f[/tex] and the definition of [tex]h[/tex] to figure out something about [tex]h(Y_1), h(Y_2)[/tex]. Hopefully that's enough to get you started!

    Also, the onto part should be much easier. So at least this is the hard part. :smile:
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Bijection Proof (hard)
  1. Bijection Proof (Replies: 15)