Prove that .
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.
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.
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 , .
This sequence of theorems proves your result.
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.