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