Proving Subset Relation for Composed Functions

[toothpaste666]

Homework Statement

for functions f: X -> Y and g: Y ->Z
show that for all subsets C in Z , (g°f)^-1(C) ⊆ f^-1(g^-1(C)) (or find a counterexample)

The Attempt at a Solution

let z ∈ (g°f)^-1(C) such that (g°f)^-1(z) = x for some x∈X
then
z = (g°f)(x)
z = g(f(x))
g^-1(z) = f(x)
f^-1(g^-1(z) = x for some x ∈ X
so z ∈f^-1(g^-1(C))

These types of proofs are very subtle and technical to me and I am not sure If I am assuming anything or if I have sufficiently proven what needed to be proven. I would greatly appreciate some feedback :)

 

[fourier jr]

I'm not sure I follow your first line. I didn't think it was necessary to use two variables (x & z) but if you want to I think it should be
x ∈ (g°f)^-1(C) such that (g°f)^-1(z) = x for some x ∈ X & z ∈ C

 

[toothpaste666]

I am not sure how to do it with one variable. =\ I am a little confused... should I change the last line to
x∈f^-1(g^-1(C)) ?

 

[Mark44]

Homework Statement

for functions f: X -> Y and g: Y ->Z
show that for all subsets C in Z , (g°f)^-1(C) ⊆ f^-1(g^-1(C)) (or find a counterexample)

The Attempt at a Solution

let z ∈ (g°f)^-1(C) such that (g°f)^-1(z) = x for some x∈X
then
z = (g°f)(x)
z = g(f(x))
g^-1(z) = f(x)
f^-1(g^-1(z) = x for some x ∈ X
so z ∈f^-1(g^-1(C))

These types of proofs are very subtle and technical to me and I am not sure If I am assuming anything or if I have sufficiently proven what needed to be proven. I would greatly appreciate some feedback :)

I don't think the statement is true. What if $g \circ f$ is invertible (which would mean that $(g \circ f)^{-1}$ exists), but f or g is not invertible?

 

[SammyS]

I don't think the statement is true. What if $g \circ f$ is invertible (which would mean that $(g \circ f)^{-1}$ exists), but f or g is not invertible?

I'm pretty sure this is dealing with preimages (inverse images), not the images of inverse functions.

 

[toothpaste666]

I think I am lost lol

 

[Fredrik]

I don't think the statement is true. What if $g \circ f$ is invertible (which would mean that $(g \circ f)^{-1}$ exists), but f or g is not invertible?

$g^{-1}(C)$ exists even when $g^{-1}$ doesn't. It's defined by $g^{-1}(C)=\{y\in Y|g(y)\in C\}$.

 

[Fredrik]

let z ∈ (g°f)^-1(C) such that (g°f)^-1(z) = x for some x∈X

This sentence doesn't make sense. I assume you meant "...be such that...". You should just start "let $z\in(g\circ f)^{-1}(C)$". No need to add a "such that". Note that the z defined this way is an element of X, not Z, so the expression $(g\circ f)^{-1}(z)$ doesn't make sense.

You just need to use the definition of the preimage of a set correctly. Here's the definition: If $f:X\to Y$ and $S\subseteq Y$, then $f^{-1}(S)=\{x\in X|f(x)\in S\}$. Note that this means that the following equivalence holds for all $x\in X$.
$$x\in f^{-1}(S)~\Leftrightarrow~ f(x)\in S.$$ I like to do these proofs as a sequence of implications. I would start by saying that the following implications hold for all $x\in X$.
$$x\in(g\circ f)^{-1}(C)~\Rightarrow~(g\circ f)(x)\in C~\Rightarrow~g(f(x))\in C~\Rightarrow~\dots$$ If you find that the sequence of implications ends with $x\in f^{-1}(g^{-1}(C))$, you will have proved that $(g\circ f)^{-1}(C)\subseteq f^{-1}(g^{-1}(C))$.

Use \circ to produce the $\circ$ symbol.

 

[micromass]

I'm pretty sure this is dealing with preimages (inverse images), not the images of inverse functions.

Right, but in his proof he seemed to use invertibility when he wrote $(g\circ f)^{-1}(z)$.

 

[Mark44]

What I had in mind were a pair of functions f (f:X→Y) and g (g:Y → Z) where f was invertible and g wasn't, but $g \circ f$ was invertible.

 

[toothpaste666]

ok let me try again

if x ∈ (g ο f)-1(C)
then (g ο f)(x) ∈ C
so g(f(x)) ∈ C
and f(x) ∈ g-1(C)
so x∈ f-1(g-1(C))

if i understand what Mark44 is saying, then this proof will not work if g is not invertible (you can't get from the third to the fourth line) or if f is not invertible (you can't get from the fourth to the fifth line) . It seems that the way the problem is worded, the fact that (g ο f) is invertible is assumed?

 

[micromass]

ok let me try again

if x ∈ (g ο f)-1(C)
then (g ο f)(x) ∈ C
so g(f(x)) ∈ C
and f(x) ∈ g-1(C)
so x∈ f-1(g-1(C))

if i understand what Mark44 is saying, then this proof will not work if g is not invertible (you can't get from the third to the fourth line) or if f is not invertible (you can't get from the fourth to the fifth line) . It seems that the way the problem is worded, the fact that (g ο f) is invertible is assumed?

Actually, the proof you just gave is perfect and works without assuming invertible.

 

[toothpaste666]

is that because of the second variable before?

 

[Fredrik]

You seem to be asking if the new proof is perfect because the previous attempt involved a second variable. You probably meant to ask something else. But I agree that your proof is good. Since you didn't make any assumptions about x other than $x\in(g\circ f)^{-1}(C)$, what you did proves that $(f\circ g)^{-1}(C)\subseteq f^{-1}(g^{-1}(C))$. The proof of $f^{-1}(g^{-1}(C))\subseteq (g\circ f)^{-1}(C)$ is similar.

 

[fourier jr]

edit: actually never mind. I didn't mean that it was wrong to use a second variable, just that I didn't bother.

 

[toothpaste666]

I think what I meant is... did the problem with invertibility arise because of the second variable?

Btw thank you all for your time and help

 

[fourier jr]

I think what I meant is... did the problem with invertibility arise because of the second variable?

I had the same proof that you got in post #11 & I don't think the invertibility had anything to do with the second variable, I think it just made it a bit more complicated than necessary.

 

[micromass]

The problem was that you wrote $(f\circ g)^{-1}(z)$. The way you used it, is that it is one single element. But it's not, unless the function is invertible. In general, it is a set of elements, not just one.

 

[toothpaste666]

ahh ok I get it now. Thank you all.