Proving M is the same language as L has two components:
s M s L
--- and ---
s L s M
We showed L implies M direction in the previous lecture.
Now for the trickier part, s M ==> s L.
This we can do by regular induction on s M, at least to get started.
We will show P(s) == s L. We show this for all s for which s M by rule
induction on the definition of M.
There are three cases, one for each inference rule defining s M.
The base case corresponds to rule M_E and is to show P(ε), i.e. ε L.
This is just rule L_E:
---- L_E
ε L
Likewise the case associated with M_N is not difficult.
We have the IH P(s) == s L, and must show P ( (s) ).
We can use N_N to show (s) N, and then we must show that N is a sublanguage of
L, which is true. Here is a proof using an inference rule tree:
s L
----- N_N ---- L_E
(s) N ε L
----------------
(s)ε L
Juxtaposition of (s) with ε is just (s), so we have shown (s) L as required.
The third (and most interesting) case corresponds to M_J.
IH1: P(s_1) == s_1 L.
IH2: P(s_2) == s_2 L.
We must show that s_1 s_2 L.
We don't have a rule for this. We need to show that append (or juxtapose) of
two lists is a list. Let's show that by induction as a lemma.
Lemma 1: ∀s_1. s_1 L ==> (∀s_2. s_2 L ==> s_1 s_2 L).
We will prove this by rule induction on the assumption s_1 L,
using Q(s) == (∀t. t L ==> s t L). We've used a different name t here to
avoid needing to do some α-renaming in the near future.
The base case for *this* induction corresponds to L_E:
Show Q(ε) == (∀t. t L ==> (ε t) L).
This is pretty clear. The juxtaposition ε t == t.
So, we fix t, assume t L, and conclude (ε t) L as that is equivalent to
the assumption we just made. This shows the base case.
The inductive case for the Lemma 1 induction corresponds to L_J:
We assume our IH: Q(s_2). We also assume A: s1 N.
We must show Q (s_1 s_2), i.e.
(∀t. t L ==> ((s_1 s_2) t) L).
To prove this, we fix t, and assume A2: t L. We must show ((s_1 s_2) t) L.
Juxtaposition is associative, so we can equivalently show (s_1 (s_2 t)) L.
We also have our IH Q(s_2) == (∀t. t L ==> (s_2 t) L).
Here is our required proof:
--- A2
t L
---- A ---------- IH
s1 N (s_2 t) L
---------------------- L_J
(s_1 (s_2 t)) L
This establishes Q(s_1 s_2) and completes the proof by induction of Lemma 1.
We can now apply Lemma 1 to complete the juxtaposition case of our original
proof. Recall, in the juxtaposition case, we had:
IH1: P(s_1) == s_1 L.
IH2: P(s_2) == s_2 L.
The obligation to show that s_1 s_2 L.
We now have Lemma 1: ∀s_1. s_1 L ==> (∀s_2. s_2 L ==> s_1 s_2 L).
This lemma exactly solves our problem (using IH1 and IH2 as well), which
completes our proof by induction.
We have now covered the implication in both direction, and can conclude that M
and L are equal.
