Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Contradiction?

  1. Oct 12, 2014 #1
    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.
    Ekran Alıntısı.PNG
    I got confused at what this [itex]B= \{x \in A : x \not\in f(x) \} [/itex] is and
    how it's true that [itex]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.[/itex]
    Can anyone explain what's going on here?
     
  2. jcsd
  3. Oct 12, 2014 #2
    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)\}##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook