Cardinality

**Drexel28** · December 28th 2009, 12:48 AM

Hello friends. I was wondering if you could critique the following proof. Thank you very much.

Notation:

$X\cong Y$ means that $X,Y$ have the same cardinal number.

Problem: Find the cardinality of the set of all functions $f$ such that $f:[0,1]\mapsto\mathbb{R}$ .

Claim: The cardinality of this set is $2^{\mathfrak{c}}$ where $\mathfrak{c}$ is the cardinality of the continuum.

Proof:

Lemma: $X\cong Y\implies \wp\left(X\right)\cong\wp\left(Y\right)$

Proof: Since $X\cong Y$ we know that there exists some $f:X\mapsto Y$ such that $f$ is a bijection. Clearly then, the function $\tilde{f}:\wp\left(X\right)\mapsto\wp\left(Y\right )$ given by $A\mapsto f\left(A\right)$ is a bijection. The conclusion follows. $\blacksquare$ .

Lemma: Let $A=\left\{f:\text{ }f:[0,1]\mapsto\mathbb{R}\right\}$ and $B=\left\{f:\text{ }f:[0,1]\mapsto[0,1]\right\}$ . then $A\cong B$ .

Proof: Since $\mathbb{R}\cong[0,1]$ we know there exists some $g:\mathbb{R}\mapsto[0,1]$ such that $g$ is a bijection. Then define $\varphi:A\mapsto B$ by $f\mapsto gf$ . To see that this is a bijection suppose that

$\varphi\left(f\right)=\varphi\left(\tilde{f}\right )\implies gf=g\tilde{f}$ and since $g$ is an injection it follows that $f=\tilde{f}$ . And since $B\subseteq A$ the conclusion follows. $\blacksquare$

Now, define a mapping $\varphi:\wp\left([0,1]\right)\mapsto B$ by $A\mapsto f_A$ where $f_A=\begin{cases} 1 & \mbox{if}\quad x\in A \\ 0 & \mbox{if} \quad x\notin A\end{cases}$ . To see that this is an injection assume that $\varphi\left(A\right)=\varphi\left(B\right)\implie s f_A=f_B$ and since $f_A=f_B$ if and only if

$f_A(x)=f_B(x)\quad\forall x\in [0,1]$ we see that $x\in A\implies f_A(x)=1=f_B(x)\implies x\in B$ where it follows, by an analogous argument, that $x\in B\implies x\in A$ which tells us precisely that $A=B$

from where it follows that $\varphi:\wp\left([0,1]\right)\mapsto B$ is an injection.

Now, define a mapping $\Delta:B\mapsto\wp\left([0,1]^2\right)$ by $f\mapsto\Gamma_f$ where, keeping with common notation, we have that $\Gamma_f=\left\{(x,y)\in[0,1]^2:y=f(x)\right\}$ is the graph of $f$ . It should be clear that this is an

injection, but if not assume that $\Delta\left(f\right)=\Delta\left(\bar{f}\right)\im plies \Gamma_f=\Gamma_{\bar{f}}$ and let $x\in[0,1]$ . We then see that $\left(x,f(x)\right)\in\Gamma_f$ but since $\Gamma_f=\Gamma_{\bar{f}}$ we see that $\left(x,f(x)\right)\in\Gamma_{\bar{f}}$ . But, since every element of $\Gamma_{\bar{f}}$ is

of the form $\left(x,\bar{f}(x)\right)$ we see that $\left(x,f(x)\right)=\left(x,\bar{f}(x)\right)\impl ies f(x)=\bar{f}(x)$ and since $x$ was arbitrary it follows that $f(x)=\bar{f}(x)\quad\forall x\in[0,1]\implies f=\bar{f}$ . Thus $\Delta:B\mapsto\wp\left([0,1]^2\right)$ is an injection.

Lastly, noting that $[0,1]\cong [0,1]^2$ (by previous problem) it follows by our lemma that $\wp\left((0,1)\right)\cong\wp\left([0,1]^2\right)$ which means that there exist some $g:\wp\left([0,1]^2\right)\mapsto\wp\left([0,1]\right)$ which is bijective. Clearly

then, $g\Delta:B\mapsto\wp\left([0,1]\right)$ is an injection. Thus, by virtue of the Schroder-Bernstein theorem we may conclude that $B\cong\wp\left([0,1]\right)$ . But, by our lemmas we see that $A\cong B,\wp\left([0,1]\right)\cong\wp\left(\mathbb{R}\right)$ from

which we may conclude, by the transitivity of the $\cong$ relation, that $A\cong\wp\left(\mathbb{R}\right)$ and since $\left|\wp\left(\mathbb{R}\right)\right|=2^{\mathfr ak{c}}$ our proof is done.

Remark: I believe that this can be extended to show that if $A$ is uncountable and $\left|B\right|\geqslant2$ that $\left|\left\{f:\text{ }f:A\mapsto B\right\}\right|=2^{\mathfrak{c}}$ . This can be concluded since, it is easy to prove that when $A=\mathbb{R}$ and

$B=\{0,1\}$ that $\left\{f:\text{ }f:A\mapsto B\right\}\cong\wp\left(\mathbb{R}\right)$ and a little finagling with the above proof shows that $\left|\left\{f:\text{ }f:\mathbb{R}\mapsto\mathbb{R}\right\}\right|=2^{\ mathfrak{c}}$ from where the conclusion follows since

$2^{\mathfrak{c}}=\left|\left\{f:\text{ }\mathbb{R}\mapsto\{0,1\}\right\}\right|\leqslant\ left|\left\{f:\text{ }f:A\mapsto B\right\}\right|\leqslant\left|\left\{f:\text{ }f:\mathbb{R}\mapsto\mathbb{R}\right\}\right|=2^{\ mathfrak{c}}$

**tonio** · December 28th 2009, 03:15 AM

Originally Posted by Drexel28

Hello friends. I was wondering if you could critique the following proof. Thank you very much.

Notation:

$X\cong Y$ means that $X,Y$ have the same cardinal number.

Problem: Find the cardinality of the set of all functions $f$ such that $f:[0,1]\mapsto\mathbb{R}$ .

Claim: The cardinality of this set is $2^{\mathfrak{c}}$ where $\mathfrak{c}$ is the cardinality of the continuum.

Proof:

Lemma: $X\cong Y\implies \wp\left(X\right)\cong\wp\left(Y\right)$

Proof: Since $X\cong Y$ we know that there exists some $f:X\mapsto Y$ such that $f$ is a bijection. Clearly then, the function $\tilde{f}:\wp\left(X\right)\mapsto\wp\left(Y\right )$ given by $A\mapsto f\left(A\right)$ is a bijection. The conclusion follows. $\blacksquare$ .

Lemma: Let $A=\left\{f:\text{ }f:[0,1]\mapsto\mathbb{R}\right\}$ and $B=\left\{f:\text{ }f:[0,1]\mapsto[0,1]\right\}$ . then $A\cong B$ .

Proof: Since $\mathbb{R}\cong[0,1]$ we know there exists some $g:\mathbb{R}\mapsto[0,1]$ such that $g$ is a bijection. Then define $\varphi:A\mapsto B$ by $f\mapsto gf$ . To see that this is a bijection suppose that

$\varphi\left(f\right)=\varphi\left(\tilde{f}\right )\implies gf=g\tilde{f}$ and since $g$ is an injection it follows that $f=\tilde{f}$ . And since $B\subseteq A$ the conclusion follows. $\blacksquare$

Now, define a mapping $\varphi:\wp\left([0,1]\right)\mapsto B$ by $A\mapsto f_A$ where $f_A=\begin{cases} 1 & \mbox{if}\quad x\in A \\ 0 & \mbox{if} \quad x\notin A\end{cases}$ . To see that this is an injection assume that $\varphi\left(A\right)=\varphi\left(B\right)\implie s f_A=f_B$ and since $f_A=f_B$ if and only if

$f_A(x)=f_B(x)\quad\forall x\in [0,1]$ we see that $x\in A\implies f_A(x)=1=f_B(x)\implies x\in B$ where it follows, by an analogous argument, that $x\in B\implies x\in A$ which tells us precisely that $A=B$

from where it follows that $\varphi:\wp\left([0,1]\right)\mapsto B$ is an injection.

Now, define a mapping $\Delta:B\mapsto\wp\left([0,1]^2\right)$ by $f\mapsto\Gamma_f$ where, keeping with common notation, we have that $\Gamma_f=\left\{(x,y)\in[0,1]^2:y=f(x)\right\}$ is the graph of $f$ . It should be clear that this is an

injection, but if not assume that $\Delta\left(f\right)=\Delta\left(\bar{f}\right)\im plies \Gamma_f=\Gamma_{\bar{f}}$ and let $x\in[0,1]$ . We then see that $\left(x,f(x)\right)\in\Gamma_f$ but since $\Gamma_f=\Gamma_{\bar{f}}$ we see that $\left(x,f(x)\right)\in\Gamma_{\bar{f}}$ . But, since every element of $\Gamma_{\bar{f}}$ is

of the form $\left(x,\bar{f}(x)\right)$ we see that $\left(x,f(x)\right)=\left(x,\bar{f}(x)\right)\impl ies f(x)=\bar{f}(x)$ and since $x$ was arbitrary it follows that $f(x)=\bar{f}(x)\quad\forall x\in[0,1]\implies f=\bar{f}$ . Thus $\Delta:B\mapsto\wp\left([0,1]^2\right)$ is an injection.

Lastly, noting that $[0,1]\cong [0,1]^2$ (by previous problem) it follows by our lemma that $\wp\left((0,1)\right)\cong\wp\left([0,1]^2\right)$ which means that there exist some $g:\wp\left([0,1]^2\right)\mapsto\wp\left([0,1]\right)$ which is bijective. Clearly

then, $g\Delta:B\mapsto\wp\left([0,1]\right)$ is an injection. Thus, by virtue of the Schroder-Bernstein theorem we may conclude that $B\cong\wp\left([0,1]\right)$ . But, by our lemmas we see that $A\cong B,\wp\left([0,1]\right)\cong\wp\left(\mathbb{R}\right)$ from

which we may conclude, by the transitivity of the $\cong$ relation, that $A\cong\wp\left(\mathbb{R}\right)$ and since $\left|\wp\left(\mathbb{R}\right)\right|=2^{\mathfr ak{c}}$ our proof is done.

Remark: I believe that this can be extended to show that if $A$ is uncountable and $\left|B\right|\geqslant2$ that $\left|\left\{f:\text{ }f:A\mapsto B\right\}\right|=2^{\mathfrak{c}}$ . This can be concluded since, it is easy to prove that when $A=\mathbb{R}$ and

$B=\{0,1\}$ that $\left\{f:\text{ }f:A\mapsto B\right\}\cong\wp\left(\mathbb{R}\right)$ and a little finagling with the above proof shows that $\left|\left\{f:\text{ }f:\mathbb{R}\mapsto\mathbb{R}\right\}\right|=2^{\ mathfrak{c}}$ from where the conclusion follows since

$2^{\mathfrak{c}}=\left|\left\{f:\text{ }\mathbb{R}\mapsto\{0,1\}\right\}\right|\leqslant\ left|\left\{f:\text{ }f:A\mapsto B\right\}\right|\leqslant\left|\left\{f:\text{ }f:\mathbb{R}\mapsto\mathbb{R}\right\}\right|=2^{\ mathfrak{c}}$

