Content deleted Content added
→Lexicographical ordering: swap 2 sentences to use 0,1-example also for non-wellfoundedness; indicate all non-cover relations by "..."; also show shortlex-order for 0,1-example to allow comparison |
→Lexicographical ordering: give a counter-example for well-ordering |
||
Line 282:
=== Lexicographical ordering ===
It is often useful to define an [[order theory|ordering]] on a set of strings. If the alphabet Σ has a [[total order]] (cf. [[alphabetical order]]) one can define a total order on Σ<sup>*</sup> called [[lexicographical order]]. The lexicographical order is [[total order|total]] if the alphabetical order is, but is not [[well-founded]] for any nontrivial alphabet, even if the alphabetical order is. For example, if Σ = {0, 1} and 0 < 1, then the lexicographical order on Σ<sup>*</sup> includes the relationships ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 1111 < ... < 11111 ... With respect to this ordering, e.g. the infinite set { 1, 01, 001, 0001, 00001, 000001, ... } has no minimal element.
See [[Shortlex]] for an alternative string ordering that preserves well-foundedness.
| |||