Complement of domain subset equals codomain complement?

33 Views Asked by At

I have come up with a proof and I don't quite know why it's wrong.

Let $A,Y$ be sets and $X \subset Y$ and $f: X\rightarrow Y$ be a function. Then $f(\overline{X}) = \overline{f(X)}$. I know that this is wrong and I can think of counterexamples as well, but I came up with a proof that seems right to me:

First I prove $f(\overline{X}) \subset \overline{f(X)}$: Let $x\in f(\overline{X})$, then $\exists y\in \overline{X}$ such that $x = f(y)$. For this $y$ however, $y\notin X$ hence $f(y)\notin f(X)$. Thus, $f(y)\in\overline{f(X)}$.

Now the other way round: Let $x\in\overline{f(X)}$. Then $x\notin f(X)$, hence $\forall y\in X: x \neq f(y)$. Thus the element that returns $x$ must be in $\overline{X}$. By definition, since there exists a y in $\overline{X}$ such that $x = f(y)$, $x\in f(\overline{X})$.

EDIT: Added the fact that X is a subset.

Where does this proof go wrong?

1

There are 1 best solutions below

2
On

None of the inclusions $f(\bar{X})\subset \overline{f(X)}$ or $\overline{f(X)}\subset f(\bar{X})$ is true. You have to impose injectivity/surjectivity conditions.

Note on notation: if you are considering $X$ as a set, then $\bar{X}$ is the empty set. I imagine that you want to take a subset $Z\subset X$ and take its complement in $X$.