4

enter image description here

This comes from the textbook: Edward A. Scheinerman - Mathematics: A Discrete Introduction-Cengage Learning (2012)

I understand everything in the proof except for why Dr. Scheinerman defined the set $B$ as he did. Informally, he says that B is a set that $f$ "misses", i.e. there is no $a \in A $ such that $f(a) = B$. How does the formal definition of $B$ he gives capture this idea?

The definition of $B$ is

$B = \{x \in A: x \notin f(x) \}$, which I read as: "$B$ is the set of all elements $x$ in $A$ that are not in the subsets they map to under $f$". Is that an accurate reading? If so, how does that definition encapsulate all the sets that $f$ "misses"?

James Ronald
  • 2,331

2 Answers2

3

This is a classic diagonalization argument. To see why $B$ is defined the way it is, let's work with a simpler example.

The idea is best exemplified in Russell's paradox (which was inspired by Cantor's proof). The idea shows that the collection of all sets is not a set. The reason why is to consider the subset $B'=\{x:x\not\in x\}\text{.}$ Clearly if $B'\in B'$ then it meets the defined requirement: $B'\not\in B'$, a contradiction. But if $B'\not\in B'$, then it doesn't meet the defined requirement, and thus $B'\in B'$, again a contradiction. So there can be no such set $B'$.

Cantor's argument is basically just an analogue of this reasoning, translated through $f$: there can be no $b$ with $f(b)=B$. A classic example of this is the barber paradox. Let $A$ be the set of all barbers, and let $f:A\rightarrow 2^A$ be the function that maps a barber $b$ to the set of barbers who cut $b$'s hair.

Now we can consider $$B=\{b\in A:b\not\in f(b)\}=\{b\text{ a barber}:b\text{ does not cut their own hair}\}\text{.}$$ There can be no barber $b\in A$ with $f(b)=B$, i.e. a barber who cuts the hair of every barber who does not cut their own hair. Why? Well, is $b\in f(b)$? Is $b\not\in f(b)$? The same idea applies.

JunderscoreH
  • 1,398
  • 1
  • 7
  • 11
  • 1
    Always noticed the similarity, but did not know the one inspired the other. That's right, Cantor was before Russell. Makes sense. –  Aug 08 '19 at 20:22
1

Yes, correct reading.

It's not aiming to capture all such subsets, but to show there exists one. And $B$ is such. Done.

Berci
  • 90,745