description/proof of that infinite sequence can be faithfully represented by sequence from natural numbers set
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of sequence.
- The reader knows a definition of well-ordered set.
Target Context
- The reader will have a description and a proof of the proposition that any infinite sequence can be faithfully represented by the sequence from the natural numbers 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 sequences }\}\), with \(dom s = J\) such that \(J \in \{\text{ the infinite sets }\}\)
//
Statements:
\(\exists f: \mathbb{N} \to J \{\text{ the order preserving bijections }\} (s \circ f \in \{\text{ the sequences }\}, \text{ from which } s \text{ can be restored })\)
//
2: Note
The motivation for this proposition is to justify our just using a sequence from \(\mathbb{N}\) for any argument for any general sequence: for an argument for any general sequence, we often use just a sequence from \(\mathbb{N}\) instead of a sequence from \(J\), but for any sequence from \(J\), \(s\), \(s \circ f\) is a sequence from \(\mathbb{N}\), and if a claim holds for \(s \circ f\), we can transfer the claim to \(s = s \circ f \circ f^{-1}\).
For example, \(s\) converges to a point if and only if \(s \circ f\) converges to the same point, because if \(s\) converges to \(p\), there is an \(N \in J\) such that for each \(j \in J\) such that \(N \lt j\), \(dist (p, s (j)) \lt \epsilon\), and then, there is \(f^{-1} (N) \in \mathbb{N}\) such that for each \(j \in \mathbb{N}\) such that \(f^{-1} (N) \lt j\), \(dist (p, s \circ f (j)) \lt \epsilon\), because \(N \lt f (j)\); if \(s \circ f\) converges to \(p\), there is an \(N \in \mathbb{N}\) such that for each \(j \in \mathbb{N}\) such that \(N \lt j\), \(dist (p, s \circ f (j)) \lt \epsilon\), and then, there is \(f (N) \in J\) such that for each \(j \in J\) such that \(f (N) \lt j\), \(dist (p, s (j)) \lt \epsilon\), because \(s (j) = s \circ f \circ f^{-1} (j)\) and \(N \lt f^{-1} (j)\).
Note that as \(f\) is order-preserving, \(f^{-1}\) is order-preserving, because for each \(j, l \in J\) such that \(j \lt l\), if \(f^{-1} (l) \lt f^{-1} (j)\), \(f (f^{-1} (l)) \lt f (f^{-1} (j))\), which would mean that \(l \lt j\), a contradiction.
3: Proof
Whole Strategy: Step 1: construct \(f\); Step 2: see that \(f\) is an order-preserving bijection; Step 3: see that \(s\) can be restored from \(s \circ f\).
Step 1:
\(J \subseteq \mathbb{N}\) has the smallest element, \(j_0\), because \(\mathbb{N}\) is a well-ordered set, which is a well-known fact.
\(J \setminus \{j_0\}\) has the smallest element, \(j_1\), likewise.
In general, \(J \setminus \{j_0, ..., j_{n - 1}\}\) has the smallest element, \(j_n\), likewise.
So, iteratively, let us define the map, \(f: \mathbb{N} \to J, l \mapsto j_l\).
Step 2:
Let us see that \(f\) is a bijection.
\(f\) is an injection, because for each \(j, l \in \mathbb{N}\) such that \(j \lt l\), \(f (l)\) is chosen from \(J \setminus \{f (0), ..., f (l - 1)\}\).
\(f\) is a surjection, because for each \(j \in J\), \(j\) is the \(l\)-th smallest element of \(J\) for an \(l \in \mathbb{N} \setminus \{0\}\), and \(j = f (l - 1)\).
So, \(f\) is a bijection.
\(f\) is order-preserving, because for each \(j, l \in \mathbb{N}\) such that \(j \lt l\), \(f (j)\) and \(f (l)\) are the \(j + 1\)-th smallest element and the \(l + 1\)-th smallest element of \(J\), so, \(f (j) \lt f (l)\).
Step 3:
As \(f\) is a bijection, \(s = s \circ f \circ f^{-1}\), so, \(s\) can be restored from \(s \circ f\).
