Results 1 to 9 of 9

Math Help - Cardinality Inequality Proof

  1. #1
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1

    Cardinality Inequality Proof

    Prove that |[0,1]| < |\mathbb{R}^{[0,1]}|.

    Attempted Solution:
    To prove this inequality I need to show there exists a 1-1 function f: [0,1] \to \mathbb{R}^{[0,1]}. And that all functions f: [0,1] \to \mathbb{R}^{[0,1]} cannot be ONTO.

    I'm having trouble conceptualizing a 1-1 function that maps from  [0,1] \to \text{set of all functions:  } g:[0,1] \to \mathbb{R} . However to the best of my knowledge I need a function that takes values from the interval [0,1] as input and outputs a function from the set of functions \mathbb{R}^{[0,1]} . A simple function in \mathbb{R}^{[0,1]} that I'm thinking of is just a straight line, so g(x) = x + b where b acts like the y-intercept. So my idea for a 1-1 mapping from f: [0,1] \to \mathbb{R}^{[0,1]}, would take inputs from [0,1] and map them to various parallel lines, g(x) with different values for b. So basically f(b) = x + b, \text{ where }x, b \in [0,1]. So my function is mapping to various parallel lines, I think that insures that f is 1-1.

    If my 1-1 function is indeed correct, now I need to prove all functions f: [0,1] \to \mathbb{R}^{[0,1]} cannot be ONTO. And I can't think of a way to start making progress on this part.

    Thanks in advance for the help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by utopiaNow View Post
    Prove that |[0,1]| < |\mathbb{R}^{[0,1]}|.
    So my idea for a 1-1 mapping from f: [0,1] \to \mathbb{R}^{[0,1]}, would take inputs from [0,1] and map them to various parallel lines, g(x) with different values for b. So basically f(b) = x + b, \text{ where }x, b \in [0,1]. So my function is mapping to various parallel lines, I think that insures that f is 1-1.
    Let's make the functions a bit clearer.
    \left( {\forall b \in [0,1]} \right)\left[ {f_b (x) = x + b} \right]\, \Rightarrow \,f_b  \in \mathbb{R}^{[0,1]}
    Now define \Phi :[0,1] \mapsto \mathbb{R}^{[0,1]} ,\;\,\Phi (b) = f_b .

    Is this true f(x) = x^2 \, \Rightarrow \,f \in \mathbb{R}^{[0,1]} ?.

    Can you finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1
    Quote Originally Posted by Plato View Post
    Let's make the functions a bit clearer.
    \left( {\forall b \in [0,1]} \right)\left[ {f_b (x) = x + b} \right]\, \Rightarrow \,f_b  \in \mathbb{R}^{[0,1]}
    Now define \Phi :[0,1] \mapsto \mathbb{R}^{[0,1]} ,\;\,\Phi (b) = f_b .

    Is this true f(x) = x^2 \, \Rightarrow \,f \in \mathbb{R}^{[0,1]} ?.

    Can you finish?
    Hmm, f(x) = x^2 \, \Rightarrow \,f \in \mathbb{R}^{[0,1]} does seem to me to be true. Because f(x) = x^2 is a valid function that could map from [0,1] \to \mathbb{R} . However I'm not sure how I'm supposed to use this piece of info. Is it the fact that, with f(x) = x^2 \, \Rightarrow \,f \in \mathbb{R}^{[0,1]} being true, it tells us that the function that was defined, namely \Phi :[0,1] \mapsto \mathbb{R}^{[0,1]} ,\;\,\Phi (b) = f_b fails to be onto as it never maps to f(x) = x^2?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by utopiaNow View Post
    Is it the fact that, with f(x) = x^2 \, \Rightarrow \,f \in \mathbb{R}^{[0,1]} being true, it tells us that the function that was defined, namely \Phi :[0,1] \mapsto \mathbb{R}^{[0,1]} ,\;\,\Phi (b) = f_b fails to be onto as it never maps to f(x) = x^2?
    Correct.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1
    Ah I see. Quick question though, I thought the idea was to show that every function possible from [0,1] \to \mathbb{R} fails to be onto. It seems what we've done is just show that one specific function is 1-1 but fails to be onto. Aren't these two different things? The first one says we need a universal disproof, however it seems all I've done is give one example that meets the criteria of the disproof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by utopiaNow View Post
    Ah I see. Quick question though, I thought the idea was to show that every function possible from [0,1] \to \mathbb{R} fails to be onto. It seems what we've done is just show that one specific function is 1-1 but fails to be onto. Aren't these two different things? The first one says we need a universal disproof, however it seems all I've done is give one example that meets the criteria of the disproof.
    That is also correct. I was addressing the example you started with.
    What exactly is the definition your textbook uses for this inequality?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1
    Quote Originally Posted by Plato View Post
    That is also correct. I was addressing the example you started with.
    What exactly is the definition your textbook uses for this inequality?
    The textbook says for this statement: " |A| < |B|" to be true it must be that there exists a 1-1 function from A to B but no bijective function from A to B. So to prove |[0,1]| < |\mathbb{R}^{[0,1]}| I was first showing there existed a 1-1 mapping from [0,1] to \mathbb{R}^{[0,1]}. And the second part of my proof requires me to show that every possible function from [0,1] to \mathbb{R}^{[0,1]} fails to be onto, which is the step I'm stuck on at the moment.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Here is the way I present this material; it may not conform to your material.

    For any set A, \left| A \right| < \left| {P(A)} \right|. (Cantorís theorem)
    The cardinality of any set is less that the cardinality of its power set.

    For any set A, \left| {P(A)} \right| = \left| {2^A } \right|.
    Where \left| {2^A } \right| = \left\{ {f:A \mapsto \left\{ {0,1} \right\}} \right\}.

    This sequence of theorems proves your result.
    Note: \left| {\left[ {0,1} \right]} \right| < \left| {P\left( {\left[ {0,1} \right]} \right)} \right| = \left| {2^{\left[ {0,1} \right]} } \right| \leqslant \left| {\mathbb{R}^{\left[ {0,1} \right]} } \right|.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1
    Hi,

    I'm actually still trying to solve this. Basically I know the result holds because of the theorems you gave, however I'm still trying to use a method similar to Cantor's Diagonalization argument and proof by contradiction to actually prove this next step:

    So to prove that all functions  f:[0,1] \to \mathbb{R}^{[0,1]} fail to be onto, I assume there exists a bijective function and then show that that leads to a contradiction. So, let g:[0,1] \to \mathbb{R}^{[0,1]} be a function so that it is bijective. Let g(x) = f_x for some x \in [0,1], and  f_x \in \mathbb{R}^{[0,1]} . Now to show that g fails to be onto I need to find a function in \mathbb{R}^{[0,1]} that is distinct from all f_x \in \mathbb{R}^{[0,1]} for each x \in [0,1]. Here is where I get stuck in the proof. The analog to finding a distinct function separate from all the previous  f_x \in \mathbb{R}^{[0,1]} in cantor's theorem was to create a set with elements that weren't in the image of the function assumed to be bijective. However I'm having trouble applying that same type of reasoning here.

    Any suggestions?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 7th 2011, 06:45 AM
  2. cardinality proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 2nd 2010, 03:34 AM
  3. Proof: Cardinality Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 13th 2010, 01:35 AM
  4. finite cardinality proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2008, 09:56 PM
  5. cardinality proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 19th 2008, 09:52 PM

Search Tags


/mathhelpforum @mathhelpforum