Quote:
Originally Posted by Polaris84 But I thought that all finite sets are countable? with 3 elements and 6 subsets, the pigeon hole principal applies, and the elements must repeat.

I'm suggesting that you walk through the proof step by step for a 3 element set with an 8 element power set. Write down the domain and range, pick some functions f, define the set X, show that X can't be hit by anything.
The pigeonhole principle doesn't apply at all here, you're mapping the smaller set to the larger set.