Question

Let \(\mathscr{F}\) be the set of all functions \(\mathbb{R} \rightarrow\\{0,1\\} .\) Show that \(|\mathbb{R}|<|\mathscr{F}|\).

Short answer

After assuming that the cardinality of \(\mathbb{R}\) is equal to or greater than \(\mathscr{F}\), we define a function that belongs to \(\mathscr{F}\), but isn't the image of any function in \(\mathbb{R}\) under a supposed bijective function. This contradiction leads to the conclusion that |\(\mathbb{R}\)|<|\(\mathscr{F}\)|.

Step-by-step solution

Setup the Assumption for Proof by Contradiction

Assume for the sake of contradiction that |\(\mathbb{R}\)|≥|\(\mathscr{F}\)|. This means there should exist a bijective function g: \(\mathbb{R}\)\(\rightarrow\mathscr{F}\).

Creating Contradiction

Now, define a function h: \(\mathbb{R}\) \(\rightarrow\{0,1\}\), for which if g(r)(r) = 0 then h(r)=1, and if g(r)(r)=1 then h(r)=0, for all r in \(\mathbb{R}\). By our definition, h is clearly in \(\mathscr{F}\).

Showing No g(r) Could be h

Show that there is no r in \(\mathbb{R}\) such that h=g(r). Following our definition of h, we find for every r in \(\mathbb{R}\), h(r) isn't equal to g(r)(r). Therefore, there is no r for which h=g(r).

Drawing Conclusion from Contradiction

The conclusion from step 3 contradicts our original assumption that there exists a bijective function g, because h is not the image of any r under g. Thus, we've reached a contradiction, which indicates our initial assumption was false. So, |\(\mathbb{R}\)|<|\(\mathscr{F}\)|.