7.4. Does All This Really Work? 225
jAjis undefined. Ais countably infinite. Ais uncountable. Ais finite. NsurjA. 8n 2 N,jAjn. 8n 2 N,jAjn. 9n 2 N:jAjn. 9n 2 N:jAj< n.Problem 7.7.
LetAto be some infinite set andBto be some countable set. We know from
Lemma 7.1.7 that
Abij.A[fb 0 g/
for any elementb 02 B. An easy induction implies that
Abij.A[fb 0 ;b 1 ;:::;bng/ (7.7)for any finite subsetfb 0 ;b 1 ;:::;bngB.
Students sometimes think that (7.7) shows thatAbij.A[B/. Now it’s true that
Abij.A[B/for all suchAandBfor any countable setB(Problem 7.13), but the
facts above do not prove it.
To explain this, let’s say that a predicateP.C/isfinitely discontinuouswhen
P.A[F/is true for everyfinitesubsetFB, butP.A[B/is false. The hole
in the claim that (7.7) impliesAbij.A[B/is the assumption (without proof) that
the predicate
P 0 .C/WWDŒAbijCç
is not finitely discontinuous. This assumption aboutP 0 is correct, but it’s not com-
pletely obvious and takes some proving.
To illustrate this point, letAbe the nonnegative integers andBbe the nonneg-
ative rational numbers, and remember that bothAandBare countably infinite.
Some of the predicatesP.C/below are finitelydiscontinuous and some arenot.
Indicate which is which.