A description/proof of that from natural number to countable set functions set is countable
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of set.
- The reader knows a definition of function.
- The reader knows a definition of countable set.
- The reader admits the proposition that the finite product of any countable sets is countable.
Target Context
- The reader will have a description and a proof of the proposition that for any countable set and any natural number, the set of all the functions from the natural number to the set is countable.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Description
For any countable set, \(S\), and any natural number, \(n\), the set of all the functions from \(n\) to \(S\), \({}^nS\), is countable.
2: Proof
For any \(f \in {}^nS\), \(f: n \rightarrow S\) where \(n = \{0, 1, . . ., n - 1\}\) by the set theory. There is an injection, \(g: {}^nS \rightarrow S \times S \times . . . \times S, f \mapsto \langle f (0), f (1), . . ., f (n - 1)\rangle\). So, \(card {}^nS \leq card (S \times S \times . . . \times S)\), but \(S \times S \times . . . \times S\) is countable by the proposition that the finite product of any countable sets is countable, so, \({}^nS\) is countable.
