Set Theory: Cardinality of functions on a set have higher cardinality than the set I'm independently working my way through Elements of the theory of functions and functional analysis by Kolmogorov and Fomin. At the moment, I'm stuck on the following exercise (on page 11), the question states:
Prove that the set of all numerical functions defined on a set M has a greater cardinal number than the cardinal number of the set M. Hint: Use the fact that the set of all characteristic functions (i.e. functions assuming only the values of 0 and 1) defined on M is equivalent to the set of all subsets of M.
Defining $f: M \rightarrow \{0,1\}$, I've figured out that $\prod_{k} (1-f_{\cap_{k} M_k}) = 1-f_{\cup_{k} M_k}=f_{M-\cup_{k}M_k}$ where $M_k$ are subsets of M. 
At this point, I'm not sure what I've proved is helpful at all and if it is, how I should connect the dots between what I've proved and what needs to be proved. My idea is that I need to first prove that the set of all characteristic functions has the same cardinality as the power set of $M$ then realise the connection between numerical functions and the characteristic functions. Both of these would then imply the result. Any ideas on how to go about this? Note that I'm quite new to set theory and am aiming to learn some real analysis for an undergraduate class.
 A: The goal is to find a bijection between charasteristic functions and subsets of $M$.
Try to map each function to a subset and each subset to a function in a natural and bijective way. In other words, how can you see a characteristic function as a description of a subset of $M$? (you probably saw it already in different contexts)
A: The question points out that there is a natural bijection $\mathcal{P}(M)\rightarrow\{0,1\}^M$ given by $A\mapsto\mathbf{1}_A$. Here $\mathcal{P}(M)$ is the power set of $M$, $X^M$ is the set of functions $M\rightarrow X$ and $\mathbf{1}_A$ is the indicator/characteristic function of $A$. So it suffices to show that the cardinality of $\mathcal{P}(M)$ is strictly larger than that of $M$. Since clearly $M\rightarrow\mathcal{P}(M)\,:\,x\mapsto\{x\}$ is injective, it suffices to show there is no bijection $\Phi\,:\,M\rightarrow\mathcal{P}(M)$. Suppose such a bijection $\Phi$ exists. Define
$$A:=\{x\in M\,:\,x\notin\Phi(x)\}\in\mathcal{P}(M).$$
By assumption, $A=\Phi(x)$ for some $x\in M$. If $x\in A$, then by definition of $A$ $x\notin\Phi(x)=A$, a contradiction. Thus $x\notin A=\Phi(x)$, so by definition $x\in A$, again a contradiction. Thus no such bijection can exist.
