Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $T$ be $T=\{x,\{x\},y \}$ and let $f:A\rightarrow T, \ f(a):=x$, where $A=\{a\}$. Define $B=\{x,y \}$. Now a weird thing happens: We should have that $x \in f(f^{-1}(B))$ by construciton of $f$, but instead we get that $\{x\} \subseteq f(f^{-1}(B))$, althought $\{x\}$ isn't even in the image of $f$!

The argument goes like this:

$x\in B \Rightarrow f^{-1}(x) \subseteq f^{-1}(B) $ by definition. Then $f(f^{-1}(\{x \})) \subseteq f(f^{-1}(B))$. So far, so good. But $$f(f^{-1}(\{x \})) =\{x\} \neq x$$ by definition of the image of a set (the image of a set - even if it contains just one element is also a set - not just the element!), which "proves" the above.

My question are: Hoe to deal with this exotic set ? Should one modifiy the definition of the image to a set with one element to exlude this strange behaviour ? Or is there a better explanation ?

EDIT: I'm terrible sorry for making so many mistakes. I hope I got everything right - but if I didn't, please excuse - it is very tired and I can't focus anymore. I shall correct any mistakes I find tomorrow.

share|improve this question
    
Wait: $f^{-1}(A)$ does not make sense, so $f(f^{-1}(A))$ does not make sense. $f^{-1}$ is a map fro $\mathcal{P}(T)$ to $\mathcal{P}(A)$. Did you mean $A=\{x\}$? If so, what is $f$? Either $f(x)=x$, or $f(x)=\{x\}$. And remember that $f(f^{-1}(\{x\}))$ is a subset of $T$. –  Arturo Magidin Mar 27 '12 at 21:22
1  
There is nothing strange happening, the "proof" is based on the identification of the two [b]different[/b] meanings of $f(\{ x \})$. –  N. S. Mar 27 '12 at 21:23
3  
I can make no sense of this at all, I’m afraid. First, there are two different functions from $A$ to $T$; which one is $f$? Is $f(a)=x$, or is $f(a)=\{x\}$? Moreover, $f^{-1}(A)=\varnothing$, unless you intended $a$ to be either $x$ or $\{x\}$. –  Brian M. Scott Mar 27 '12 at 21:24
    
@ArturoMagidin Probably $A=\{ x \}$. –  N. S. Mar 27 '12 at 21:25
    
Note also that in general, $x\in f(f^{-1}(\{x\}))$ if and only if $x\in\mathrm{Im}(f)$. –  Arturo Magidin Mar 27 '12 at 21:35

2 Answers 2

up vote 7 down vote accepted

