Prove that .
Attempted Solution:
To prove this inequality I need to show there exists a 1-1 function . And that all functions cannot be ONTO.
I'm having trouble conceptualizing a 1-1 function that maps from . 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 . A simple function in that I'm thinking of is just a straight line, so where b acts like the y-intercept. So my idea for a 1-1 mapping from , would take inputs from [0,1] and map them to various parallel lines, with different values for b. So basically . 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 cannot be ONTO. And I can't think of a way to start making progress on this part.
Thanks in advance for the help.
Hmm, does seem to me to be true. Because is a valid function that could map from . However I'm not sure how I'm supposed to use this piece of info. Is it the fact that, with being true, it tells us that the function that was defined, namely fails to be onto as it never maps to ?
Ah I see. Quick question though, I thought the idea was to show that every function possible from 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.
The textbook says for this statement: " " 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 I was first showing there existed a 1-1 mapping from to . And the second part of my proof requires me to show that every possible function from to fails to be onto, which is the step I'm stuck on at the moment.
Here is the way I present this material; it may not conform to your material.
For any set , . (Cantor’s theorem)
The cardinality of any set is less that the cardinality of its power set.
For any set , .
Where .
This sequence of theorems proves your result.
Note: .
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 fail to be onto, I assume there exists a bijective function and then show that that leads to a contradiction. So, let be a function so that it is bijective. Let for some and . Now to show that g fails to be onto I need to find a function in that is distinct from all for each . Here is where I get stuck in the proof. The analog to finding a distinct function separate from all the previous 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?