# Proof by Contradiction?

I was studying the first chapter "Sets and Structures" of the "A Course in Advanced Calculus - Robert S. Borden". I faced a difficulty at the part of the proof of contradiction.

I got confused at what this $B= \{x \in A : x \not\in f(x) \}$ is and
how it's true that $If~y \in A ~\text{is such that}~f(y)=B, \text{where is y? It must be either in}~B~\text{or in} A \setminus B.$
Can anyone explain what's going on here?

## Answers and Replies

Since ##f:A\rightarrow\mathcal{P}(A)##, ##f(x)## is a subset of ##A## for each ##x##. So for each ##x\in A##, one of ##x\in f(x)## or ##x\not\in f(x)## is true. ##B## is the subset of ##A## where ##x\not\in f(x)## is true.

Since ##B## is a subset of ##A## - and thus ##B\in\mathcal{P}(A)## - it is reasonable to ask if ##B## is in the range of ##f##. It's going to turn out that it's not, and that is the essence of the remainder of the proof and the "source" of the contradiction.

Assuming that ##B## is in the range of ##f##, there is ##y\in A## such that ##f(y)=B##. Forget about what ##f## and ##y## and ##B## are for a moment; that's just the definition of range from pre-calc. Then either ##y\in f(y)=B## or ##y\not\in f(y)=B## (note that ##y\not\in B\Rightarrow y\in A \setminus B##); remember, since ##f(y)=B## is a subset of ##A## and ##y\in A##, one of those has to be true. But either way you go, you end up with an absurdity; either $$y\in f(y)\Rightarrow_1 y\in B\Rightarrow_2 y\not\in f(y)$$ or $$y\not\in f(y)\Rightarrow_2 y\in B\Rightarrow_1 y\in f(y)$$ where the ##\Rightarrow_1## implications are "true" by virtue of the fact that ##f(y)=B## and the ##\Rightarrow_2## implications are true from the definition of ##B=\{x\in A:x\not\in f(x)\}##.