Proof: function of int. of family of sets and int. of function of family of sets

[SithsNGiggles]

Homework Statement

The question is "Prove

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

Also, prove the statement's equality when $f$ is an injective function.

Homework Equations

The Attempt at a Solution

Let $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$.

Then $\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha$,

i.e. $\exists x \in A_\alpha \forall \alpha \in \Omega$.

It follows that $\exists f(x) \in f(A_\alpha) \forall \alpha \in \Omega$,

i.e. $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

Thus $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha) \Rightarrow f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$, and hence,
$f(\bigcap_{\alpha \in \Omega} A_\alpha) \subseteq \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

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?

 

[micromass]

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.

 

[SithsNGiggles]

What did you try for the other inclusion (in the case that f is injective).

Specifically:
Let $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

Then $f(x) \in f(A_\alpha) \forall \alpha \in \Omega$.

Thus $\exists x \in A_\alpha, \forall \alpha \in \Omega$, for which $f(x) \in f(A_\alpha)$.

i.e. $x \in \bigcap_{\alpha \in \Omega} A_\alpha$.

So, $\exists f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$, and hence,

$f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha) \Rightarrow f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$, so RHS $\subseteq$ 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.

 

[micromass]

Specifically:
Let $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

Then $f(x) \in f(A_\alpha) \forall \alpha \in \Omega$.

Thus $\exists x \in A_\alpha, \forall \alpha \in \Omega$, for which $f(x) \in f(A_\alpha)$.

i.e. $x \in \bigcap_{\alpha \in \Omega} A_\alpha$.

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)=x². 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!

 

[SithsNGiggles]

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!

 

[SithsNGiggles]

Let $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$.

Then $\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha$

Let $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

Then $f(x) \in f(A_\alpha) \forall \alpha \in \Omega$.

Thus $\exists x \in A_\alpha, \forall \alpha \in \Omega$, for which $f(x) \in f(A_\alpha)$.

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

always guarantee that

$\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha$?

And does letting
$f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$

guarantee that

$\exists x \in A_\alpha, \forall \alpha \in \Omega$, for which $f(x) \in f(A_\alpha)$?

I'm having some doubts.

 

[micromass]

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

always guarantee that

$\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha$?

Yes.

And does letting
$f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$

guarantee that

$\exists x \in A_\alpha, \forall \alpha \in \Omega$, for which $f(x) \in f(A_\alpha)$?

This guarantees that for each alpha $f(x)\in f(A_\alpha)$. This implies that for each alpha, there is an $y_\alpha$ such that $f(y_\alpha)=f(x)$.

 

[SithsNGiggles]

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.

 

[micromass]

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)?

Well, there certainly is such a function. If $A\subseteq X$, then we can indeed define f(A).

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.

Maybe it would be a good idea to post the proof here so I can examine it?

 

[SithsNGiggles]

Let $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$.

Then $\exists x \in \bigcap_{\alpha \in \Omega} A_\alpha$,

i.e. $\exists x \in A_\alpha \forall \alpha \in \Omega$.

This implies that $f(x) \in f(A_\alpha) \forall \alpha \in \Omega$,

i.e. $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

Thus $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha) \Rightarrow f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$, and hence,
$f(\bigcap_{\alpha \in \Omega} A_\alpha) \subseteq \bigcap_{\alpha \in \Omega} f(A_\alpha)$.

- - - - - - - - - - -
Now let $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$, i.e. $f(x) \in f(A_\alpha)$.

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

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

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

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

Clearly, $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)$.

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

As shown above, letting $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$ does not imply that $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$, so $\bigcap_{\alpha \in \Omega} f(A_\alpha) \not\subseteq f(\bigcap_{\alpha \in \Omega} A_\alpha)$.

 

[micromass]

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.

 

[SithsNGiggles]

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) = x², which was already accepted prior to the rest of this proof.)

 

[micromass]

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) = x², which was already accepted prior to the rest of this proof.)

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.

 

[SithsNGiggles]

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:

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

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

Clearly, $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)$.

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

As shown above, letting $f(x) \in \bigcap_{\alpha \in \Omega} f(A_\alpha)$ does not imply that $f(x) \in f(\bigcap_{\alpha \in \Omega} A_\alpha)$, so $\bigcap_{\alpha \in \Omega} f(A_\alpha) \not\subseteq f(\bigcap_{\alpha \in \Omega} A_\alpha)$.

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