A coding of the countable linear orderings (Q803179): Difference between revisions

Let \(\triangleleft\) be a (strict) linear ordering on the set \({\mathbb{N}}\) of the non-negative integers and \(<\) the usual strict linear order on \({\mathbb{N}}\). Then the code of \(\triangleleft\) is defined as the mapping f: \({\mathbb{N}}\to {\mathbb{N}}\) which for \(n\in {\mathbb{N}}\) is defined by: f(n) is the cardinality of the set \(\{k<n|\) \(k\triangleleft n\}\). Clearly, a function f: \({\mathbb{N}}\to {\mathbb{N}}\) is a code for some linear ordering of \({\mathbb{N}}\) iff f satisfies f(n)\(\leq n\) for all \(n\in {\mathbb{N}}\). Then the author proves: A code f: \({\mathbb{N}}\to {\mathbb{N}}\) is a code of a well- ordering of \({\mathbb{N}}\) iff there is no strictly increasing function h such that n-f(h(n)) tends to infinity with n.