Nuprl - Proof: hanoi general exists 2 2 1 1

(18steps total) Remark PfGloss PfGloss PrintForm Definitions Lemmas HanoiTowers Sections NuprlLIB Doc

IF YOU CAN SEE THIS go to /sfa/Nuprl/Shared/Xindentation_hack_doc.html
At: hanoi general exists 2 2 1 1

1. n :

2. 0<n
3.

f,g:({1...n-1}

Peg), a:

.
3.

z:{a...}, s:({a...z}

{1...n-1}

Peg).
3. s is a Hanoi(n-1 disk) seq on a..z & s(a) = f & s(z) = g
4. f : {1...n}

Peg
5. g : {1...n}

Peg
6. a :

7.

f(n) = g(n)
8. m : {a...}
9. s1 : {a...m}

{1...n-1}

Peg
10. s1 is a Hanoi(n-1 disk) seq on a..m
11. s1(a) = f
12. s1(m) = (

i.otherPeg(f(n); g(n)))
13. z : {m+1...}
14. s2 : {m+1...z}

{1...n-1}

Peg
15. s2 is a Hanoi(n-1 disk) seq on m+1..z
16. s2(m+1) = (

i.otherPeg(f(n); g(n)))
17. s2(z) = g

s1:({a...m}

{1...n}

Peg), s2:({m+1...z}

{1...n}

Peg).

(s1 @(m) s2) is a Hanoi(n disk) seq on a..z

& s1(a) = f

{1...n}

Peg

& s2(z) = g

{1...n}

Peg

By:

BackThru:
Thm*

n:

, a:

, z:{a...}, m:{a...z-1}, f,g:({1...n}

Peg).
Thm* f(n)

g(n)
Thm*

Thm* (

s1:({a...m}

{1...n-1}

Peg), s2:({m+1...z}

{1...n-1}

Peg).
Thm* (s1 is a Hanoi(n-1 disk) seq on a..m
Thm* (& s1(a) = f

{1...n-1}

Peg
Thm* (& s2 is a Hanoi(n-1 disk) seq on m+1..z
Thm* (& s2(z) = g

{1...n-1}

Peg
Thm* (& s1(m) = s2(m+1)
Thm* (& (

i:{1...n-1}. s1(m,i)

f(n) & s2(m+1,i)

g(n)))
Thm*

Thm* (

r1:({a...m}

{1...n}

Peg), r2:({m+1...z}

{1...n}

Peg).
Thm* ((r1 @(m) r2) is a Hanoi(n disk) seq on a..z & r1(a) = f & r2(z) = g)
THEN
Witness: s1 | s2

Generated subgoals:

1 18. i : {1...n-1}
s1(m,i) f(n)
2 steps

2 18. i : {1...n-1}
s2(m+1,i) g(n)
2 steps

About:

IF YOU CAN SEE THIS go to /sfa/Nuprl/Shared/Xindentation_hack_doc.html

(18steps total) Remark PfGloss PfGloss PrintForm Definitions Lemmas HanoiTowers Sections NuprlLIB Doc