How is the set of functions from ${\{a,b\}}$ to $N$ countable? Assume a set of functions from ${\{a,b\}}$ to $N$ 
Where $N$ is the set of Natural numbers.
Let us assume that the size of $N$ is $n$.
i.e $|N|=n$
The first element $a$ have $n$ choices for mapping.
The second element $b$ have $n$ choices for mapping as well.
So the number of functions = $n.n$ = $n^2$.
which  is strictly greater than $n$ and hence the size of $N$.
So "Set of functions from ${\{a,b\}}$ to $N$", should not be countable. But it is. I am just a beginner in discrete maths, so this might be a stupid question for some. But please explain.
 A: One way to approach this naively is to look at the graph of any such $f$. It consists of  exactly two pairs: $(a,f(a))$ and $(b,f(b))$. And since $a$ and $b$ are fixed, and since for any $n,m\in \mathbb N$ there is an $f:\{a,b\}\to \mathbb N$ with $f(a)=n$ and $f(b)=m$, we see that we are dealing with two copies of $\mathbb N$. That is, $\left(\{(a,f(a)\}_{f:(a,b)\to \mathbb N}\right)\bigcup \left(\{(b,f(b)\}_{f:(a,b)\to \mathbb N}\right)\cong \mathbb N\times \mathbb N$. But this latter set is countable, because the map $(n,m)\mapsto 2^n\cdot 3^m$ injects into $\mathbb N.$
A: Many of your intuitions about finite sets do not carry over to infinite sets.  Yes, for a finite range there are more functions than the size of the range, but for an infinite range it is not true.  There are the same number of pairs of naturals as there are naturals.  Cantor's pairing function provides an explicit bijection.  You can search the site for pairing function and find many examples.
A: Consider the set $S = \mathbb{N} \times \mathbb{N}$, the cartesian product of $\mathbb{N}$ with itself.
It consists precisely of all pairs of natural numbers.
It should be easy to see that each function $f:\{a, b\} \to \mathbb{N}$ corresponds to a unique pair of natural numbers. For example, you can identify the function $f$ with the pair $(f(a), f(b)) \in \mathbb{N} \times \mathbb{N}$.  
The above agrees with the cardinality that you had obtained, namely, $n^2$.
However, note that $n$ is not a non-negative integer anymore. (As opposed to the case when you have finite sets.)  
Thus, the inequality $n^2 > n$ need not hold. In fact, one would first need to define a way in which one can make sense of something like $n^2$ or $n\cdot n$.
It seems reasonable to imagine that $n^2$ could be the "size" of $\mathbb{N} \times \mathbb{N}$.  
Let us now show that $n^2$ does indeed equal $n.$
Of course, one must again make sense of what it means for two "infinite numbers" to be equal. It is certainly not the case $\mathbb{N}\times\mathbb{N} = \mathbb{N}$.
However, if I can show that there's a bijection between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$, then it seems reasonable to assert that $n^2 = n$.  
I now illustrate one such bijection. Note that I shall assume $\mathbb{N}$ to mean the set of positive integers, that is, $\{1, 2, \ldots\}$.  
Define the function $\phi:\mathbb{N}\times\mathbb{N} \to \mathbb{N}$ as $\phi((a, b)) = 2^{a-1}(2b-1)$.
The fact that this is a bijection will follow from basic properties of natural numbers such as their unique factorisation.

Thus, what one can see is that statements that were true for finite sets need not hold for infinite sets.
One other such example could be the following:
If $S$ is finite, then $S$ can never have the same "size" (cardinality) as any of its proper subsets.
However, this is not true for infinite sets. It is very well possible for an infinite set to have the same "size" as one of its proper subsets.
