Warning: this is an htmlized version!
The original is across this link,
and the conversion rules are here.
% (find-angg "LATEX/2008induction.tex")
% http://angg.twu.net/LATEX/2008induction.tex.html
% http://angg.twu.net/LATEX/2008induction.pdf
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2008induction.tex && latex    2008induction.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2008induction.tex && pdflatex 2008induction.tex"))
% (eev "cd ~/LATEX/ && Scp 2008induction.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (find-dvipage "~/LATEX/2008induction.dvi")
% (find-pspage  "~/LATEX/2008induction.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -P pk -o 2008induction.ps 2008induction.dvi")
% (find-pspage  "~/LATEX/2008induction.ps")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage  "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2008induction.pdf" (ee-twupfile "LATEX/2008induction.pdf") 'over)
% (ee-cp "~/LATEX/2008induction.pdf" (ee-twusfile "LATEX/2008induction.pdf") 'over)


% «.e-mail»			(to "e-mail")
% «.incr-and-decr»		(to "incr-and-decr")
% «.types»			(to "types")
% «.definitions»		(to "definitions")
% «.cases-0-1-9»		(to "cases-0-1-9")
% «.cases-0-1-9-2»		(to "cases-0-1-9-2")
% «.lemmas»			(to "lemmas")
% «.proofs-5-to-11»		(to "proofs-5-to-11")
% «.proofs-12-to-15ppp»		(to "proofs-12-to-15ppp")
% «.proofs-16-to-19»		(to "proofs-16-to-19")
% «.proofs-20-to-23»		(to "proofs-20-to-23")
% «.interval-lemmas»		(to "interval-lemmas")
% «.interval-induction»		(to "interval-induction")
% «.interval-induction-2»	(to "interval-induction-2")
% «.interval-induction-3»	(to "interval-induction-3")
% «.intervals»			(to "intervals")


\documentclass[oneside]{book}
\usepackage[latin1]{inputenc}
\usepackage{edrx08}       % (find-dn4ex "edrx08.sty")
%L process "edrx08.sty"  -- (find-dn4ex "edrx08.sty")
\input edrxheadfoot.tex   % (find-dn4ex "edrxheadfoot.tex")
\begin{document}

\input 2008induction.dnt

%*
% (eedn4-51-bounded)

Index of the slides:
\msk
% To update the list of slides uncomment this line:
\makelos{tmp.los}
% then rerun LaTeX on this file, and insert the contents of "tmp.los"
% below, by hand (i.e., with "insert-file"):
% (find-fline "tmp.los")
% (insert-file "tmp.los")
\tocline {E-mail} {2}
\tocline {Increasing and decreasing} {3}
\tocline {L1, L2, Types} {4}
\tocline {Definitions} {5}
\tocline {Cases 0, 1 and 9} {6}
\tocline {Cases 0, 1 and 9 (2)} {7}
\tocline {Lemmas} {8}
\tocline {Proofs (5 to 11)} {9}
\tocline {Proofs (12 to 15${}'''$)} {10}
\tocline {Proofs (16 to 19)} {11}
\tocline {Proofs (20 to 23)} {12}
\tocline {Interval lemmas} {13}
\tocline {Induction in intervals} {14}
\tocline {Induction in intervals (2)} {15}
\tocline {Intervals} {16}

% (defun a () (interactive) (insert "$\\begin{array}{lcl}\n \\end{array}\n$\n"))

\def\N{\mathbb{N}}
\def\Zer{\ensuremath{\mathsf{Zer}}}
\def\Inj{\ensuremath{\mathsf{Inj}}}
\def\Ind{\ensuremath{\mathsf{Ind}}}
\def\ang#1{\langle#1\rangle}
\def\Pts{\mathcal{P}}
\def\neto{\nearrow}
\def\neto{{\nearrow}}
\def\seto{\searrow}
\def\seto{{\searrow}}
\def\notS{\begin{picture}(0,0)\put(0,1){$\not{}$}\end{picture}S}
\def\epito{\twoheadrightarrow}
\def\nepito{\not\twoheadrightarrow}
\def\isdisjoint{\text{ is disjoint}}
\def\different{\text{ different}}
\def\covers{\text{ covers }}


\newpage
% --------------------
% «e-mail»  (to ".e-mail")
% (s "E-mail" "e-mail")
\myslide {E-mail} {e-mail}

{\myttchars
\footnotesize
\begin{verbatim}
Tenho boas notícias sim... vou dar um resumo.

O Petrúcio tava tentando fazer todas as provas numa linguagem - que eu
chamo de "L1" - que não tem conjuntos, interseções, uniões, etc. Eu
tava usando uma linguagem - "L2" - que permite tudo isso e algumas
coisas mais, e que pra mim era óbvio que tudo que eu fizesse em L2
podia ser traduzido para L1...

Bom, eu formalizei essa L2 - não totalmente ainda, mas acho que
suficiente bem - e a tradução dela para L1, e tenho um monte de lemas
interessantes cujas provas em L2 são curtíssimas e bem intuitivas... e
isto inclui vários pedaços da demonstração de que aquela construção do
Petrúcio prova Ind |- Zer \/ Inj.

Essa outra abordagem daqui me pareceu ainda mais natural. Como sempre,
tudo fica mais fácil com um exemplo ("dever de casa pro leitor:
generalize" - só que como eu não tou dando detalhes suficientes esse
dever de casa não é pra ser levado a sério). Imaginem que o nosso N é
isso aqui:

  0->1->2->3->4->5->6->4

eu encontrei um modo de caracterizar os elementos do loop (i.e., {4,
5, 6}) e o primeiro cara de fora do loop que aponta pro loop (o 3),
usando L2 - e portanto, com a tradução, tenho um modo de fazer tudo
isso em L1... daí dá pra provar que o 4 tem dois antecessores. Ainda
não chequei todos os detalhes do que eu vou dizer agora, mas lá vai...

Eu chamo de "L" a construção que me dá esse loop, de "[a,\infty)" a
construção que me dá todos os sucessores de a, e de "\notS A" a
construção que me retorna todos os elementos de A cujo sucessor não
está em A. Então nesse caso

  L(0) = {4, 5, 6},

  [0,\infty) \ L(0) = {1, 2, 3},

  \notS([0,\infty) \ L(0)) = {3},

e o sucessor do 3 é o único cara de [0,\infty) que pode ter mais de um
predecessor em [0,\infty) - um dentro do loop e um fora. No caso em
que eu tenho um w com w->0 (por ~Zer) e vale Inj, então todo mundo
pertence a [0,\infty), inclusive o w; aí eu vou ter L(0) = todo mundo,
[0,\infty) \ L(0) = vazio, e não vou poder ter um cara com dois
predecessores... ou seja, Inj (o "Inj de verdade", sobre o N todo),
vai valer.

Depois vou escrever os detalhes direito.

  [[]]s, té quinta,
    E.
\end{verbatim}
}

\newpage
% --------------------
% «incr-and-decr»  (to ".incr-and-decr")
% (s "Increasing and decreasing" "incr-and-decr")
\myslide {Increasing and decreasing} {incr-and-decr}

We will say that a predicate $P$ on $N$ is ``non-decreasing'' when
$x.Px⊃PSx$, and ``non-increasing'' when $x.PSx⊃Px$; obviously, the
idea is that the characteristic function of a predicate on $N$ may be
non-decreasing or non-increasing (for each arrow $x \to Sx$), and we
are making these terms apply to predicates too.

Notation:
%
$$\begin{array}{rclll}
  \neto P & := & x.Px⊃PSx && \text{(non-decreasing)}, \\
  \seto P & := & x.PSx⊃Px && \text{(non-increasing)}. \\
  \end{array}
$$

Note that $\neto P \Bij \seto (P)$.

We can define the set of successors of $a$ and the set of predecessors
of $b$ as:
%
$$\begin{array}{rclll}
  x   [a,) & := & A. Aa ∧ \neto A ⊃ Ax \\
  x  (-,b] & := & B. Bb ∧ \seto A ⊃ Bx \\
  \end{array}
$$

It is easy to see that $\neto([a,))$ and that $\seto((-,b])$.

Lemma: $b[a,) \Bij a(-,b]$.

Proof:
%
$$\begin{array}{rcl}
  b[a,)  & \equiv & A. Aa ∧ \neto A ⊃ Ab \\
  a(-,b] & \equiv & B. Bb ∧ \seto A ⊃ Ba \\
           & \equiv & A. Ab ∧ \neto A ⊃ Aa \\
           & \equiv & A. Aa ∧ \neto A ⊃ Ab. \\
  \end{array}
$$

Now let's define the ``closed interval'' $[a,b]$. This will be like
$[a,)$, except that the characteristic function will be allowed to
decrease at the arrow $b \to Sb$; when $b \notin [a,)$ we will have
$[a,b]=[a,)$.
%
$$\begin{array}{rclll}
  x   [a,b] & := & A. Aa ∧ (x \neq b.Px⊃PSx) ⊃ Ax \\
  \end{array}
$$

Lemma: if $Sb \in [0,b]$ then $[0,b]=[0,)$.

Proof: straightforward (look at the arrow $b \to Sb$).

Lemma: if $x[a,b]$ and $Sx \notin [a,b]$ then $x=b$.

Proof: straightforward.

% \msk
% 
% Now suppose that $\ang{N, 0, S}$ is a DP-structure in which $\Ind$
% holds. $\Ind$ means that $N = [0,)$ (i.e., all elements of $N$ are
% successors of 0).
% 
% Definition: a wabc-structure is a DP-structure with four extra
% constants, $w, a, b, c$, in which $\Ind$ holds, and where $Sw=0$ and
% $Sa=Sb=c$. Note that $\Ind$ implies that $w,a,b,c \in [0,)$.
% 
% In a wabc-structure we have:
% %
% $$\begin{array}{c}
%   {} [0,) = [0,w] = (-,w] = (-,0], \\
%   {} [0,a]\{c\} = [0,c] = [0,b]\{c\} \\
%   \end{array}
% $$
% 
% {\it (oops, the last line is wrong...)}
% 
% (Note that a closed interval $[0,x]$ in a wabc-structure either is the
% whole $N$ or has a ``last element'' whose successor is not in the
% interval... and that element is necessarily $x$.)

\newpage
% --------------------
% «types»  (to ".types")
% (s "L1, L2, Types" "types")
\myslide {L1, L2, Types} {types}

\large

Conventions:

$\begin{array}{lcl}
  x,y &:& N \\
  P,Q &:&  \\
  A,B         &:& \Pts(N)       \text{\;\;(i.e., $N \to $)} \\
  \calA,\calB &:& \Pts(\Pts(N)) \text{\;\;(i.e., $(N \to ) \to $)} \\
 \end{array}
$

L1:

$\begin{array}{lcl}
  x,0,Sx             &:& N \\
  ,,P,P∧Q,P⊃Q,P∨Q &:&  \\
  Ax, x=y            &:&  \\ 
  x.P, x.P         &:&  \\
  A.P, A.P         &:&  \\
 \end{array}
$

L1'':

$\begin{array}{lcl}
  x \in N.P, x\in N.P              &:&  \\
  A \subseteq N.P, A \subseteq N.P &:&  \\
 \end{array}
$

L2:

$\begin{array}{lcl}
  \emp, N, AB, AB, A \bsl B              &:& \Pts(N) \\
  \{a\}, \{a,b\}, \ldots                   &:& \Pts(N) \\
  \emp, \Pts(A), \calA\calB, \calA\calB, \calA\bsl\calB &:& \Pts(\Pts(N)) \\
  \sst{aN}{P}, \bigcap\calA, \bigcup\calB                &:& \Pts(N) \\
  A \subseteq N.P, A \subseteq N.P       &:&  \\
  \sst{A\subseteq N}{P}                    &:& \Pts(\Pts(N)) \\
  x  A                                    &:&  \\
  A  \calA                                &:&  \\
 \end{array}
$

Extras:

$\begin{array}{lcl}
 [a,), \, (-,b], \, [a,b]   &:& \Pts(N) \\
 \neto A, \seto A             &:&        \\
 \notS A                      &:& \Pts(A) \\
 La, a \to b, a \epito b,     &:&        \\
 a \le b, a < b, a \sim b     &:&        \\
 L^9a, L'a, L^a              &:& \Pts(N) \\
 \Ind, \Inj, \Zer             &:&        \\
 \end{array}
$

\newpage
% --------------------
% «definitions»  (to ".definitions")
% (s "Definitions" "definitions")
\myslide {Definitions} {definitions}

Definitions:

$\begin{array}{lcl}
 aA           &:=& Aa      \\
 A\calA       &:=& \calA A \\
 \sst{x}{P}    &:=& xN.P  \\
 N             &:=& xN.  \\
 \emp          &:=& xN.  \\
 \sof{a,b}     &:=& \sst{x}{x=a∨x=b} \\
 AB           &:=& \sst{x}{xA ∧ xB} \\
 AB           &:=& \sst{x}{xA ∨ xB} \\
 A \bsl B      &:=& \sst{x}{xA ∧ xB} \\
 \sst{A}{P}    &:=& A.P  \\
 \bigcup\calA  &:=& \sst{x}{A\calA.xA} \\
 \bigcap\calA  &:=& \sst{x}{A\calA.xA} \\
 \neto A       &:=& x.xA⊃SxA \\
 \seto A       &:=& x.SxA⊃xA \\
 {}[a,)       &:=& \bigcap\sst{A}{aA ∧ \neto A} \\
 {}[-,b)      &:=& \bigcap\sst{B}{bB ∧ \seto B} \\
% {}[a,b]       &:=& \bigcap\sst{A}{aA ∧ (x \neq b.xA⊃SxA)} \\
 \notS A       &:=& \sst{aA}{Sa \notin A} \\
 La            &:=& a  [Sa,) \\
% L^9a          &:=& [a,) \\
 L^a          &:=& \sst{b[a,)}{Lb} \\
 L'a           &:=& \sst{b[a,)}{Lb} \\
 a \to b       &:=& Sa = b \\
 a \epito b    &:=& [a,) \ni b \\
% a \le b       &:=& [a,) \supseteq [b,) \\
% a < b         &:=& [a,) \supsetneq [b,) \\
% a \sim b      &:=& [a,) = [b,) \\
 \calA \isdisjoint      &:=& A,B\calA.A \neq B \funto AB=\emp \\
 \calA \covers a \to Sa &:=& A\calA.\{a,Sa\} \subseteq A \\
 {} [a,b]               &:=& \bigcap\sst{A}{aA ∧ xA\bsl\{b\}.SxA} \\
 {} [a,bc]              &:=& \bigcap\sst{A}{aA ∧ xA\bsl\{b,c\}.SxA} \\
 \end{array}
$

\msk

% Theorem: if $c,d[a,)$ then $c \epito d ∨ d \epito c$.
% 
% Proof: suppose that $c,d[a,)$ and $(c \epito d)$ and $(d \epito
% c)$, and define:
% %
% $$B := \sst{b[a,)}{b \epito c ∧ c \epito d}.$$
% 
% Then $aB$, $\neto B$, and so $[a,) \subseteq B$;
% 
% but $c,d \notin B$, which contradicts $c,d[a,)$.
% 
% \msk
% 
% Theorem: the elements in $L^a$ are all $\sim$-equivalent.
% 
% Theorem: the elements in $L^9a/\sim$ are linearly ordered.
% 
% \msk

% Theorem: each element $cL'a$, $c \neq a$, has exactly one predecessor in $L'a$.
% 
% Proof: the predecessor is $\notS (L^9a \bsl \{c\})$ (...)
% 
% \msk
% 
% Theorem: each element $cL^a$ has exactly one predecessor in $cL^a$.
% 
% Proof: the predecessor is $\notS (L^a \bsl \{c\})$ (...)
% 
% \msk
% 
% Theorem: if $L'a \neq \emp$ and $L^a \neq \emp$ then $L'a$ has a last element ---
% 
% namely, $\notS L'a$.


\newpage
% --------------------
% «cases-0-1-9»  (to ".cases-0-1-9")
% (s "Cases 0, 1 and 9" "cases-0-1-9")
\myslide {Cases 0, 1 and 9} {cases-0-1-9}

We say that $b$ {\sl is in a loop} --- and we write this as $Lb$ ---

when $Sb \epito b$, i.e., when $b[Sb,)$.

With the predicate $L$ we can split $[a,)$ in two disjoint parts:

a ``linear part'', $L'a$, and a ``loop part'', $L^a$, that are defined as:
%
$$\begin{array}{rcl}
  L'a  &:=& \sst{b[a,)}{Lb} \\
  L^a &:=& \sst{b[a,)}{Lb} \\
  \end{array}
$$

Theorem: $[a,)$ is either a loop,

an infinite straight line, or a ``nine''.

We will call these cases ``0'', ``1'' and ``9'',

according to the shapes of the numbers.

{\myttchars
%\footnotesize
\normalsize
\begin{verbatim}
    . <- ... <- .
 <-               <-
w                    .
 ->                ->
   a -> . -> . -> .

      Case 0


   a -> . -> . -> ...

      Case 1

                          ...
                       <-     <-
                      c          .
                       ->      ->
   a -> . -> ... -> b -> d -> .
   \________  ______/ \____  ____/
            \/             \/
           L'a            L°a

      Case 9
\end{verbatim}
}

\newpage
% --------------------
% «cases-0-1-9-2»  (to ".cases-0-1-9-2")
% (s "Cases 0, 1 and 9 (2)" "cases-0-1-9-2")
\myslide {Cases 0, 1 and 9 (2)} {cases-0-1-9-2}

If $a=0$ and $\Ind$ holds, then $[a,)$ is the whole universe (i.e., $N$).

We want to show that $\Zer$ only holds in the case ``0'',

and that $\Inj$ only holds in the case ``9''.

\msk

Lemmas:

$L^a$ is a single loop: for $b,cL^a$ we have $b \epito c$ and $c \epito b$.

A loop is a sink: there may be arrows from $L'a$ to $L^a$,

but no arrows leave $L^a$ back to $L'a$.

$L'a$ is linearly ordered: $b,cL'a$ either $b \epito c$ and $c \epito b$ hold,

and if both $b \epito c$ and $c \epito b$ hold then $b=c$.

Each element $\neq a$ of $L'a$ has exactly one predecessor (in $L'a$).

\ssk
$\upto$ {\sl [ I have not proved this yet!]}
\ssk

$L'a$ has a last element if and only if we are in the case ``9'';

and this last element (`$b$' in the figure), when it exists, is unique.

The successor of the last element of $L'a$ is in the loop part

(the arrow $b \to d$ in the figure for the case ``9'').

Every element in a loop has a predecessor in the loop

(arrows $w \to a$ in the figure ``0'', $c \to d$ in the figure ``9'');

this shows that $\Inj$ fails in the case ``9''.

\ssk
{\sl [I have not shown yet that the predecessor-in-the-loop is unique...

I will need that to show that $\Inj$ holds in ``0'']}
\ssk

In the cases ``1'' and ``9'' the element $a$ (i.e., 0) has no

predecessor --- i.e., $\Zer$ holds.









\large

\newpage
% --------------------
% «lemmas»  (to ".lemmas")
% (s "Lemmas" "lemmas")
\myslide {Lemmas} {lemmas}

$\begin{array}{rl}
  (1) & \neto[a,) \\
  (2) & \seto(-,b] \\
  (3) & \neto A \Bij \seto(N \bsl A) \\
  (4) & b[a,) \Bij a(-,b] \\
  \\
  (5) & [a,) = \{a\}[Sa,) \\
  (6) & a \epito b \Bij [a,) \supseteq [b,) \\
  (7) & a \epito b, b \epito a \Bij [a,) = [b,) \\
  (8) & a \epito b \funto Sa \epito Sb \\
  (9) & La \Bij [a,) = [Sa,) \\
 (10) & La \funto LSa \\
%(11) & \notS(-,b] = \emp \Bij Lb \\
 (11) & \neto(-,b] \Bij Lb \\
 \\
 (12) & a \neq b, a \epito b \funto Sa \epito b \\
 (13) & \notS(-,b] \subseteq \{b\} \\
 (14) & La \funto [a,) \subseteq (-,a] \\
 (15) & La, a \epito b \funto b \epito a \\
 (15') & La, a \epito b \funto Lb \\
 (15'') & La, a \epito b, a \epito c \funto b \epito c ∧ c \epito b \\
 (15''') & La, a \epito b \funto [a,)=[b,) \\
 \\
 (16) & c \nepito d, d \nepito c \funto \neto\sst{b}{b \epito c ∧ b \epito d} \\
 (17) & a \epito c, a \epito d, c \nepito d, d \nepito c \funto  \\
 (18) & a \epito c, a \epito d \funto c \epito d ∨ d \epito c \\
 (19) & a \epito c, a \epito d, Lc, Ld \funto c \epito d ∧ d \epito c \\
 \\
 (20) & L'a \neq \emp, L^a \neq \emp \funto \notS L'a \neq \emp \\
 (21) & b,c\notS L'a, b \neq c, b \epito c \funto  \\
 (22) & b,c\notS L'a, \funto b=c \\
 (23) & Ld, Sd \neq d \funto \notS([d,)\bsl\{d\}) \neq \emp \\
 \end{array}
$


\newpage
% --------------------
% «proofs-5-to-11»  (to ".proofs-5-to-11")
% (s "Proofs (5 to 11)" "proofs-5-to-11")
\myslide {Proofs (5 to 11)} {proofs-5-to-11}

%:*.<=.*\subseteq *
%:*.>=.*\supseteq *
%:*->>*\epito *
%:*!->>*\nepito *
%:*<<-*\epiot *
%:*!=*\neq *
%: *b->>cd*b \epito c ∧ b \epito d*
%:
%:                                                     Sa[a,)   \neto[a,)
%:                                                     ---------------------
%:  a(\{a\}[Sa,))   \neto(\{a\}[Sa,))    a[a,)     [Sa,).<=.[a,)   
%:  --------------------------------------    ---------------------------
%:       [a,).<=.\{a\}[Sa,)                  \{a\}[Sa,).<=.[a,)
%:                                          
%:       ^i-5.1                                 ^i-5.2
%:
%:   a->>b                  [a,).>=.[b,)
%:  -------  ----------     --------------
%:  b[a,)  \neto[a,)      [a,)\ni"b
%:  -------------------      ----------
%:    [b,).<=.[a,)          a->>b
%:
%:    ^i-6.1                  ^i-6.2
%:
%:      a->>b            b->>a           [a,)=[b,)      [a,)=[b,)    
%:  --------------   --------------    --------------   --------------   
%:  [a,).>=.[b,)   [b,).>=.[a,)    [a,).>=.[b,)   [a,).<=.[b,)   
%:  -------------------------------    --------------   --------------   
%:            [a,)=[b,)                  a->>b            b->>a        
%:
%:            ^i-7.1                       ^i-7.2           ^i-7.3
%:
%:                    [b\{a\}]^1   
%:                    -----------   
%:       a->>b            b=a           
%:      -------          -----                   -----------
%:      b[a,)          Sb=Sa     [b[Sa,)]^1  \neto[Sa,)
%:   --------------    ---------   -------------------------
%:   b\{a\}[Sa,)    Sb[Sa,)        Sb[Sa,)
%:   --------------------------------------------1     -----------
%:                 Sb[Sa,)                           \neto[Sa,)
%:                 -----------------------------------------------
%:                            [Sb,).<=.[Sa,)
%:                            ----------------
%:                               Sa->>Sb
%:
%:                               ^i-8
%:
%:         La                                 [a,)=[Sa,)
%:       ------            ------             ------------
%:       Sa->>a            a->>Sa               a[Sa,)
%:   ---------------   ---------------          --------
%:   [Sa,).>=.[a,)   [a,).>=.[Sa,)          Sa->>a
%:   ---------------------------------          ------
%:                [a,)=[Sa,)                    La
%:
%:                ^i-9.1                          ^i-9.2
%:
%:         La
%:        ------
%:        Sa->>a
%:       --------
%:       SSa->>Sa
%:       --------
%:         LSa
%:
%:         ^i-10
%:
%:   [b(-,a]]^1
%:   ------------
%:      b->>a       La
%:     -------    ------    --------
%:     Sb->>Sa    Sa->>a    a(-,a]  \neto(-,a]   
%:     -----------------    ---------------------
%:        Sb->>a                 Sa(-,a]
%:      ---------                ---------
%:      Sb(-,a]                 Sa->>a
%:     -----------1               ------
%:     \neto(-,a]                  La
%:
%:     ^i-11.1                      ^i-11.2
%:
$$\ded{i-5.1} \qquad \ded{i-5.2}$$
$$\ded{i-6.1} \qquad \ded{i-6.2}$$
$$\ded{i-7.1} \qquad \ded{i-7.2} \qquad \ded{i-7.3}$$
$$\ded{i-8}$$
$$\ded{i-9.1} \qquad \ded{i-9.2}$$
$$\ded{i-10}$$
$$\ded{i-11.1} \qquad \ded{i-11.2}$$


\newpage
% --------------------
% «proofs-12-to-15ppp»  (to ".proofs-12-to-15ppp")
% (s "Proofs (12 to 15${}'''$)" "proofs-12-to-15ppp")
\myslide {Proofs (12 to 15${}'''$)} {proofs-12-to-15ppp}


%:               a->>b
%:          --------------
%:   b!=a   b\{a\}[Sa,)
%:   ---------------------
%:       b[Sa,)
%:       --------
%:       Sa->>b
%:
%:       ^i-12
%:
%:                          [a(-,b]\bsl\{b\}]^1
%:                          ---------------------
%:  [a(-,b]\bsl\{b\}]^1          a(-,b]
%:  ---------------------          --------
%:         a!=b                      a->>b
%:         -------------------------------
%:                   Sa->>b
%:                 ---------
%:                 Sa(-,b]
%:            --------------------1
%:            \notS(-,b].<=.\{b\}
%:
%:            ^i-13
%:   
%:                 La
%:  --------   -----------
%:  a(-,a]   \neto(-,a]
%:  ----------------------
%:      [a,).<=.(-,a]
%:
%:      ^i-14
%:
%:      La
%:  ---------------
%:  [a,).<=.(-,a]
%:  -----------------
%:  b[a,)=>b(-,a]
%:  -----------------
%:    a->>b=>b->>a
%:
%:    ^i-15
%:
%:
%:  La  a->>b
%:  ---------
%:    b->>a       La
%:    -------   ------
%:    Sb->>Sa   Sa->>a   a->>b
%:    ------------------------
%:          Sb->>b
%:          ------
%:            Lb
%:
%:            ^i-15'
%:
%:   La  a->>b          La  a->>c
%:   ---------          ---------
%:     b->>a    a->>c     c->>a    a->>b
%:     --------------     --------------
%:          b->>c             c->>b
%:          -----------------------
%:                b->>c∧c->>b
%:
%:                ^i-15''
%:
%:         La  a->>b
%:         ---------
%:  a->>b    b->>a
%:  --------------
%:   [a,)=[b,)
%:
%:   ^i-15'''
%:
%:
$$\ded{i-13}$$
$$\ded{i-14}$$
$$\ded{i-15}$$
$$\ded{i-15'}$$
$$\ded{i-15''}$$
$$\ded{i-15'''}$$

\newpage
% --------------------
% «proofs-16-to-19»  (to ".proofs-16-to-19")
% (s "Proofs (16 to 19)" "proofs-16-to-19")
\myslide {Proofs (16 to 19)} {proofs-16-to-19}

%:  [b->>d]^1  c!->>d             [b->>c]^1  d!->>c
%:  -----------------             -----------------
%:        b!=c         [b->>c]^1       b!=d          [b->>d]^1
%:        ----------------------       -----------------------
%:                Sb->>c                     Sb->>d
%:                ---------------------------------1
%:                      \neto\sst{b}{b->>c∧b->>d}
%:  
%:                            ^i-16
%:  
%:                   a->>c   a->>d       c!->>d   d!->>c
%:                 -----------------   --------------------
%:  a->>c  a->>d   a\sst{b}{b->>cd}   \neto\sst{b}{b->>cd}
%:  ------------   ----------------------------------------
%:    c,d[a,)          [a,).<=.\sst{b}{b->>cd}             c!->>d   d!->>c
%:    -------------------------------------------         -----------------------
%:                c,d\sst{b}{b->>cd}                     c,d\notin\sst{b}{b->>cd}
%:                ----------------------------------------------------------------
%:                                            
%:  
%:                                            ^i-17
%:    a->>c  a->>d
%:  ----------------
%:  c!->>d∧d!->>c=>
%:  ----------------
%:  (c!->>d∧d!->>c)
%:  ----------------
%:  (c->>d∧d->>c)
%:  ----------------
%:  (c->>d∨d->>c)
%:  ---------------
%:    c->>d∨d->>c
%:  
%:    ^i-18
%:
%:                            Lc  [c->>d]^1   Ld  [d->>c]^1   
%:                            -------------   -------------
%:  a->>c  a->>d   [c->>d]^1    d->>c            c->>d       [d->>c]^1
%:  ------------   ------------------            ---------------------
%:  c->>d∨d->>c        c->>d∧d->>c                   c->>d∧d->>c
%:  ------------------------------------------------------------1
%:                          c->>d∧d->>c
%:  
%:                          ^i-19
%:
$$\ded{i-16}$$
$$\ded{i-17}$$
$$\ded{i-18}$$
$$\ded{i-19}$$


\newpage
% --------------------
% «proofs-20-to-23»  (to ".proofs-20-to-23")
% (s "Proofs (20 to 23)" "proofs-20-to-23")
\myslide {Proofs (20 to 23)} {proofs-20-to-23}

%:  L'a!=\emp   [\notS"L'a=\emp]^1
%:  ---------   ------------------
%:    aL'a       \neto"L'a
%:    ---------------------       ------------
%:         [a,).<=.L'a           L'a.<=.[a,)
%:         -----------------------------------
%:                   L'a=[a,)
%:                   ---------
%:                   L^a=\emp                  L^a!=\emp
%:                   -------------------------------------
%:                                   
%:                              ---------------1
%:                              \notS"L'a!=\emp
%:  
%:                              ^i-20
%:  
%:  b\notS"L'a   b!=c  b->>c   c\notS"L'a
%:  ----------    -----------   -----------
%:    a->>Sb        Sb->>c        cL'a      b\notS"L'a
%:    ---------------------------------     ------------
%:                SbL'a                    Sb\notin"L'a
%:                --------------------------------------
%:                               
%:  
%:                               ^i-21
%:  
%:  b,c\notS"L'a
%:  -------------
%:   b,cL'a
%:   ---------
%:   b,c[a,)    b,c\notS"L'a  [b!=c]^2  [b->>c]^1   b,c\notS"L'a  [b!=c]^2  [b->>c]^1
%:  -----------   ----------------------------------   ----------------------------------
%:  b->>c∨c->>b                                                    
%:  -----------------------------------------------------------------1
%:                             
%:                            ---2
%:                            b=c
%:  
%:                            ^i-22
%:  
%:                         Sd!=d           [\notS([d,)\bsl\{d\})=\emp]^1
%:                   -------------------   ------------------------------
%:      Ld           Sd([d,)\bsl\{d\})      \neto([d,)\bsl\{d\})
%:  ------------     ----------------------------------------------
%:  [d,)=[Sd,)              [Sd,).<=.[d,)\bsl\{d\}
%:  --------------------------------------------------
%:             [d,).<=.[d,)\bsl\{d\}
%:             -----------------------
%:                       
%:             ---------------------------1
%:             \notS([d,)\bsl\{d\})!=\emp
%:  
%:             ^i-23
%:  
$$\ded{i-20}$$
$$\ded{i-21}$$
$$\ded{i-22}$$
$$\ded{i-23}$$


\newpage
% --------------------
% «interval-lemmas»  (to ".interval-lemmas")
% (s "Interval lemmas" "interval-lemmas")
\myslide {Interval lemmas} {interval-lemmas}

Definitions:

$\begin{array}{lcl}
 S(A)   &:=& \sst{x}{aA. Sa=x} \\
 A,\_ &:=& \sst{X}{A \subseteq X} \\
 \_,B &:=& \sst{X}{S(X \bsl B) \subseteq X} \\
 A,B  &:=& A,\_  \_,B \\{}
 [A,B]  &:=& \bigcap \, A,B \\{}
 [a,b]  &:=& \bigcap \, \{a\},\{b\} \\{}
 [ab,cd]  &:=& \bigcap \, \{a,b\},\{c,d\} \\
 \end{array}
$

\msk

Elementary lemmas:

$\begin{array}{rl}
 (1) & A \subseteq [A,B] \\
 (2) & \notS([A,B]) \subseteq B \\
 (3) & [a,B] \subseteq [a,) = [a,\emp] \\
 (4) & AA',\_ = A,\_  A',\_ \\
 (5) & AA',\_ = A,\_  A',\_ \\
 (6) & \_,BB' = \_,B  \_,B' \\
 (7) & \_,BB' = \_,B  \_,B' \\
 (8) & [AA',B] \\& = \bigcap(A,\_  A',\_  \_,B) \\& = [A,B]  [A',B] \\
 (9) & [A,BB'] \\& = \bigcap(A,\_  \_,B  \_,B') \\& = [A,B]  [A,B'] \\
 \end{array}
$

\msk

Order lemmas:

$\begin{array}{rl}
 (1) & [AS(B),BB'] = [AS(B),B'] \\
 (2) & b \notin [A,C] \funto [A,C] = [A,\{b\}C] \\
 (3) & B[A,C] = \emp \funto [A,C] = [A,BC] \\
 (4) & b,b'  \notS([a,B]) \funto b=b' \\
 (5) & [a,BC] = [a,B] \text{ or } [a,BC] = [a,C] \\
 (6) & b[a,c] \funto [a,b] \subseteq [a,c] \\
 (7) & b[a,c] \funto [b,c] \subseteq [a,c] \\
 (8) & b,Sb[a,c]\phantom{, \; b \neq Sb} \funto [a,c] = [a,b][Sb,c] \\
 (9) & b,Sb[a,c]         , \; b \neq Sb  \funto [a,c] = [a,b][Sb,c] \\
 \end{array}
$



\newpage
% --------------------
% «interval-induction»  (to ".interval-induction")
% (s "Induction in intervals" "interval-induction")
\myslide {Induction in intervals} {interval-induction}

Induction lemmas:

$\begin{array}{rl}
 (1) & A \subseteq X, \; S(X \bsl B) \subseteq X \funto [A,B] \subseteq X \\
 (2) & A \subseteq X \subseteq [A,B], \; S(X \bsl B) \subseteq X \funto [A,B] = X \\
 \end{array}
$

\msk

Small lemmas: one whose proof I have not finished yet,

$\begin{array}{rl}
 (1) & b[a,c] \funto [a,b] = [a,bc] \subseteq [a,c] \\
 \end{array}
$

%:         -----------------
%:         \_,bc.>=.\_,b
%:  -------------------------------
%:  a,\_\_,bc.>=.a,\_\_,b
%:  -------------------------------
%:  a,bc.>=.a,b
%:  ---------------
%:  \bigcapa,bc.<=.\bigcapa,b
%:  -----------------------------
%:  [a,bc].<=.[a,b]
%:
%:  ^indintfoo
%:
$$\ded{indintfoo}$$

%:                    c\notin[a,b]∨b=c
%:            -------------------------------
%:            [a,b]\bsl\{b,c\}=[a,b]\bsl\{b\}
%:  -------   -------------------------------
%:  a[a,b]      S([a,b]\bsl\{b,c\}).<=.[a,b]
%:  -----------------------------------------
%:             [a,b]a,\_\_,bc
%:             --------------------
%:             [a,b]a,bc
%:             --------------------
%:             [a,b].>=.\bigcapa,bc
%:             --------------------
%:               [a,b].>=.[a,bc]
%:
%:               ^indint2
%:
%:
%:  \_,bc.<=.\_,c
%:  -------------------------------
%:  a,\_\_,bc.<=.a,\_\_,c
%:  -----------------------------------------------
%:  \bigcap(a,\_\_,bc).>=.\bigcap(a,\_\_,c)
%:  -----------------------------------------------
%:  \bigcapa,bc.>=.\bigcapa,c
%:  ---------------------------
%:  [a,bc].<=.[a,c]
%:
%:  ^indint3
%:

$$\ded{indint2}$$

$$\ded{indint3}$$


\newpage
% --------------------
% «interval-induction-2»  (to ".interval-induction-2")
% (s "Induction in intervals (2)" "interval-induction-2")
\myslide {Induction in intervals (2)} {interval-induction-2}

...and another small lemma (whose proof is complete):

$\begin{array}{rl}
 (2) & b[a,c] \funto [b,c] \subseteq [ab,c] = [a,c] \\
 \end{array}
$

%:
%:  -----------------
%:  b,\_.>=.ab,\_
%:  -------------------------------
%:  b,\_\_,c.>=.ab,\_\_,c
%:  -------------------------------------------------
%:  \bigcap(b,\_\_,c).<=.\bigcap(ab,\_\_,c)
%:  -------------------------------------------------
%:  [b,c]\subseteq[ab,c]
%:
%:  ^indint0
%:
%:         b[a,c]
%:     --------------
%:     b\bigcapa,c
%:  --------------------
%:  b,\_\supseteqa,c
%:  --------------------
%:  b,\_a,c=a,c
%:  --------------------------
%:  b,\_a,\_\_,c=a,c
%:  --------------------------
%:  ab,\_\_,c=a,c
%:  --------------------
%:  ab,c=a,c
%:  ------------
%:  [ab,c]=[a,c]
%:
%:  ^indint1
%:

$$\ded{indint0} \qquad \ded{indint1}$$



Big lemmas (not proved yet):

$\begin{array}{rl}
 (1) & b,c[a,c], b \neq c \funto [a,Sb] = [a,b]  \{Sb\} \\
 (2) & b,c[a,c], b \neq c \funto [b,c] = \{b\}  [Sb,c] \\
 (3) & b,c[a,c], b \neq c \funto [a,c] = [a,b]  [Sb,c] \\
 \end{array}
$



\newpage
% --------------------
% «interval-induction-3»  (to ".interval-induction-3")
% (s "Induction in intervals (3)" "interval-induction-3")
\myslide {Induction in intervals (3)} {interval-induction-3}

Definitions:

$\begin{array}{rcl}
 {} [a,b;Sb]       &:=& ([a,Sb] = [a,b]\{Sb\}) \\
 {} [b;Sb,c]       &:=& ([b,c] = \{b\}[Sb,c]) \\
 {} [a,b;Sb,c]     &:=& ([a,c] = [a,b][Sb,c]) \\
 {} [a,b;Sb;SSb,c] &:=& ([a,c] = [a,b]\{Sb\}[SSb,c]) \\
 \end{array}
$

\msk

Induction rules:
%:
%:  P(a)  b[a,).P(b)⊃P(Sb)
%:  -------------------------
%:       b[a,).P(b)
%:
%:       ^iind-1
%:
%:  P(a)  b[a,c],b\neq"c.P(b)⊃P(Sb)
%:  ---------------------------------
%:       b[a,c].P(b)
%:
%:       ^iind-2
%:
%:  P(a)  b[a,c],b\neq"c,Sb\neq"c.P(b)⊃P(Sb)
%:  ------------------------------------------
%:       b[a,c],b\neq"c.P(b)
%:
%:       ^iind-3
%:
$$\ded{iind-1}$$
$$\ded{iind-2}$$
$$\ded{iind-3}$$

\msk


Lemmas:
%:
%:  c[a,c]  a\neq"c    b,Sb,c[a,c]  b,Sb\neq"c  [a,b;Sb]     b,c[a,c]  b\neq"c    
%:  ================    ==================================     ==================    
%:     [a,a;Sa]                   [a,Sb;SSb]                      [a,b;Sb]           
%:                                                                                   
%:     ^ind-abb0                  ^ind-abb+                       ^ind-abb           
%:                                                                                   
%:  c[a,c]  a\neq"c    b,Sb,c[a,c]  b,Sb\neq"c  [b;Sb,c]     b,c[a,c]  b\neq"c    
%:  ================    ==================================     ==================    
%:     [a;Sa,c]                   [Sb;SSb,c]                      [b;Sb,c]           
%:                                                                                   
%:     ^ind-bbc0                  ^ind-bbc+                       ^ind-bbc           
%:                                                                                   
%:  c[a,c]  a\neq"c    b,Sb,c[a,c]  b,Sb\neq"c  [a,b;Sb,c]   b,c[a,c]  b\neq"c    
%:  ================    ====================================   ==================    
%:     [a,a;Sa,c]                 [a,Sb;SSb,c]                    [a,b;Sb,c]         
%:                                                                                   
%:     ^ind-abbc0                 ^ind-abbc+                      ^ind-abbc          
%:  
$$\ded{ind-abb0} \qquad \ded{ind-abb+} \qquad \ded{ind-abb}$$
$$\ded{ind-bbc0} \qquad \ded{ind-bbc+} \qquad \ded{ind-bbc}$$
$$\ded{ind-abbc0} \qquad \ded{ind-abbc+} \qquad \ded{ind-abbc}$$


Proofs:
%:  
%:  b,Sb,c[a,c]  b,Sb\neq"c  [a,b;Sb]
%:  ==================================
%:            [a,Sb;SSb]              
%:
%:            ^ind-abb++
%:
%:  
%:  b,Sb,c[a,c]  b,Sb\neq"c  [b;Sb,c]
%:  ==================================
%:            [Sb;SSb,c]              
%:                                    
%:            ^ind-bbc++
%:
%:
%:               Sb,c[a,c]  Sb\neq"c
%:               --------------------
%:  [a,b;Sb,c]      [Sb;SSb,c]         b,c[a,c]  b\neq"c
%:  --------------------------         ------------------
%:       [a,b;Sb;SSb,c]                  [a,b;Sb]
%:       ----------------------------------------
%:                      [a,Sb;SSb,c]
%:  
%:                      ^ind-abbc++
%:
$$\ded{ind-abb++}$$
$$\ded{ind-bbc++}$$
$$\ded{ind-abbc++}$$


















\newpage
% --------------------
% «intervals»  (to ".intervals")
% (s "Intervals" "intervals")
\myslide {Intervals} {intervals}

{\bf [This is old! Cannibalize and delete it.]}

Convention: whenever we write $[a,b]$ it is implicit that $a \epito b$.

We will write $ABC$ to indicate a disjoint union ---

i.e., $ABC$, but it is implicit that $\{A,B,C\}$ is disjoint.

\msk

Lemmas:

$\begin{array}{rl}
  (1) & \notS[a,b] \subseteq \{b\} \\
  (2) & a \neq b \funto [a,b] = \{a\}[Sa,b] \\
  (3) & a,b,c \different,\, b[a,c] \funto [a,b][Sb,c] \\
  (4) & b,c[a,b] \funto [a,bc]=[a,b]∨[a,bc]=[a,c] \\
  (5) & a,b,c,d \different, \, b,c[a,d], \, b[a,bc] \funto \\
      & Sb,c \notin [a,bc] \\ 
  (6) & a,b,c,d \different, \, b,c[a,d] \funto \\
      & [a,d]=\{a\}[Sa,bc][Sb,cd][Sc,bd] \\
  (7) & a,b,c,d \different, \, b,c[a,d] \funto \\
      & \{\{a\},\,[Sa,bc],\,[Sb,cd],\,[Sc,bd]\} \text{ does not cover } \\
      & a \to Sa,\, b \to Sb, \text{ or } c \to Sc \\
  (8) & La \funto [Sa,a] = [Sa,) = [a,) \\
 \end{array}
$

\msk

Now suppose that $a$ is in a loop, that $b,c[Sa,a]$,

that $Sa,b,c,a$ are different, and that $Sb=Sc$.

This implies that
%
$$[Sa,a]=\{Sa\}[SSa,bc][Sb,ca][Sc,ba],$$

and this should be absurd (check).

\msk

This implies that each element in a loop

has at most one predecessor in the loop.

We already knew that each element in a loop

has a predecessor in the loop, so this shows that
%
$$La \funto !p[a,).Sp=a.$$



% (fooi "\\nepito" "!->>" "\\epito" "->>" "\\funto" "=>" "\\neq" "!=")
% (fooi "\\nepito" "!->>" "\\epito" "->>" "\\funto" "=>")



%*

\end{document}

% Local Variables:
% coding:           raw-text-unix
% ee-anchor-format: "«%s»"
% End: