Cardinality of the set of all functions

[ribbon]

Homework Statement

What is the cardinality of the set of all functions from N to {1,2}?

Homework Equations

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?

 

[pasmith]

Homework Statement

What is the cardinality of the set of all functions from N to {1,2}?

Homework Equations

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?

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\}$.

 

[ribbon]

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\}$.

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!

 

[haruspex]

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!

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.

 

[pasmith]

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)?

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.)