Recursive structure of MOS scales: Difference between revisions

Inthar (talk | contribs)
Inthar (talk | contribs)
Line 413: Line 413:
# w₂(L, s) = the first K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) (which must be longer than w₁(L, s), since W₂ had more λ's than W₁)
# w₂(L, s) = the first K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) (which must be longer than w₁(L, s), since W₂ had more λ's than W₁)
# w₃(L, s) = the last K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s)
# w₃(L, s) = the last K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s)
Note that the latter two words have at most k s's.


If w₂ contains fewer complete chunks (<L...Ls preceded by where < is the left chunk boundary) or at least 2 more than w₃, we are done, since they must automatically have different numbers of s's. Hence it suffices to consider the following two cases, each split into subcases:
If w₂ contains fewer complete chunks (<L...Ls preceded by where < is the left chunk boundary) or at least 2 more than w₃, we are done, since they must automatically have different numbers of s's. Hence it suffices to consider the following two cases, each split into subcases:
Line 421: Line 422:


Case 1.1:
Case 1.1:
  w2: <L ... sXL ... sXL ... sXL ... sXL ...]
  w2: <L ... sXL ... sXL ... sXL ... sXL ...L] (complete chunks followed by one or more L's)
  w3:        <L ... sXL ... sXL ... sXL ... s>
  w3:        <L ... sXL ... sXL ... sXL ... s> (complete chunks only)


This implies that the last chunk is bigger than the first one, a contradiction because w₂ begins in λ.  
This implies that the last chunk is bigger than the first one, a contradiction because w₂ begins in λ.  
Line 428: Line 429:
Case 1.2:
Case 1.2:
  w1:  s[something with k s's]
  w1:  s[something with k s's]
  w2: <L ... sXL ... sXL ... sXL ... s>
  w2: <L ... sXL ... sXL ... sXL ... s> (complete chunks only)
  w3:        <L ... sXL ... sXL ... sXL ... s>
  w3:        <L ... sXL ... sXL ... sXL ... s> (complete chunks only)


Truncate the strings as follows, to get three distinct K-steps in w:
Truncate the strings as follows, to get three distinct K-steps in w:
Line 440: Line 441:


Case 1.3:
Case 1.3:
  w2: <L ... sXL ... sXL ... sXL ... sXL ...]
  w2: <L ... sXL ... sXL ... sXL ... sXL ...L] (complete chunks followed by one or more L's)
  w3:  [... sXL ... sXL ... sXL ... sXL ... s>
  w3:  [... sXL ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks)


or
or


Case 1.4:
Case 1.4:
  w2: <L ... sXL ... sXL ... sXL ... sX]
  w2: <L ... sXL ... sXL ... sXL ... s> (complete chunks only)
  w3:  [... sXL ... sXL ... sXL ... sXL ... s>
  w3:  [... sXL ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks)


(both 1.3 and 1.4 imply w₃ has one more s).
(both 1.3 and 1.4 imply w₃ has one more s).
Line 456: Line 457:


Case 2.1:
Case 2.1:
  w2: <L ... sXL ... sXL ... sXL ... sXL ... s>
  w2: <L ... sXL ... sXL ... sXL ... sXL ... s> (complete chunks only)
  w3:                <L ... sXL ... sXL ... sXL ... s>
  w3:                <L ... sXL ... sXL ... sXL ... s> (complete chunks only)
⇒ w₂ has more s's.
⇒ w₂ has k s's and w₃ has (k-1) s's, contradicting the assumption that w is a mos.


Case 2.2:
Case 2.2:
  w2: <L ... sXL ... sXL ... sXL ... sXL ... s>
  w2: <L ... sXL ... sXL ... sXL ... sXL ... s> (complete chunks only)
  w3:              [sXL ... sXL ... sXL ... sXL ... s>
  w3:              [sXL ... sXL ... sXL ... sXL ... s> (s followed by complete chunks)
⇒ do the same trick as in Case 1.2
⇒ do the same trick as in Case 1.2


Case 2.3:
Case 2.3:
  w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...]
  w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...] (complete chunks followed by one or more L's)
  w3:          [ ... sXL ... sXL ... sXL ... sXL ... s>
  w3:          [ ... sXL ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks)


Case 2.4:
Case 2.4:
  w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...]
  w2: <L ... sXL ... sXL ... sXL ... sXL ... sXL ...] (complete chunks followed by one or more L's)
  w3:                <L ... sXL ... sXL ... sXL ... s>
  w3:                <L ... sXL ... sXL ... sXL ... s> (one or more L's followed by an s, followed by complete chunks)


Both 2.3 and 2.4 are contradictions since the first chunk is λ so has to be at least as big as the last one.
Both 2.3 and 2.4 are contradictions since the first chunk is λ so has to be at least as big as the last one.