# An unwanted property of the set $T=\{x,\{x\} \}$

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.

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

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.

-
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$.

-