# Math Help - Cardinality Inequality Proof

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.

2. Originally Posted by utopiaNow
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?

3. Originally Posted by Plato
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$?

4. Originally Posted by utopiaNow
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.

5. 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.

6. Originally Posted by utopiaNow
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?

7. Originally Posted by Plato
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.

8. 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|$.

9. 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?