TransWikia.com

The number of the sets, $A$ s.t. $f^{-1}(f(A))=A$

Mathematics Asked by se-hyuck yang on February 3, 2021

Say $f colon X to Y$ such that $1mapsto2, 2mapsto3, 3mapsto4, 4mapsto3, 5mapsto1, 6mapsto2, 7mapsto3$.

(Here the $X ={1,2,3,4,5,6,7}, Y = {1,2,3,4,5,6}$)

Find the number of the sets $A$ satisfying $f^{-1}(f(A))=A$


In my thought, To claim $f^{-1}(f(A))=A$, $f$ should be one to one function(or injective) for the set $A$.

So considering $f({1,6}) = {2}$, $f({2,4,7}) = {3}$, $f({3}) = {4}$ and $f({5}) = {1}$

So I classified the case like the below for making the injective for $f : A to Y$

$(1)$ $f({5}) = {1}$ ; There are $2$ cases $5$ is element of the $A$ or not.

$(2)$ $f({3}) = {4}$ ; There are $2$ cases $4$ is element of the $A$ or not.

$(3)$ $f({2,4,7}) = {3}$; There are $4$ case, because $A$ should be include only one element among ${2,4,7}$ or not include any element.

$(4) f({1,6}) = {2}$ ; with the same logic $A$ can be $3$ cases.

So my answer is $ 2times 2 times 4 times 3 =48$ But the answer was 16. What the point did I have mistake? Thanks.

One Answer

You have the idea, but check that for those elements that map to the same one, you need to either include them all or not include any. For example, if you let $A = {2,4}$, then $f^{-1}(f(A)) = f^{-1}({3}) = {2,4,7}$. This is exactly the problem that hinders $f^{-1}(f(A))$ and $A$ from being the same.

So, the set $A$ has to be the result of the union of any of these: ${5}$, ${3}$, ${2,4,7}$, ${1,6}$, that is, the preimages of single elements. Hence there are $4^2 = 16$ possible sets.

Edit. As an exercise in set theory, you can rigorously prove what we've used here: that given $f: X mapsto Y$ and $A subset X$, we have:

$$f^{-1}(f(A)) = A iff forall a in A, f^{-1}(f({a})) subseteq A iff forall y in Y, f^{-1}({y}) subseteq A$$

Answered by Miguel González on February 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP