Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to prove "There is no set to which every function belongs." Can I approach it as follows?

Attempt No. 1: Let $$F: A\rightarrow B$$ Since $$F\subset A\times B,$$ it follows that $$F\in \mathcal{P}(A\times B).$$ Now, let $$\mathcal{P}(A\times B)$$ be the set of all functions from A into B. Since $$\mathcal{P}(A\times B)\subseteq \mathcal{PP}(A\times B),$$ it follows that $$\mathcal{PP}(A\times B)$$ is also a set of all functions from A into B. Therefore $$\mathcal{P}(A\times B)=\mathcal{PP}(A\times B).$$

Attempt No. 2 is to approach it by the concept of Russel Paradox. Then I must build a set of all functions that are not in itself, but, honestly, I have not a clue of what constitute a function that is not in itself.

share|improve this question
2  
Maybe this is too naive, but isn't the subset of all identity functions in bijection with the class of all sets? –  t.b. Jun 4 '11 at 18:45
    
@Theo: That seems true (I'm naive also), but what do you do next? Does this fact, that there's a bijection to a "smaller" set, help in some way? –  ShreevatsaR Jun 4 '11 at 19:27
1  
@ShreevatsaR: I'd say: If the collection of all functions were a set then the subcollection of all identity functions would be a set as well, but it isn't by Russell. –  t.b. Jun 4 '11 at 19:47
    
@Theo: Ah, thanks. –  ShreevatsaR Jun 4 '11 at 19:48
add comment

2 Answers

Here's is a Russell's Paradox type solution:

Suppose there exists a set $\mathcal{F}$ of all functions. Consider the following subset of $\mathcal{F}$: $$ \mathcal{S} \;=\; \{f\in\mathcal{F} \mid f\text{ is not an element of the domain of }f\}. $$ Clearly $\mathcal{S}$ is nonempty, so there exists at least one function $f$ with domain $\mathcal{S}$ (e.g. the constant zero function). Is $f$ an element of $\mathcal{S}$?

share|improve this answer
add comment

Assume the class of all functions, $\mathcal F$, is a set, then it has a rank, i.e. some $\alpha$ such that the class is an element of $V_\alpha$ (and $\alpha$ is the minimal one), this is not true, as the identity function from $V_\alpha$ to itself is in the class $\mathcal F$ so it must have appeared in a higher rank, contradicting the assumption about $\alpha$.

To finish the proof we just observe that a class is also a set if and only if it has a rank, therefore $\mathcal F$ is a proper class.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.