Question

Suppose the function \(f \rightarrow X \rightarrow Y\) is onto. Prove or disprove that the induced map \(\bar f^{-1} \mathcal P \left({Y}\right) \rightarrow \mathcal P \left({X}\right)\) is onto. As a first step, make sure to state what it means that a function is onto.


The function \(f: X \rightarrow Y\) is onto which means it's a surjection, and the definition is \((\forall Y) (\exists X) (f(x) = y)\)

Answer 1

@wio do I just provide an example that would prove that this is a surjection?

Answer 2

like... what if we let X = [a,b,c,d] and Y = [1.2,3] then we could find the pairings to confirm that \[\bar f^{-1} \] is indeed a function from powerset (y) to powerset (x)

Answer 3

f(a) = 1 f(b) = 3 f(c) = 2 f(d) = 3

Answer 4

induced map?

Answer 5

yes

Answer 6

isn't that the union of all elements?

Answer 7

I need a clear definition of induced map

Answer 8

k let me check in my book

Answer 9

Let \(f: X \rightarrow Y\). The set function induced by \(f\) is the function \(\bar f \mathcal P \left({X}\right) \rightarrow \mathcal P \left({Y}\right) \) defined by the rule that for all \(A \in \mathcal P \left({X}\right) \).
\(\bar f(A) =[y \in Y : (\exists x \in A) [f(x) =y]]=[f(x): x \in A]\)

Answer 10

hmm might work if the bar wasn't an inverse.. there's another definition with f bar inverse

Answer 11

def... 5.3.8 Let \( f : X \rightarrow Y\). For each set \(B \in \mathcal P \left({Y}\right) . \), define the function \(\bar f^{-1} : \mathcal P \left({Y}\right) \rightarrow \mathcal P \left({X}\right)\) by \(\bar f^{-1} (B) =[x \in X: f(x) \in B]\) . .

Answer 12

What about \(\bar{f} ^{ -1}(\emptyset)\)?

Answer 13

wouldn't that be an emptyset?! ^

Answer 14

prove or disprove...

Answer 15

Okay how about this....

Answer 16

so.. if we pick wrong..oh boy

Answer 17

We should try to find a counter example.

Answer 18

I do have one idea though...

Answer 19

ok... so if isn't not a surjection then f(x) can't equal to y

Answer 20

*if it

Answer 21

\[
\bar f^{-1}(\{1,2\}) = \{1,2,3\}
\]and\[
\bar f^{-1}(\{2\}) = \{3\}
\]

Answer 22

I think from your counter example, there is no way to get \(\bar f^{-1}(S) = \{2,3\}\) since if you want \(2\) then you're going to get \(1\) as well.

Answer 23

So while \(\bar f^{-1}\) is a function, it isn't onto.

Answer 24

ok but shouldn't we have the f first and then the f inverse second.. and finally the f bar inverse.. because my book has it as f: [1,2,3] -> [a,b,c] and it was defined by f(1) = a f(2) = a and f(3) = b ...
so the inverses are f^-1(a) = 1 f^-1(a) = 2 and f^-1(b) = 3

Answer 25

oops that's f inverse isn't a function D:

Answer 26

what if we want to prove it.. what would we need to do? just wondering

Answer 27

X={1,2,3}
Y={a,b}
f(1) = a
f(2) = a
f(3) = b
fbar({1,2,3})={a,b}
fbar({2,3})={a,b}

fbar^-1 {a,b}={1,2,3}
as wio pointed out, fbar^-1 will never equal {2,3}, an element of p(X)
thus fbar^-1 is not onto

Answer 28

oh I see it... they don't equal at all...so it's not a surjection ..

Answer 29

would anyone like to check my induction proof? I'm kind of whizzed that I got it wrong because I swear I've done everything right.

Answer 30

\[
\bar f^{-1}(\emptyset) = \emptyset \\
\bar f^{-1}(\{a\}) = \{1,2\} \\
\bar f^{-1}(\{b\}) = \{3\} \\
\bar f^{-1}(\{a,b\}) = \{1,2,3\}
\]You can't find \(\{1\}\), \(\{2\}\), \(\{1,3\}\) or \(\{2,3\}\)

Answer 31

Also, when you think about it, if \( \|\mathcal P(Y)\| < \|\mathcal P(X)\| \) then it is impossible for it to be onto.

Answer 32

k... new question..