Given any set $A$, and any function $f$ whose domain is $A$, show that the set {${x \in A \ | \ x \notin f(x)}$} is not in the range of $f$ (i.e. there is no $a \in A$ such that $f(a)$ = {${x ∈ A \ | \ x \notin f(x)}$}).
Any help would be greatly appreciated.
On
====
I think there needs to be a little bit more to the question than you are stating [*].
$A$ is a set and $f$ is a function with $A$ as a domain. SO $f: A\to ?????$ what? What set is the codomain? What is the output of the function. It does not say.
I'd read this as $f$ could be any function and it could map to any set $X$ so $f: A \to X$ but we are not given any information of what $X$ may be.
But then they talk of $\{x \in A \ | \ x \notin f(x)\}$. But in general this doesn't make sense. $f(x)$ is in general not a set but a single element of $X$. So that implies $X$ is a set of sets. And it is a set of sets which will share some of the same elements of $A$.
This in not a typical function $f:A \to ????$.
This strongly implies $f$ is a function that maps the elements of $A$ to subsets of $A$. i.e. $f:A \to P(A)$ where for some $x \in A$ then $f(x)$ is a subset of $A$.
If that is the case then $S = \{x\in A| x \not \in f(x)\}$ or $S$ is the set of all $x \in A$ that get mapped to subset of $A$ that do not happen to have $x$ as element.
So for example: if $A = \{1,2,3\}$ and $f:\{1,2,3\} \to \{\emptyset, \{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\}, \{1,2,3\}\}$. And $f(2) = \{1,2\}$ then $2 \in \{1,2\}= f(2)$. So $2 \not \in S$. But if $f(1) = \{2,3\}$ then $1 \not \in \{2,3\} = f(1)$ so $1 \not \in f(1)$ so $1 \in S$.
So they are asking you prove that there is no $a\in A$ so that $f(a) = S$.
And this is ... the liar's paradox.
If $f(a) = S$ then either $a \in S$ or $a \not \in S$. If $a \in S$ then $a \not \in f(a) = S$. That is a contradiction. But of $a \not\in S = f(a)$ then $a \in S$. That is a contradiction.
To put this in English (see if this makes sense; it can get confusing):
Let $f$ be a function that maps elements of a set $A$ to subsets of $A$. If we take the set of all elements that that are not elements of the subsets they are mapped to, then there is no element that is mapped to that set. That would cause a logical inconsistency as the element that maps to such a set would be an element of the set it was mapped to if and only if it were not.
===
By the way; paradox resolution: So the liars paradox or Russel's paradox says. Define $f(k) : = S := \{x\in A|x \not \in f(x)\}$. We can't define that set $S$ until after we define $f$ and $S$ relies upon $f$ in its definition. As such it simply will not be any $f(x)$ and such a command is simply not possible.
[*]===== Perhaps more general and set theoretical ====
[*] Or maybe not.
Henning Makholm says in a comment that this is probably is a set theory context in which every object is in some way viewed as being a set.
So if $f: \mathbb N \to \mathbb Z$ via $f(x) = x^2 - 2$ and so $f(2) = 2$ then $2$ is not merely the natural number $2$ but a set as well. As $2 \not \in $ the set we represent as $2 = \{0, 1\} = \{\emptyset, \{\emptyset\}\}$ so $2 \in$ the mystery set. but $f(3) = 7$ and $7 = \{0,1,2,3,4,5,6\}$ and $3\in \{0,1,2,3,4,5,6\} = 7 = f(3)$ so $3$ is not in the mystery set.
In fact I think for this $f$ the mystery set is $\{0,1,2\}= 3$ and there is no $n$ so that $f(n) =3$. (I might be wrong about that.)
.... (redo of above)....
Perhaps a practical way to see this.
In set theoretical terms the natural numbers when viewed as sets are:
$0 = \emptyset$ and
For $n > 0$ then $n = (n-1)\cup \{n-1\} = \{0,1,2,3,......, n-1\}$.
So if $f:\mathbb N \to \mathbb N: f(n)=n^2 - 4n +4=(n-2)^2$. Then $f(0) = 0$ and $0 =\emptyset \not \in \emptyset = 0$ so $0 \not \in f(0)$ so $0 \in S$.
$f(1) = 1$ and $1 = \{0\}$ and $1\not \in \{0\} =1 = f(1)$ so $1 \in S$.
$f(2) = 0$ and $2 \not \in 0= f(2)$ so $2 \in S$.
$f(3) = 1$ and $3 \not \in 1 = f(3)$ so $3 \in S$.
$f(4) = 4$ and $4 \not in 4 = \{0,1,2,3\}$ so $4 \in S$.
For $n\ge 5$ then $f(n) = (n-2)^2 > n$ and $n \in x$ for any $x > n$ so $n \not \in S$.
So $S = \{0,1,2,3,4\} = 5$. And $5 \ne f(n)$ for any $n$.
That's kind of neat.
On
A function $f$ is just a set of ordered pairs (of sets; everything is a set) (which means $\forall x \in f: \exists a,b: x = (a,b)$) , with the special "functional" property that $\forall x,x',y : ((x,y) \in f \land (x,y')) \in f \to y=y'$.
The domain of $f$ is just the set $\operatorname{dom}(f) := \{x: \exists y: (x,y) \in f\}$, the set of all $x$ that are used as "input". The range of $f$ is just $\operatorname{ran}(f):=\{y: \exists x: (x,y) \in f\}$, all sets that occur as "values".
Now suppose $\operatorname{dom}(f) = A$ and define $A'= \{x \in A: x \notin f(x)\}$ which is a well-defined set, by the axiom of separation.
Suppose $A'$ is in the range of $f$, so that $\exists x: (x,A') \in f$. The fact that $(x,A') \in f$ implies that $x \in \operatorname{dom}(f)=A$ and also that $f(x) = A'$.
And by definition of $A'$: $$x \in A' \text{ iff } x \notin f(x) = A'$$
which is a contradiction. So $A' \notin \operatorname{ran}(f)$, as claimed.
On
Cantor's theorem states
Let $A$ be a set. There is no bijective correspondence between $A$ and $\mathcal P(A)$.
where $\mathcal P(A)$ is the power set of $A$, that is, the set of all subsets of $A$.
What you're looking at is the trick that lies at the heart of the proof of this theorem. For some reason the author of what you're reading decided to strip away all the assumptions that are not necessary to prove that the trick works (though they are necessary to get any intuitive idea of what the point of it is).
With more assumptions in it, the trick would be
Let $A$ be a set, and let $f$ be a function $A\to\mathcal P(A)$. Then there is an element of $\mathcal P(A)$ (that is, a subset of $A$) that is not in the range of $f$.
In other words, $f$ is not surjective, and in particular is not a bijection.
And the proof of that would be what you have there -- namely that one subset of $A$ that is guaranteed not to be in the range of $f$ is just $\{x\in A\mid x\notin f(x)\}$.
It turns out that it's not necessary for this argument to know that $f(x)$ is always a subset of $A$. In fact, if there's some $x$ such that $f(x)$ is not a subset of $A$, then this $x$ is no danger for our conclusion that such-and-such subset of $A$ is not in the range of $f$.
Since we're (apparently) working in pure set theory so everything is a set, we can still ask whether $x$ is in $f(x)$ even when $f$ is not a subset of $A$. The answer can be yes or no, but what it is happens not to matter for the conclusion.
It would be a lot clearer, however, if the author had specified that $f$ was $A\to\mathcal P(A)$ instead of just some function with domain $A$.
Hint: The question is about functions $f \colon A \to \mathcal{P}(A)$. That is, functions with domain $A$ such that, for every $t\in A$, the output $f(t)$ is a subset of $A$. [For example, $f \colon \mathbb{N} \to \mathcal{P}(\mathbb{N})$, $f(n) = $ set of divisors of $n$. In this case $f(4) = \{1, 2, 4\}$.]
Let $B = \{x \in A \mid x\not\in f(x)\} \subset A$, hence $B \in \mathcal{P}(A)$. Suppose that $B$ were in the image of $f$ and let $a\in A$ such that $f(a) = B$. Show that both $a\in B$ and $a\not\in B$ lead to contradictions.
Added: This is a formal presentation of the Barber paradox (https://en.wikipedia.org/wiki/Barber_paradox).
More precisely, suppose we are talking about people on an island (close system). For every person $x$, let $f(x)$ be the set of people shaved by $x$ (may include $x$ or not). Then $B$ is the set of people who do not shave themselves. Is there any person who shaves exactly those people who do not shave themselves? Does that person shave itself?