Let be a partially ordered set, which we call the ``alphabet''.
A ``string'' (or a ``word'') is a finite sequence of elements of
(written strung all together). Let
be the set of all strings made from elements of . For example, if
, then , , , and are all
elements of
, where denotes the empty string which
is of length zero.
If and are two strings in
, then let
be the concatenation of and . For
example, if is the string and is , then
is . Note that for any string ,
.
Define the relation on
by
if and only if there is a string
so that
.
Prove that is a partial order on
.