# What would be the explicit formula of a “dictionary” function / relation?

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

(1) a

(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".

• The lexicographic order can be defined on arbitrary partial orders; you don't need to map into the integers. – Patrick Stevens May 5 at 8:22

This is one way of defining lexical order on words. First you define an alphabet $$\Sigma$$ the set of all the letters you are dealing with. Then $$\Sigma^*$$ is the Kleene closure of that set. That is the set of all tuples (also called strings or words) made with elements from $$\Sigma$$ including "" which is the empty string.
If you have an ordering on on the letters in your alphabet $$\geq_\Sigma : \Sigma^2$$ then you can define a dictionary ordering this way $$\geq_{\Sigma^*} := \{ \langle x,y \rangle \in \langle \Sigma^*,\Sigma^* \rangle | y = "" \vee (h(x) \geq_\Sigma h(y) \wedge h(x) \neq h(y)) \vee (h(x) = h(y) \wedge t(x) \geq_{\Sigma^*} t(y) \}$$