Let's be clear: given a function $f\colon R\to S$, then $f$ induces two functions, $$\begin{align*} \underline{f}&\colon\mathcal{P}(R)\to\mathcal{P}(S)&&\text{the `direct image' function}\\ \overline{f}&\colon \mathcal{P}(S)\to\mathcal{P}(R)&&\text{the `inverse image' function}. \end{align*}$$ These functions are defined by: $$\underline{f}(X) = \{s\in S\mid\exists r\in X(f(r)=s)\}$$ and $$\overline{f}(Y) = \{r\in R\mid f(r)\in Y\}.$$

We often just use $f$ to denote $\underline{f}$ and $f^{-1}$ to denote $\overline{f}$, but $f$ and $\underline{f}$ are different functions (and $\overline{f}$ is different from the inverse of $f$, when it exists).

But, let's be very careful and not conflate notations.

Note that in general it is false that if $y\in Y$, then necessarily $y\in \underline{f}(\overline{f}(Y))$. This holds if and only if $y\in \underline{f}(R)$; that is, if and only if $y$ is in the image of $f$.

So, take $X=\{x,\{x\},y\}$ (I will assume that all three elements are pairwise distinct), and let $f\colon\{a\}\to X$ be the function $f(a)=x$.

Now, let us compute $\underline{f}(\overline{f}(B))$: $$\begin{align*} \overline{f}(\{x,y\}) &= \{r\in A\mid f_1(r)\in\{x,y\}\}\\ &= \{r\in A\mid f_1(r)=x\text{ or }f_1(r)=y\}\\ &= \{a\}.\\ \underline{f}(\overline{f}(\{x,y\})) &= \underline{f_1}(\{a\})\\ &= \{f_1(a)\} = \{x\}. \end{align*}$$ Note that $x\in \underline{f}(\overline{f}(B))$, exactly as desired.

It is also true that $\{x\}\subseteq \underline{f}(\overline{f}(B))$, and that $\{x\}$ is not in the image of $f$. But I don't see why this is a matter of concern: if we have $g\colon\{1\}\to\{2\}$ given by $g(1)=2$, then $\{2\}$ is a subset of $\underline{g}(\overline{g}(\{2\}))$ even though $\{2\}$ is not in the image of $g$ (it's not even in the codomain). So what?


You are conflating a lot of notation; for example, $f^{-1}(x)$ does not literally make sense: it should be $\overline{f}$, and the argument should be a subset of $B$, not an element; we often just write $f^{-1}(x)$, but that is sloppy notation that should be used only if there is no danger of ambiguity; but here, there is danger of ambiguity, because $f^{-1}(\{x\})$ could mean either $\overline{f}(\{x\})$, or $\overline{f}(\{\{x\}\})$. And when there is danger of ambiguity, we do not use sloppy notation that introduces the ambiguity.

So your argument should run as follows:

$x\in B$, so $\{x\}\subseteq B$. Therefore, $\overline{f}(\{x\})\subseteq \overline{f}(B)$. Hence, $\underline{f}(\overline{f}(\{x\}))\subseteq \underline{f}(\overline{f}(B))$.

And there is no problem: $\overline{f}(\{x\}) = \{a\}$, and $\underline{f}(\{a\}) = \{f(a)\} = \{x\}\subseteq \underline{f}(\overline{f}(B))$.

Why do you believe it should be $x$, though, is a mystery. Note that we do indeed have $x\in \{x\}=\underline{f}(\overline{f}(B))$, exactly as expected.

I think you'll find that your confusion arises from confusing the element $\{x\}$ of $T$ and the element $\{x\}$ of $\mathcal{P}(T)$ (that is, you are confusing them because in order to apply $\overline{f}$ to "the element $\{x\}$ of $T$" you actually have to compute $$\overline{f}\Bigl(\bigl\{\;\{x\}\;\bigr\}\Bigr),$$ not $\overline{f}({x})$), and of confusing $f$ with $\underline{f}$. Try writing things carefully and without sloppy notation, and you'll see that the apparent contradictions disappear.

share|improve this answer
    
Mac Lane + Birkhoff use $f_*$ and $f^*$. (BTW, I've just noticed that the cover of my second edition says Birkoff!) –  lhf Mar 27 '12 at 23:04
    
Doesn't the direct image go between power sets, and not just the sets? –  Asaf Karagila Mar 27 '12 at 23:38
    
@Asaf: Yes; typo. –  Arturo Magidin Mar 28 '12 at 1:26
    
@lhf: I think Halmos uses underlines and overlines, but I'm away from the office. –  Arturo Magidin Mar 28 '12 at 1:27
    
@lhf, your edition of the book mispells the name of the author?! –  Mariano Suárez-Alvarez Mar 28 '12 at 1:32

In this problem, there is a problem with the notation we use:

$f^{-1}(\{ x \})$ has two different meanings. The preimage of the element $\{ x \}$ and also the preimage of the set $\{ x \}$. But the two meanings are completely different, the "paradox" comes from the fact that during the proof we use both meanings at different spots...

$f^{-1}(\{x \}) \subseteq f^{-1}(A)$ here $\{x\}$ is a subset of $A$.

$f(f^{-1}(\{x \})) =\{x\} \neq x$ here $x$ is an element of $A$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.