What would be the explicit formula of a " dictionary" function / relation that would put in the "dictionary order" all the words of a natural language ( having an alphabet)?
I think that one of the main difficulties here is that a lexicographic order relation only "works" with n-tuples having the same size. So, apparently, we need as many ordering relations as possible sizes for a word.
My reflexion does not go further than this:
(1) We need W the set of all words
(2) We need a function "Letter" having as domain W and associating each word with an n-tuple such that if the nth letter of a word is the mth letter of the alphabet, then the nth element of the n-tuple is m
For example: Letter ( cat) = (3,1,20)
(3) Then an equivalence relation classifying n-tuples according to their length
(4) Then a relation that, in each equivalence class, would put in order lexicographically the word-representing n-tuples.
In the equivalence class of (3,1,20) this relation would be :
(a,b,c ) < ( d,e,f) iff
(2) or, if a=d, b
(3) or, if b=e , c < f .
(6) Finally we would need the inverse of the function L to recover words from n-tuples.
This suggestion is clearly is far from being satisfying.
Remark.- I add the tag " computer science" for maybe the problem can be solved using a kind of "algorithm".