Content deleted Content added
No edit summary |
proof that a*b has no least element |
||
Line 22:
:The least element of a*b is b. The [[lexicographical order]] on Σ* is indeed a [[well-ordering]]. --[[User:Pexatus|Pexatus]] 00:22, 19 March 2006 (UTC)
::No. There is no least element of a*b if you use the alphabetical ordering <math>a < b</math>. Assume there is some least element ''m''; this means that <math>m = a^{k}b</math> for some non-negative integer ''k''. Note that <math>n = a^{k+1}b</math> is also in a*b. ''n'' agrees ''m'' in ''k'' positions, but the ''k + 1''th position of ''n'' is less than the ''k + 1''th position of ''m'', so <math>n < m</math>, which contradicts the assumption that there exists a least element of a*b. Therefore, there is no least element of a*b. --[[User:Bkkbrad|Bkkbrad]] 16:28, 13 September 2006 (UTC)
== strings, not characters ==
| |||