# Cardinality of the set of all functions

1. Aug 4, 2013

### ribbon

1. The problem statement, all variables and given/known data
What is the cardinality of the set of all functions from N to {1,2}?

2. Relevant equations

3. The attempt at a solution
I know the cardinality of the set of all functions coincides with the respective power set (I think) so 2^n where n is the size of the set. The cardinality of N is aleph-nought, and its power set, 2^aleph nought.

However what limitations does mapping to a finite (2 elements) set here expose us to?
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Aug 4, 2013

### pasmith

This would be one of those circumstances in which it is essential to use the formal definition of a function $F$ from $A$ to $B$ as being a subset of $A \times B$ with the property that for each $a \in A$ there is exactly one $b \in B$ such that $(a,b) \in F$.

Thus there are at most as many functions from $\mathbb{N}$ to $\{1,2\}$ as there are subsets of $\mathbb{N} \times \{1,2\}$.

Last edited: Aug 4, 2013
3. Aug 4, 2013

### ribbon

Interesting well I know the set N has 2^(aleph nought) subsets and the set S = {1, 2} has 2^2 subsets, so am I correct when I say:

2^(aleph nought) x 2^2 = 2^(aleph nought + 2)?

Also I am trying to more so understand your explanation of the equivalence of a function from A to B to a subset AxB? Is there anyway you could dumb that down a little more for me? Much appreciated!

4. Aug 4, 2013

### haruspex

Any function f:A→B defines a subset S of AxB consisting of the pairs {(a, f(a)):a in A}. S has the property that given a in A there exists a unique (a, b) in S.
Conversely, any subset of AxB with this property defines a function A→B, and two different such sets will define two different functions.

5. Aug 6, 2013

### pasmith

All one can say is that the number of such functions is at most the cardinality of $2^{\mathbb{N} \times \{1,2\}}$, which is uncountable by the diagonalization argument. But that is consistent with the possibility that the collection of those subsets of $\mathbb{N} \times \{1,2\}$ which satisfy the condition to be a function is countable.

But there exists a bijection $2^\mathbb{N} \to \{f : \mathbb{N} \to \{1,2\}\}$, so the number of such functions is exactly the cardinality of $2^{\mathbb{N}}$. (To find the bijection, consider the subset of $\mathbb{N}$ on which a function takes the value 1.)