description/proof of that for infinite set, if there is injection from set into natural numbers set, there is bijection from natural numbers set onto set
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of injection.
- The reader knows a definition of surjection.
- The reader admits the proposition that for any infinite set, if there is a surjection from the natural numbers set onto the set, there is a bijection from the natural numbers set onto the set.
Target Context
- The reader will have a description and a proof of the proposition that for any infinite set, if there is any injection from the set into the natural numbers set, there is a bijection from the natural numbers set onto the set.
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: Structured Description
Here is the rules of Structured Description.
Entities:
\(S\): \(\in \{\text{ the infinite sets }\}\)
//
Statements:
\(\exists f: S \to \mathbb{N} \in \{\text{ the injections }\}\)
\(\implies\)
\(\exists f'': \mathbb{N} \to S \in \{\text{ the bijections }\}\)
//
2: Note
So, \(S\) is countable.
3: Proof
Whole Strategy: Step 1: take the bijection, \(f^`: S \to f (S)\), and its inverse, \({f^`}^{-1}: f (S) \to S\); Step 2: take any \(s_0 \in S\) and the surjection, \(f': \mathbb{N} \to S, n \mapsto {f^`}^{-1} (n) \text{ when } n \in f (S); \mapsto s_0 \text{ otherwise }\); Step 3: apply the proposition that for any infinite set, if there is a surjection from the natural numbers set onto the set, there is a bijection from the natural numbers set onto the set.
Step 1:
The codomain restriction of \(f\), \(f^`: S \to f (S), s \mapsto f (s)\), is a bijection.
There is the inverse of \(f^`\), \({f^`}^{-1}: f (S) \to S\).
Step 2:
Let \(s_0 \in S\) be any, which exists, because \(S \neq \emptyset\).
Let us define \(f': \mathbb{N} \to S, n \mapsto {f^`}^{-1} (n) \text{ when } n \in f (S); \mapsto s_0 \text{ otherwise }\).
\(f'\) is a surjection, because for each \(s \in S\), \(f (s) \in f (S)\), so, \(f' (f (s)) = {f^`}^{-1} (f (s)) = {f^`}^{-1} (f^` (s)) = s\).
Step 3:
There is a bijection, \(f'': \mathbb{N} \to S\), by the proposition that for any infinite set, if there is a surjection from the natural numbers set onto the set, there is a bijection from the natural numbers set onto the set.
