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: Proof: function of int. of family of sets and int. of function of family of sets

  1. Mar 14, 2012 #1
    1. The problem statement, all variables and given/known data
    The question is "Prove

    [itex]f(\bigcap_{\alpha \in \Omega} A_\alpha) \subseteq \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex]
    where [itex]f:X \rightarrow Y[/itex] and [itex]\{A_\alpha : \alpha \in \Omega\}[/itex] is a collection of subsets of [itex]X[/itex].

    Also, prove the statement's equality when [itex]f[/itex] is an injective function.

    2. Relevant equations

    3. The attempt at a solution

    Let [itex]f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex].

    Then [itex]\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex],

    i.e. [itex]\exists x \in A_\alpha \forall \alpha \in \Omega[/itex].

    It follows that [itex]\exists f(x) \in f(A_\alpha) \forall \alpha \in \Omega[/itex],

    i.e. [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex].

    Thus [itex]f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha) \Rightarrow f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex], and hence,
    [itex]f(\bigcap_{\alpha \in \Omega} A_\alpha) \subseteq \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex].

    I tried following a similar thought process in proving the reverse, but I end up showing that the RHS is a subset of the LHS. Although it works out for the injective f, where does it go wrong when f is not injective?
  2. jcsd
  3. Mar 14, 2012 #2
    That is correct.

    What did you try for the other inclusion (in the case that f is injective). Perhaps we'll be able to tell you where it goes wrong.
  4. Mar 14, 2012 #3
    Let [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex].

    Then [itex]f(x) \in f(A_\alpha) \forall \alpha \in \Omega[/itex].

    Thus [itex]\exists x \in A_\alpha, \forall \alpha \in \Omega[/itex], for which [itex]f(x) \in f(A_\alpha)[/itex].

    i.e. [itex]x \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex].

    So, [itex]\exists f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex], and hence,

    [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha) \Rightarrow f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex], so RHS [itex]\subseteq[/itex] LHS.

    There's probably some implied assumption that I should be pointing out, but I'm not sure what it is. I applied this process to both cases of f being injective and f not being injective. I don't know what's missing, but I think I'm having trouble understanding the definition of injective in this context.
  5. Mar 14, 2012 #4
    Here's your error. The x here is dependent of alpha. That, is you might not get the same x for every value alpha.

    For example, if f(x)=x2. Then 1 is in f([-2,0]) and in f([0,2]). So we can take an x in [-2,0] such that f(x)=1, and we can take x in [0,2] such that f(x)=1. But this x is obviously not the same!!
  6. Mar 14, 2012 #5
    Oh, I see. I've been assuming the relationship between (the existences of) x and f(x) was a two-way street.

    Thanks for clarifying!
  7. Mar 20, 2012 #6

    Actually, one more question: Does letting
    [itex]f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex]

    always guarantee that

    [itex]\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex]?

    And does letting
    [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex]

    guarantee that

    [itex]\exists x \in A_\alpha, \forall \alpha \in \Omega[/itex], for which [itex]f(x) \in f(A_\alpha)[/itex]?

    I'm having some doubts.
  8. Mar 21, 2012 #7

    This guarantees that for each alpha [itex]f(x)\in f(A_\alpha)[/itex]. This implies that for each alpha, there is an [itex]y_\alpha[/itex] such that [itex]f(y_\alpha)=f(x)[/itex].
  9. Mar 22, 2012 #8
    Sorry for the hassle micromass, but does your post have anything to do with f: X -> Y inducing a new function f: P(X) -> P(Y)?

    I presented my proof to my professor, but I'm told that the proof is still missing something, particularly in the part where I refer to the guarantee of the existence of x.

    Thanks again.
  10. Mar 22, 2012 #9
    Well, there certainly is such a function. If [itex]A\subseteq X[/itex], then we can indeed define f(A).

    Maybe it would be a good idea to post the proof here so I can examine it?
  11. Mar 23, 2012 #10
    Let [itex]f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex].

    Then [itex]\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex],

    i.e. [itex]\exists x \in A_\alpha \forall \alpha \in \Omega[/itex].

    This implies that [itex]f(x) \in f(A_\alpha) \forall \alpha \in \Omega[/itex],

    i.e. [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex].

    Thus [itex]f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha) \Rightarrow f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex], and hence,
    [itex]f(\bigcap_{\alpha \in \Omega} A_\alpha) \subseteq \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex].

    - - - - - - - - - - -
    Now let [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex], i.e. [itex]f(x) \in f(A_\alpha)[/itex].

    This implies the existence of at least one [itex]x \in A_\alpha \forall \alpha \in \Omega[/itex], i.e. [itex]x \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex].

    [next I use a non-injective function to demonstrate the "at least one" note]

    Let [itex]y \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex] and [itex]z \not\in \bigcap_{\alpha \in \Omega} A_\alpha[/itex] (but [itex]z \in A_\alpha[/itex] for some [itex]\alpha \in \Omega[/itex], where [itex]y \not= z[/itex].

    Additionally, let [itex]f(x) = f(z)[/itex], such that f is non-injective, and let [itex]f(y), f(z) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex].

    Clearly, [itex]f(y) \in \bigcap_{\alpha \in \Omega} f(A_\alpha) \Rightarrow y \in \bigcap_{\alpha \in \Omega} A_\alpha \Rightarrow f(y) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex].

    However, since [itex]z \not\in \bigcap_{\alpha \in \Omega} A_\alpha[/itex], [itex]f(z) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex] does not imply that [itex]z \in \bigcap_{\alpha \in \Omega} A_\alpha[/itex], so [itex]f(z) \not\in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex].​

    As shown above, letting [itex]f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)[/itex] does not imply that [itex]f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex], so [itex]\bigcap_{\alpha \in \Omega} f(A_\alpha) \not\subseteq f(\bigcap_{\alpha \in \Omega} A_\alpha)[/itex].
  12. Mar 23, 2012 #11
    You did something weird. Here are some comments:

    1) You somehow tried to prove that if a function is not injective, then the equality does not hold. This was not at all what you need to prove. You need to prove that if the function IS injective, then the equality DOES hold. This is completely something else. You actually need to assume that your function is injective and then show the inequality. Assuming not injective is useless.

    It's like this: "if x=2, then x²=4". This expression is true, but how to prove it?? You somehow proved "if x is not 2, then x² is not 4". Notice that this expression is not true (take x=-2). So you can't just negate everything in a statement without changing the statements meaning.

    2) If you want to show that the inequality does not necessarily hold when the function is not injective, then a counterexample suffices. You don't need to give an entire formal proof for this. For example, if I wanted to show that "if x is even, then x² is odd" is NOT true, then a counterexample suffices. Indeed, I could take x=2, then x²=4 is not odd. So with just one counterexample, I proved that the statement is false.
  13. Mar 23, 2012 #12
    Hmm, I knew I was doing something wrong, but I wasn't sure if what I was doing was relevant. Thanks for clearing that up. I suppose that's what my prof was telling me.

    So after leaving out the "proof" after the dividing line, would this proof be acceptable? (I also include a counter-example where f(x) = x2, which was already accepted prior to the rest of this proof.)
  14. Mar 23, 2012 #13
    The thing before the line is certainly acceptable.
    But it isn't enough: the question asks two things!! The first thing is showing an inclusion, which you did. But the other thing is showing that equality holds if f is injective. You did not yet show this.
  15. Mar 23, 2012 #14
    Showing that equality holds for an injective function is a different problem altogether, but I was still hoping to tackle it along with this one. Is there a way that I could alter this part:

    to make it work for an injective function? Meaning, is there anything I can salvage here and start off by assuming f is injective?

    Thanks again
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook