Results 1 to 11 of 11

Math Help - Proof

  1. #1
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85

    Proof

    Working on a proof and I need some help

    Let f : A ----> B be an injective (1:1) function and consider C a subset of A. Show that f^(-1)(f(C)) = C or [inverse image of f(C) = C]

    e = an element of

    What I have so far is...

    C = { a e A such that a e C}
    f(A) = { b e B such that there exists a e A, for f(a) = b}
    f(C) = { b e B such that there exists c e A, for f(c) = b}
    f(C) is a subset of B

    f^(-1)(f(C)) = { a e A such that f(a) e f(C)}

    Am I doing this right so far? And if I am, how do I go from the "f(a) e f(C)" part to "a e C" which would then be equal to C and my proof will be done?

    I also have a similar problem to this except f : A ----> B is surjective (onto) rather than injective. How does this change the proof? Very lost...

    - Nicole
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi!

    f:A\rightarrow B is injective, C \subseteq A and what needs to be shown is f^{-1}[f[C]]=C ?

    We want to prove an equality of sets so we need to prove two inclusions.
    Let's start with the easy one, C \subseteq f^{-1}[f[C]], where injectivity doesn't play any role.

    Let x \in C. By definition, f[C] = \{b \in B: (\exists c \in C) f(c)=b\} , so we have f(x) \in f[C].
    Definition of inverse image gives f^{-1}[f[C]] = \{z \in A : f(z) \in f[C]\}. So x \in f^{-1}[f[C]].

    Now let's prove the oposite inclusion.
    Let x \in f^{-1}[f[C]]. By definition of inverse image we get f(x) \in f[C], so, by definition of f[C], there exists some c \in C such that f(c)=f(x).
    Now we use that f is injective: f(c)=f(x) implies c=x. This is an answer to your question at the end of your attempt, it is just definition of injectivity. So we have x=c and we know that c\in C, so x \in C and we are done.


    As for the surjective function, what is exactly the question?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85
    Oh wow, thanks!

    the surjective problem is the exact same problem, except instead of being injective, f is surjective... oh and instead of C, it's D hehe

    thanks again! you're the best!

    - Nicole
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2009
    Posts
    125
    If it is like you're saying, surjectivity won't help us .

    Consider simple counterexample: A=\{0,1\}, B=\{1\}, C=\{0\}\subseteq A, and define f:A\rightarrow B, f(0)=f(1)=1.

    You see f is surjective, but f^{-1}[f[C]] = \{0,1\} = A \neq C.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85
    oh wait, I lied... I do that sometimes hehe

    here's the problem:
    Let f : A --> B be a surjective function and assume that D is a subset of B. Prove that f(f^-1(D)) = D

    my bad I fail....

    - Nicole
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    125
    I thought!
    Try it first and show how far you can get. Again, one inclusion is easy and the second one uses the surjectivity.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85
    So.. I did it the same way you solved the last one...

    D = { b e B : b e D}

    f^(-1)(D) = {a e A : f(a) = D}
    => f^(-1)(x) e f^(-1)(D)

    f(f^(-1)(D)) = { b e B : f(b) e f^(-1)(D)}
    => x e f(f^(-1)(D))

    => D subset of f(f^(-1)(D))

    is that right at all?

    for the surjective part, I know that A --> B being surjective means for all b e B, there exists a e A s.t. f(a) = b

    so D being a subset of B, for all d e D there exists a e A s.t. f(a) = d?

    and.... my brain is fried.... I feel like I know it, but I just can't write it...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2009
    Posts
    125
    Quote Originally Posted by thaopanda View Post
    So.. I did it the same way you solved the last one...

    D = { b e B : b e D}

    f^(-1)(D) = {a e A : f(a) = D}
    => f^(-1)(x) e f^(-1)(D)

    f(f^(-1)(D)) = { b e B : f(b) e f^(-1)(D)}
    => x e f(f^(-1)(D))

    => D subset of f(f^(-1)(D))
    You got it wrong way, this one is the part where surjectivity is needed!
    Also, reading your notation is like learning a new language, please start using LaTeX - if you left-click on math expressions on one of my posts, you can see how easy the code is, and for other symbols check http://www.mathhelpforum.com/math-help/latex-help/

    So let's look at that inclusion D \subseteq f[f^{-1}[D]].
    Let x \in D. Since f is surjective, there exists some y\in A such that f(y)=x, and this means that y\in f^{-1}[D]. And obviously x=f(y) \in f[f^{-1}[D]]. So D \subseteq f[f^{-1}[D]] .

    Now you try the other, easier inclusion (using some latex ).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85
    I'm probably gonna get this wrong again...

    so i started with
    f(y)  \in f[f^{-1}[D]]
    where f(y) = b and  b \in B
    <br />
b \in f[f^{-1}[D]] <br />
    <br />
f^{-1}(b) \in f^{-1}[D]<br />
    <br />
b \in D <br />

    I think I'm a hopeless case... I'll figure this out eventually...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Aug 2009
    Posts
    125
    Nice work with LaTeX!
    Moreover, if I'm reading your proof in certain order (not down from top as usual) i think it is correct

    Let's look at it. We want to prove that f[f^{-1}[D]] \subseteq D so we start by picking arbitrary element say x from f[f^{-1}[D]] and we try to prove that this element must belong to D too. This is the third line of your proof, with which you should begin. So first line:

    x \in f[f^{-1}[D]]

    Definition of "image of f", f[f^{-1}[D]] = \{y: y \in B \; \& \; (\exists z \in f^{-1}[D]) \, f(z)=y\}, tells us that there must be some z \in f^{-1}[D] such that f(z)=x (because x \in f[f^{-1}[D]]).

    But because z \in f^{-1}[D], definition of inverse image, f^{-1}[D]=\{t \in A: f(t)\in D\}, tells us that f(z)\in D.

    But f(z)=x, which means that x \in D.

    We conclude that f[f^{-1}[D]] \subseteq D.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85
    woooo!
    thanks soooo much! now if only you could take my test for me tomorrow
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum