Results 1 to 7 of 7

Math Help - Cardinality

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Cardinality

    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}}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Drexel28 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by tonio View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Drexel28 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by tonio View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by emakarov View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 08:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 03:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 04:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 06:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 03:23 PM

Search Tags


/mathhelpforum @mathhelpforum