Hmmmm....can't you use that the cardinality of all the functions from set A to set B is $|B|^{|A|}$ , together with arithmetic of cadinals?

Because if you can then the wanted cardinal is simply $|\mathbb{R}|^{|[0,1]|}=\mathfrak{c}^\mathfrak{c}=\left(2^{\aleph_0}\ri ght)^\mathfrak{c}=2^{\aleph_0\cdot\mathfrak{c}}=2^ \mathfrak{c}$ ...and you get to save lots of ink and paper.

Tonio

**Drexel28** · December 28th 2009, 09:20 PM

Originally Posted by tonio

Hmmmm....can't you use that the cardinality of all the functions from set A to set B is $|B|^{|A|}$ , together with arithmetic of cadinals?

Because if you can then the wanted cardinal is simply $|\mathbb{R}|^{|[0,1]|}=\mathfrak{c}^\mathfrak{c}=\left(2^{\aleph_0}\ri ght)^\mathfrak{c}=2^{\aleph_0\cdot\mathfrak{c}}=2^ \mathfrak{c}$ ...and you get to save lots of ink and paper.

Tonio

Hello, Tonio! I wish! My last statement was purely a remark. I am reviewing some old stuff for an upcoming class. The class happens to be mostly focused on modern analysis and topology. Consequently, the concept of cardinal arithmetic is not used. I guess that I could introduce the concept and show that it is consistent, but that almost seems like more work!

So, I'm sorry if I missed something but I didn't see that you said this proof was either right or wrong.

**tonio** · December 29th 2009, 01:21 AM

Originally Posted by Drexel28

Hello, Tonio! I wish! My last statement was purely a remark. I am reviewing some old stuff for an upcoming class. The class happens to be mostly focused on modern analysis and topology. Consequently, the concept of cardinal arithmetic is not used. I guess that I could introduce the concept and show that it is consistent, but that almost seems like more work!

So, I'm sorry if I missed something but I didn't see that you said this proof was either right or wrong.

Honestly I didn't read your whole proof: it's too looooong for me. But I did read that you use very happily Cantor-Bernstein-Schroeder Theorem, and if you can allow yourself to use this powerful theorem, then I'd say you can use the simple rules of arithmetic of cardinals!! Thus my demonstration is way shorter and simple.

**Drexel28** · December 29th 2009, 01:24 AM

Originally Posted by tonio

Honestly I didn't read your whole proof: it's too looooong for me. But I did read that you use very happily Cantor-Bernstein-Schroeder Theorem, and if you can allow yourself to use this powerful theorem, then I'd say you can use the simple rules of arithmetic of cardinals!! Thus my demonstration is way shorter and simple.

True, using the Schroder-Bernstein theorem may seem to be a bigger jump than using cardinal arithmetic but that would by like computing the area of a triangle using an integral for me. I can't just introduce an entirely new concept to prove this theorem, for theoretically I would have to justify all of the countless lemmas you have implicitly used in your "way shorter and simpler" proof.

**emakarov** · January 1st 2010, 10:42 AM

The proof seems correct, but

Remark: I believe that this can be extended to show that if

is uncountable and

that

.

should say that $|A|\le\mathfrak{c}$ and something about $|B|$ , e.g., that it is finite

**Drexel28** · January 1st 2010, 11:28 AM

Originally Posted by emakarov

The proof seems correct, but
should say that $|A|\le\mathfrak{c}$ and something about $|B|$ , e.g., that it is finite

Thank you emakarov. Really what I should say, as you said, is that $A\cong \mathbb{R}$ and $2\leqslant \left|B\right|\leqslant \mathfrak{c}$ .

Thread: Cardinality

LinkBack

Thread Tools

Display

Cardinality

Similar Math Help Forum Discussions

Cardinality

Cardinality of R, [0,1], R^2, [0,1] x [0,1]

Cardinality

Cardinality

Cardinality

Search Tags