How is the set of functions from ${\{a,b\}}$ to $N$ countable?

Question

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.

Answer 1

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite.

You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\{a,b\}$ to $\mathbb{N}$ using the injection $\alpha$ below:

$\alpha : \mathbb{N}^{\{a, b\}} \rightarrow \mathbb{N} : f \mapsto 2^{f(a)}(2f(b)+1)$

Answer 2

Saad Balbiyad's answer is correct. This answer spells out some of the ideas in more detail.

A set is countably infinite if its elements can be paired up with natural numbers so that (a) no elements are paired up with the same number, (b) no element is paired with two numbers, (c) there are no numbers or elements left unpaired. In other words, a set is countably infinite if there is a one-to-one correspondence between the elements of the set and the elements of the natural numbers. In this case, we consider the size (cardinality) of the set to be the same as the size $|\mathbb{N}|$ of the natural numbers.

Consider the set of ordered pairs of natural numbers $(n,m)$. Your intuition that the number of elements in this set is $|\mathbb{N}|\times|\mathbb{N}|$ is correct, but the intuition that this quantity is greater than $|\mathbb{N}|$ is incorrect: we can pair the elements of the set of pairs of natural numbers with the natural numbers according to a one-to-one correspondence.

Think of the pairs as placed in a two-dimensional array extending indefinitely to the right and indefinitely down. At the upper left corner is $(0,0)$, with $(1,0)$ to its right, $(0,1)$ below it, and $(1,1)$ diagonally down and two the right. I think you can figure out how to arrange all of the pairs in this form. (It might be easier to draw the following on paper:) Now consider walking through this array so that no pairs are missed, and none are encountered twice. Start at $(0,0)$ and then go one element to right, then diagonally down-left until you get to the left edge, then down one, then diagonally up-right, then right one, then diagonally down-left, and so on. You are placing all of the pairs in a determinate order with none left out and none considered twice. You can therefore map each pair, as it is encountered, with the next natural number. Thus there is a one-to-one-correspondence between pairs of natural numbers and single natural numbers. These two sets have the same size. (Yes, it's weird that when $n$ is the size of the natural numbers, $n\times n = n$, but infinities are weird. That's life. Or math.)

The size of the real numbers is greater than the size of the natural numbers, however. The real numbers are uncountable; they can't be paired up with the natural numbers without leaving some out (nearly all of them). For more on this, search for "Cantor's diagonal argument". It's not very difficult to understand, it's beautiful, and it's mind-blowing, if you've never encountered the idea.