;; 2025-11-30.  ueb08.scm

;; Please note that loading the following libraries nat.scm and
;; pos.scm takes a few minutes on minlog-web

(set! COMMENT-FLAG #f)
(libload "nat.scm")
(libload "pos.scm")
(set! COMMENT-FLAG #t)

;; We need a binary representation of positive natural numbers.

(display-alg "pos")
#|
pos
	One:	pos
	SZero:	pos=>pos
	SOne:	pos=>pos
|#

(display-pconst "NatDouble")
#|
NatDouble
  comprules
0	NatDouble Zero	Zero
1	NatDouble(Succ n)	Succ(Succ(NatDouble n))
|#

;; We define PN

(add-program-constant "PN" (py "pos=>nat"))

(add-item-to-algebra-edge-to-embed-term-alist
 "pos" "nat"
 (let ((var (make-var (make-alg "pos") -1 t-deg-one "")))
   (make-term-in-abst-form
    var (make-term-in-app-form
         (make-term-in-const-form
          (pconst-name-to-pconst "PN"))
         (make-term-in-var-form var)))))

(add-computation-rules
 "PN One" "Succ Zero"
 "PN(SZero p)" "NatDouble(PN p)"
 "PN(SOne p)" "Succ(PN(SZero p))")

;; PNTotal
(set-totality-goal "PN")
(assume "p^" "Tp")
(elim "Tp")
;; 3-5
(use "TotalNatSucc")
(use "TotalNatZero")
;; 4
(assume "p^1" "Tp1" "IH")
(ng #t)
(use "NatDoubleTotal")
(use "IH")
;; 5
(assume "p^1" "Tp1" "IH")
(ng #t)
(use "TotalNatSucc")
(use "NatDoubleTotal")
(use "IH")
;; Proof finished.
;; (cp)
(save-totality)
;; ok, PNTotal added as a new theorem.

(replace-item-in-algebra-edge-to-embed-term-alist
 "pos" "nat"
 (let ((var (make-var (make-alg "pos") -1 t-deg-one "")))
   (make-term-in-abst-form
    var (make-term-in-app-form
	 (make-term-in-const-form
	  (pconst-name-to-pconst "PN"))
	 (make-term-in-var-form var)))))

(display-pconst "NatEven")
#|
NatEven
  comprules
0	NatEven Zero	True
1	NatEven(Succ Zero)	False
2	NatEven(Succ(Succ n))	NatEven n
|#

(display-pconst "NatHalf")
#|
NatHalf
  comprules
0	NatHalf Zero	Zero
1	NatHalf(Succ Zero)	Zero
2	NatHalf(Succ(Succ n))	Succ(NatHalf n)
|#

;; We define NP

(add-program-constant "NP" (py "nat=>pos"))
(add-computation-rules
 "NP Zero" "1"
 "NP(Succ Zero)" "1"
 "NP(Succ(Succ n))"
 "[if (NatEven n)
      (SZero(NP(Succ(NatHalf n))))
      (SOne(NP(Succ(NatHalf n))))]")

(pp (nt (pt "NP(Succ(Succ Zero))")))
(pp (nt (pt "NP(Succ(Succ(Succ Zero)))")))
(pp (nt (pt "NP(Succ(Succ(Succ(Succ Zero))))")))
(pp (nt (pt "NP(Succ(Succ(Succ(Succ(Succ Zero)))))")))

;; Totality of NP needs CVIndPvar

(pp "CVIndPvar")
#|
(F -> all n (Pvar nat)n) -> 
all n(all m(m<n -> (Pvar nat)m) -> (Pvar nat)n) -> all n (Pvar nat)n
|#

;; NPStep
(set-goal "all n(Zero<n -> all m(m<=Succ n -> TotalPos(NP m)) -> 
 TotalPos(NP(Succ(Succ n))))")
(assume "n" "0<n" "Prog")
(ng #t)
(cases (pt "NatEven n"))
;; 4,5
(assume "En")
(ng #t)
(use "TotalPosSZero")
(use "Prog")
(ng #t)
(use "NatHalfLe")
;; 5
(assume "On")
(ng #t)
(use "TotalPosSOne")
(use "Prog")
(ng #t)
(use "NatHalfLe")
;; Proof finished.
;; (cp)
(save "NPStep")

(display-idpc "TotalPos")
#|
TotalPos	with content of type pos
	TotalPosOne:	TotalPos 1
	TotalPosSZero:	all p^(TotalPos p^ -> TotalPos(SZero p^))
	TotalPosSOne:	all p^(TotalPos p^ -> TotalPos(SOne p^))
|#

;; The proof of totality of NP is omitted, or better assumed by

(change-t-deg-to-one "NP")

;; We now aim at proving that NP and PN are inverse to each other.

;; (display-pconst "NP" "PN")

;; NP
;;   comprules
;; 0	NP Zero	1
;; 1	NP(Succ Zero)	1
;; 2	NP(Succ(Succ n))
;; 	[if (NatEven n)
;;  (SZero(NP(Succ(NatHalf n))))
;;  (SOne(NP(Succ(NatHalf n))))]
;; PN
;;   comprules
;; 0	PN 1	Succ Zero
;; 1	PN(SZero p)	NatDouble(PN p)
;; 2	PN(SOne p)	Succ(PN(SZero p))

(pp "NatHalfDouble")
;; all n NatHalf(NatDouble n)=n

(pp "NatEvenDouble")
;; all n NatEven(NatDouble n)

;; NPDouble
(set-goal "all n(Zero<n ->  NP(NatDouble n)=SZero(NP n))")
(cases)
;; 2,3
(assume "Absurd")
(use "EfAtom")
(use "Absurd")
;; 3
(assume "n" "Useless")
(ng #t)
(simp "NatHalfDouble")
(simp "NatEvenDouble")
(ng #t)
(use "Truth")
;; Proof finished.
;; (cp)
(save "NPDouble")

(pp "NatHalfSuccDouble")
;; all n NatHalf(Succ(NatDouble n))=n

(pp "NatEvenToOddSucc")
;; all n(NatEven n -> NatEven(Succ n) -> F)

;; The following theorems may be helpful
(pp "EfAtom")
(pp "NatHalfSuccDouble")
(pp "NatEvenToOddSucc")
(pp "NatEvenDouble")

;; NPSuccDouble
(set-goal "all n(Zero<n ->  NP(Succ(NatDouble n))=SOne(NP n))")
(cases)
;; ...
(save "NPSuccDouble")

(pp "NatLt0Double")
;; all n(Zero<n -> Zero<NatDouble n)

;; NatZeroLtPos
(set-goal "all p Zero<p")
(ind)
;; 2-4
(use "Truth")
;; 3
(ng #t)
(assume "p" "0<p")
(use "NatLt0Double")
(use "0<p")
;; 4
(ng #t)
(strip)
(use "Truth")
;; Proof finished.
;; (cp)
(save "NatZeroLtPos")

;; The following theorems may be helpful
(pp "Truth")
(pp "NPDouble")
(pp "NPSuccDouble")
(pp "NatZeroLtPos")

;; NPNId
(set-goal "all p NP(PN p)=p")
(ind)
;; ...
(save "NPNId")

;; (pp "NatDoubleSuccHalfEven")
;; all n(NatEven n -> NatDouble(Succ(NatHalf n))=Succ(Succ n))

;; NPNId needs CVInd

(pp "CVInd")
;; all ws(all n(all m(m<n -> ws m) -> ws n) -> all n ws n)

(pp (var-to-type (pv "ws")))
;; nat=>boole

;; (pp "NatDoubleSuccHalfEven")
;; all n(NatEven n -> NatDouble(Succ(NatHalf n))=Succ(Succ n))

(pp "NatDoubleHalfOdd")
;; all n((NatEven n -> F) -> Succ(NatDouble(NatHalf n))=n)

(set-goal "all n(NatEven n -> NatDouble(Succ(NatHalf n))=Succ(Succ n))")
(assume "n")
(ng #t)
(use "NatDoubleHalfEven")
;; Proof finished.
(save "NatDoubleSuccHalfEven")

;; You may find the following theorems helpful
(pp "NatDoubleSuccHalfEven")
(pp "NatLeToLtSucc")
(pp "NatHalfLe")
(pp "NatDoubleHalfOdd")

;; PNPIdSucc
(set-goal "all n PN(NP(Succ n))=Succ n")
(use "CVInd")
(ng #t)
(cases)
;; 4,5
(assume "Useless")
(ng #t)
(use "Truth")
;; 5
(assume "n" "Prog")
(ng #t)
(cases (pt "NatEven n"))
;; ...
(save "PNPIdSucc")

;; You may find the following theorems helpful

(pp "EfAtom")
(pp "PNPIdSucc")

;; PNPId
(set-goal "all n(Zero<n -> PN(NP n)=n)")
(cases)
;; ...
(save "PNPId")
