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!

Homework Help: Functions, one to one, subsets, intersections

  1. Aug 6, 2009 #1
    The problem statement, all variables and given/known data
    General Case:

    Let [tex]f:A \rightarrow B[/tex] be a function. Show that [tex]f( \bigcap_{\alpha\in\Lambda} T_{\alpha}) = \bigcap_{\alpha\in\Lambda} f(T_{\alpha})[/tex] for all choices of [tex]\{T_{\alpha}\}_{\alpha\in\Lambda[/tex] if and only if [tex]f[/tex] is one-to-one.

    Simpler Case:

    Let [tex]f:A \rightarrow B[/tex] be a function, and [tex]X, Y[/tex] be subsets of [tex]A[/tex].
    Show that [tex]f(X \cap Y) = f(X) \cap f(Y)[/tex] if and only if [tex]f[/tex] is one-to-one.

    The attempt at a solution

    I am trying to understand the simpler case first before attempting a solution for the general case.

    Assume [tex]f[/tex] is one-to-one. Let [tex]b \in f(X) \cap f(Y)[/tex].
    Then, [tex]b \in f(X), b \in f(Y)[/tex]. Then, [tex]\exists a (a \in X, a \in Y, f(a) = b)[/tex].
    This implies that [tex]a \in X \cap Y[/tex]. Therefore, [tex]f(X \cap Y) = f(X) \cap f(Y)[/tex].

    (=>)(Our hint here is to use contraposition -- assuming the following to show f is not one-to-one.).

    Assume [tex]f(X \cap Y) \neq f(X) \cap f(Y).[/tex] Let [tex]u \in f(X) \cap f(Y)[/tex].
    Then, [tex]u \in f(X), u \in f(Y)[/tex]. This implies [tex]\exists a,b (a \in X, b \in Y, f(a) = f(b) = u)[/tex].

    If I show that [tex] a,b \notin (X \cap Y) [/tex], does that mean [tex] a \neq b [/tex]?
    If so, then, [tex] f(a) = f(b) [/tex], so [tex]f[/tex] cannot be one-to-one.

    Any thoughts?
  2. jcsd
  3. Aug 6, 2009 #2
    The reverse direction looks fine. Just remember that the existence of the a in that part of the proof depends on f being one-to-one, so it might help to state that. Also, remember that the conclusion from the reverse direction is [tex] f(X \cap Y) \supset f(X) \cap f(Y)[/tex].

    The forward direction seems needlessly complicated. This direction is true regardless of whether f is one-to-one. If b is in [tex]f(X \cap Y)[/tex], then b = f(a) for some a in A such that a is X and a is in Y.
  4. Aug 6, 2009 #3


    User Avatar
    Homework Helper

    No, you should not use "assume" here.

    You are trying to prove: [tex]f \mbox{ is one-to-one } \Rightarrow f(X \cap Y) = f(X) \cap f(Y)[/tex]

    i.e, f is already one-to-one. Don't need to assume anymore. You must use this to prove that [tex]f(X \cap Y) = f(X) \cap f(Y)[/tex]. So, no assumption here. :)

    In this step, you are proving that: [tex]f(X \cap Y) = f(X) \cap f(Y) \Rightarrow f \mbox{ is one-to-one }[/tex], i.e: now you have this piece of information: [tex]f(X \cap Y) = f(X) \cap f(Y)[/tex], and you need to prove that f is one-to-one.

    So, to use proof by contradiction, you assume that f is not one-to-one. And try to see what error it leads to.

    Hope, it's clear enough. :)
  5. Aug 6, 2009 #4
    I think it's ok for the OP to use "assume" since he is just restating the hypotheses for the reverse implication. However, I clearly misread the question, as the initial proof of the reverse implication does show set equality. Sorry.

    But yes, for the actual forward direction if you assume f is not one-to-one, then you should obtain an easy contradiction.
  6. Aug 6, 2009 #5
    Attempt #2 (<=)

    And yes, I'm restating the "given" information (the assumptions) for clarity.

    Assume [tex]f[/tex] is one-to-one. Let [tex]b \in f(X) \cap f(Y)[/tex].
    Then, [tex]b \in f(X), b \in f(Y)[/tex]. Then, there exists [tex]c \in X, d \in Y[/tex] such that [tex]f(c) = b = f(d)[/tex]. Since [tex]f[/tex] is one-to-one, [tex]c = d[/tex]. Then, [tex]c, d \in (X \cap Y)[/tex] so [tex]b \in f(X \cap Y)[/tex]. Therefore, [tex]f(X \cap Y) = f(X) \cap f(Y)[/tex].

    Working on it.
  7. Aug 6, 2009 #6
    I'm not sure how the initial proof shows set equality. I'm still only seeing one inclusion, [tex]\supseteq[/tex]. I would think the other inclusion would need to be stated, even if it's pretty obvious. Also, the modified proof just above my post is much better since it assumes a [tex]c[/tex] and [tex]d[/tex] as opposed to merely one element [tex]a[/tex].

    The forward direction can be done with contrapositive/contradiction (assuming that [tex]f[/tex] isn't one-to-one), but could also be done with a regular one-to-one proof. Assume that [tex]f(a) = f(b)[/tex] and see what falls out when you keep in mind your assumptions.
  8. Aug 6, 2009 #7


    User Avatar
    Science Advisor

    You are right: now only one inclusion has been proved, the other one should also be mentioned (it is trivial, but then at least say 'the other inclusion is trivial', showing you understand that both inclusion are necessary).
    Not much better, but the only right way. The first attempt was just wrong. :smile:
  9. Aug 8, 2009 #8


    User Avatar
    Homework Helper

    How about, assume that f is not one-to-one. By definition:

    [tex]\exists c \neq d : f(c) = f(d)[/tex]

    Ok, now, you have to choose X, and Y wisely, so that it leads to contradiction (i.e, [tex]f(X \cap Y) \neq f(X) \cap f(Y)[/tex]).

    Let's see if you can go from here. :)
  10. Aug 8, 2009 #9
    Following from your reply.

    Let [tex]X = \{c\}, Y = \{d\}[/tex]. Then, [tex]f(X \cap Y) = \emptyset \neq f(X) \cap f(Y)[/tex]

    ... was it that easy?
  11. Aug 9, 2009 #10
    Assume [tex]f(X \cap Y) = f(X) \cap f(Y)[/tex]. And, assume [tex]f[/tex] is not one-to-one.
    Then, [tex]\exists c \neq d[/tex] such that [tex]f(c) = f(d) = z[/tex]. Now, let [tex]X = \{c\}, Y = \{d\}[/tex]. Then, [tex]f(X \cap Y) = \emptyset \neq f(X) \cap f(Y) = \{z\}[/tex].
    So our assumption that [tex]f[/tex] was not one-to-one is false. Therefore, [tex]f[/tex] must be one-to-one.

    I think that works. Thanks for the help.
    I didn't think I was allowed to choose which sets [tex]X, Y[/tex] represented.
  12. Aug 9, 2009 #11


    User Avatar
    Homework Helper

    That's why everyone here told you it was easy.. :)

    Perfect, congratulations. :smile:

    Well, of course you can, X, and Y just need to be subsets of A; since you have [tex]c, \ d \in A[/tex], so, that means: [tex]\{ c \} , \{ d \} \subset A[/tex]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook