Functional equation : $f[X-f[X]]=f[X]-f[f[X]]$

85 Views Asked by At

Let $X$ be non-empty subset and $f : X \to X$ be $1-1$ function.

Prove that $f[X-f[X]]=f[X]-f[f[X]]$, where $f[A]$ is image of set $A$ under function $F$ :

$f[A] =\{y\in X :$ there exists $x \in A$ such that $y=f(x)\}$

My attempt :

Since $f$ is $1-1$ function, $f[X]$ is a subset of $X$.

Similarly, $f[f[x]]$ is a subset of $f[X]$.

so $f[f[x]]$ is a subset of $X$.

2

There are 2 best solutions below

0
On

Let $a \in f[X-f[X]]$.

Then, there exists $b \in X-f[X]$ such that $f(b)=a$.

Since $b \notin f[X]$, we know that there does not exist $c \in X$ such that $f(c)=b$.

We now show that $a \notin f[f[X]]$. Assume the contrary, and let $f(m)=a$ where $m \in f[X]$. Since $f$ is injective, we obtain $m=b$. Since $m \in f[X]$, there exists $n$ such that $f(n)=m$, i.e. $f(n)=b$, which is a contradiction to the last paragraph.

Therefore, $a \in f[X]-f[f[X]]$.


Let $a \in f[X]-f[f[X]]$, i.e. $a \in f[X]$ and $a \notin f[f[X]]$.

Let $b \in X$ satisfy $f(b)=a$.

We now show that $b \notin f[X]$. Assume the contrary, and let $f(c)=b$. Then, $f(f(c))=f(b)=a$, contradicting $a \notin f[f[X]]$.

Therefore, $a \in f[X-f[X]]$.


We have shown that $a \in f[X-f[X]] \implies a \in f[X]-f[f[X]]$ and $a \in f[X]-f[f[X]] \implies a \in f[X-f[X]]$, so we conclude with $a \in f[X-f[X]] \iff a \in f[X]-f[f[X]]$, whence $f[X-f[X]] = f[X]-f[f[X]]$ by the axiom of extension.

0
On

More generally, $f[A-B]=f[A]-f[B]$ for subsets $A,B\subseteq X$.

Indeed, if $x\in f[A-B]$, then there exists $y\in A-B$ with $f(y)=x$. Then $y\in A$ and so $x\in f[A]$. Certainly, $x\notin f[B]$ as that would mean there exists $z\in B$ with $f(z)=x$, where from infectivity of $f$, we find $z=y$, contradicting $y\notin B$. We conclude $f[A-B]\subseteq f[A]-f[B]$.

The other direction, $f[A-B]\supseteq f[A]-f[B]$. is similar.