# HG changeset patch # User Shinji KONO # Date 1695089498 -32400 # Node ID 8fb16f9a882aefe94064d86a300b15c2c9167980 # Parent fff18d4a063b17033572b4e966790f59336524bb ... diff -r fff18d4a063b -r 8fb16f9a882a Galois.agda-lib --- a/Galois.agda-lib Mon Sep 18 13:19:37 2023 +0900 +++ b/Galois.agda-lib Tue Sep 19 11:11:38 2023 +0900 @@ -1,5 +1,5 @@ name: Galois -depend: standard-library-2.0 +depend: standard-library include: src flags: --warning=noUnsupportedIndexedMatch diff -r fff18d4a063b -r 8fb16f9a882a src/Putil.agda --- a/src/Putil.agda Mon Sep 18 13:19:37 2023 +0900 +++ b/src/Putil.agda Tue Sep 19 11:11:38 2023 +0900 @@ -5,7 +5,7 @@ open import Algebra open import Algebra.Structures open import Data.Fin hiding ( _<_ ; _≤_ ; _-_ ; _+_ ; _≟_) -open import Data.Fin.Properties hiding ( <-trans ; ≤-trans ; ≤-irrelevant ; _≟_ ) renaming ( <-cmp to <-fcmp ) +open import Data.Fin.Properties as DFP hiding ( <-trans ; ≤-trans ; ≤-irrelevant ; _≟_ ) renaming ( <-cmp to <-fcmp ) open import Data.Fin.Permutation open import Function hiding (id ; flip) open import Function.Inverse as Inverse using (_↔_; Inverse; _InverseOf_) @@ -123,7 +123,7 @@ -- pins1 (suc i) (suc j) (s≤s si≤n) = psawpim {suc (suc (suc n))} {j} (s≤s (s≤s si≤n)) ∘ₚ pins1 i j (≤-trans si≤n a≤sa ) -- open import Relation.Binary.HeterogeneousEquality as HE using (_≅_ ) -open ≡-Reasoning +-- open ≡-Reasoning pins : {n m : ℕ} → m ≤ n → Permutation (suc n) (suc n) pins {_} {zero} _ = pid @@ -157,7 +157,7 @@ toℕ (fromℕ< (≤-trans (fin y = suc x → toℕ y < suc m ... | tri> ¬a ¬b c = ⊥-elim ( nat-<> c (subst (λ k → k < suc m) (sym p12) a )) @@ -232,13 +232,13 @@ fromℕ< (≤-trans (s≤s a₁) (s≤s (s≤s m≤n) )) ≡⟨⟩ fromℕ< (s≤s (≤-trans a₁ (s≤s m≤n))) - ≡⟨ ? ⟩ -- lemma10 {suc (suc n)} (p3 x) {p6} {p2} ⟩ + ≡⟨ lemma10 {suc (suc n)} (p3 x) {p6} {p2} ⟩ fromℕ< ( s≤s (fin ¬a ¬b c = ⊥-elim (nat-≤> c q ¬a ¬b c = fromℕ< {Data.Nat.pred (toℕ (Inverse.to perm (suc x)))} (p00 x c) p← : Fin n → Fin n - p← x with perm ⟨$⟩ˡ (suc x) | inspect (_⟨$⟩ˡ_ perm ) (suc x) - p← x | zero | record { eq = e } = ⊥-elim ( sh2 perm p0=0 {x} e ) - p← x | suc t | _ = t + p← x with <-fcmp (perm ⟨$⟩ˡ (suc x)) (# 0) + p← x | tri≈ ¬a b ¬c = ⊥-elim (sh2 perm p0=0 b) + p← x | tri> ¬a ¬b c = fromℕ< {Data.Nat.pred (toℕ (Inverse.from perm (suc x)))} (p01 x c) + -- using "with" something binded in ≡ is prohibited piso← : (x : Fin n ) → p→ ( p← x ) ≡ x - piso← x with perm ⟨$⟩ˡ (suc x) | inspect (_⟨$⟩ˡ_ perm ) (suc x) - piso← x | zero | record { eq = e } = ⊥-elim ( sh2 perm p0=0 {x} e ) - piso← x | suc t | _ with perm ⟨$⟩ʳ (suc t) | inspect (_⟨$⟩ʳ_ perm ) (suc t) - piso← x | suc t | _ | zero | record { eq = e } = ⊥-elim ( sh1 perm p0=0 e ) - piso← x | suc t | record { eq = e0 } | suc t1 | record { eq = e1 } = begin - t1 - ≡⟨ plem0 plem1 ⟩ - x - ∎ where - open ≡-Reasoning - plem0 : suc t1 ≡ suc x → t1 ≡ x - plem0 refl = refl - plem1 : suc t1 ≡ suc x - plem1 = begin - suc t1 - ≡⟨ sym e1 ⟩ - Inverse.to perm _ - ≡⟨ cong (λ k → Inverse.to perm k ) (sym e0) ⟩ - Inverse.to perm ( Inverse.from perm _ ) - ≡⟨ inverseʳ perm ⟩ - suc x - ∎ + piso← x = p02 _ _ refl refl where + p02 : (y z : Fin n) → p← x ≡ y → p→ y ≡ z → z ≡ x + p02 y z px=y py=z with <-fcmp (perm ⟨$⟩ˡ (suc x)) (# 0) + ... | tri≈ ¬a b ¬c = ⊥-elim (sh2 perm p0=0 b) + ... | tri> ¬a ¬b c with <-fcmp (perm ⟨$⟩ʳ (suc y)) (# 0) + ... | tri≈ ¬a₁ b ¬c = ⊥-elim (sh1 perm p0=0 b) + ... | tri> ¬a₁ ¬b₁ c₁ = ? where + open ≡-Reasoning + p03 : toℕ (Inverse.to perm (suc x)) ≡ suc (toℕ y) + p03 = ? + -- with perm ⟨$⟩ˡ (suc x) in eq + -- ... | t = ? +-- ... | zero = ⊥-elim ( sh2 perm p0=0 {y} eq ) +-- ... | suc s with perm ⟨$⟩ˡ (suc x) in eq1 +-- ... | zero = ⊥-elim ( sh1 perm p0=0 eq1 ) +-- ... | suc t1 = begin +-- ? ≡⟨ ? ⟩ +-- ? ∎ where +-- open ≡-Reasoning +-- plem0 : suc t1 ≡ suc x → t1 ≡ x +-- plem0 refl = refl +-- plem1 : suc t1 ≡ suc x +-- plem1 = begin +-- suc t1 ≡⟨ sym eq1 ⟩ +-- Inverse.to perm _ ≡⟨ cong (λ k → Inverse.to perm k ) (sym ?) ⟩ +-- Inverse.to perm ( Inverse.from perm _ ) ≡⟨ inverseʳ perm ⟩ +-- suc x +-- ∎ +-- piso→ : (x : Fin n ) → p← ( p→ x ) ≡ x - piso→ x with perm ⟨$⟩ʳ (suc x) | inspect (_⟨$⟩ʳ_ perm ) (suc x) - piso→ x | zero | record { eq = e } = ⊥-elim ( sh1 perm p0=0 {x} e ) - piso→ x | suc t | _ with perm ⟨$⟩ˡ (suc t) | inspect (_⟨$⟩ˡ_ perm ) (suc t) - piso→ x | suc t | _ | zero | record { eq = e } = ⊥-elim ( sh2 perm p0=0 e ) - piso→ x | suc t | record { eq = e0 } | suc t1 | record { eq = e1 } = begin - t1 - ≡⟨ plem2 plem3 ⟩ - x - ∎ where - plem2 : suc t1 ≡ suc x → t1 ≡ x - plem2 refl = refl - plem3 : suc t1 ≡ suc x - plem3 = begin - suc t1 ≡⟨ sym e1 ⟩ - Inverse.from perm (suc t) ≡⟨ cong (λ k → Inverse.from perm k ) (sym e0 ) ⟩ - Inverse.from perm ((Inverse.to perm (suc x)) ) ≡⟨ cong (λ k → Inverse.from perm (Inverse.to perm (suc x)) ) (sym e0 ) ⟩ - Inverse.from perm ( Inverse.to perm _ ) ≡⟨ inverseˡ perm ⟩ - suc x ∎ - + piso→ x = ? +-- with perm ⟨$⟩ʳ (suc x) | inspect (_⟨$⟩ʳ_ perm ) (suc x) +-- piso→ x | zero | record { eq = e } = ⊥-elim ( sh1 perm p0=0 {x} e ) +-- piso→ x | suc t | _ with perm ⟨$⟩ˡ (suc t) | inspect (_⟨$⟩ˡ_ perm ) (suc t) +-- piso→ x | suc t | _ | zero | record { eq = e } = ⊥-elim ( sh2 perm p0=0 e ) +-- piso→ x | suc t | record { eq = e0 } | suc t1 | record { eq = e1 } = begin +-- t1 +-- ≡⟨ plem2 plem3 ⟩ +-- x +-- ∎ where +-- plem2 : suc t1 ≡ suc x → t1 ≡ x +-- plem2 refl = refl +-- plem3 : suc t1 ≡ suc x +-- plem3 = begin +-- suc t1 ≡⟨ sym e1 ⟩ +-- Inverse.from perm (suc t) ≡⟨ cong (λ k → Inverse.from perm k ) (sym e0 ) ⟩ +-- Inverse.from perm ((Inverse.to perm (suc x)) ) ≡⟨ cong (λ k → Inverse.from perm (Inverse.to perm (suc x)) ) (sym e0 ) ⟩ +-- Inverse.from perm ( Inverse.to perm _ ) ≡⟨ inverseˡ perm ⟩ +-- suc x ∎ +-- shrink-iso : { n : ℕ } → {perm : Permutation n n} → shrink (pprep perm) refl =p= perm -shrink-iso {n} {perm} = record { peq = λ q → refl } +shrink-iso {n} {perm} = record { peq = λ q → ? } shrink-iso2 : { n : ℕ } → {perm : Permutation (suc n) (suc n)} → (p=0 : perm ⟨$⟩ˡ (# 0) ≡ # 0) → pprep (shrink perm p=0) =p= perm @@ -536,10 +564,12 @@ perm ⟨$⟩ʳ ( perm ⟨$⟩ˡ zero ) ≡⟨ cong (λ k → perm ⟨$⟩ʳ k ) p=0 ⟩ perm ⟨$⟩ʳ zero - ∎ - s001 (suc q) with perm ⟨$⟩ʳ (suc q) | inspect (_⟨$⟩ʳ_ perm ) (suc q) - ... | zero | record {eq = e} = ⊥-elim (sh1 perm p=0 {q} e) - ... | suc t | e = refl + ∎ where + open ≡-Reasoning + s001 = ? + -- s001 (suc q) with perm ⟨$⟩ʳ (suc q) | inspect (_⟨$⟩ʳ_ perm ) (suc q) + -- ... | zero | record {eq = e} = ⊥-elim (sh1 perm p=0 {q} e) + -- ... | suc t | e = refl shrink-cong : { n : ℕ } → {x y : Permutation (suc n) (suc n)} @@ -547,22 +577,23 @@ → (x=0 : x ⟨$⟩ˡ (# 0) ≡ # 0 ) → (y=0 : y ⟨$⟩ˡ (# 0) ≡ # 0 ) → shrink x x=0 =p= shrink y y=0 shrink-cong {n} {x} {y} x=y x=0 y=0 = record { peq = p002 } where p002 : (q : Fin n) → (shrink x x=0 ⟨$⟩ʳ q) ≡ (shrink y y=0 ⟨$⟩ʳ q) - p002 q with x ⟨$⟩ʳ (suc q) | inspect (_⟨$⟩ʳ_ x ) (suc q) | y ⟨$⟩ʳ (suc q) | inspect (_⟨$⟩ʳ_ y ) (suc q) - p002 q | zero | record { eq = ex } | zero | ey = ⊥-elim ( sh1 x x=0 ex ) - p002 q | zero | record { eq = ex } | suc py | ey = ⊥-elim ( sh1 x x=0 ex ) - p002 q | suc px | ex | zero | record { eq = ey } = ⊥-elim ( sh1 y y=0 ey ) - p002 q | suc px | record { eq = ex } | suc py | record { eq = ey } = p003 ( begin - suc px - ≡⟨ sym ex ⟩ - x ⟨$⟩ʳ (suc q) - ≡⟨ peq x=y (suc q) ⟩ - y ⟨$⟩ʳ (suc q) - ≡⟨ ey ⟩ - suc py - ∎ ) where - p003 : suc px ≡ suc py → px ≡ py - p003 refl = refl - + p002 q = ? +-- p002 q with x ⟨$⟩ʳ (suc q) | inspect (_⟨$⟩ʳ_ x ) (suc q) | y ⟨$⟩ʳ (suc q) | inspect (_⟨$⟩ʳ_ y ) (suc q) +-- p002 q | zero | record { eq = ex } | zero | ey = ⊥-elim ( sh1 x x=0 ex ) +-- p002 q | zero | record { eq = ex } | suc py | ey = ⊥-elim ( sh1 x x=0 ex ) +-- p002 q | suc px | ex | zero | record { eq = ey } = ⊥-elim ( sh1 y y=0 ey ) +-- p002 q | suc px | record { eq = ex } | suc py | record { eq = ey } = p003 ( begin +-- suc px +-- ≡⟨ sym ex ⟩ +-- x ⟨$⟩ʳ (suc q) +-- ≡⟨ peq x=y (suc q) ⟩ +-- y ⟨$⟩ʳ (suc q) +-- ≡⟨ ey ⟩ +-- suc py +-- ∎ ) where +-- p003 : suc px ≡ suc py → px ≡ py +-- p003 refl = refl +-- open import FLutil FL→perm : {n : ℕ } → FL n → Permutation n n @@ -643,7 +674,8 @@ pins ( toℕ≤pred[n] x ) ⟨$⟩ʳ (# 0) ≡⟨ px=x x ⟩ x - ∎ + ∎ where + open ≡-Reasoning x=0 : (perm ∘ₚ flip (pins (toℕ≤pred[n] x))) ⟨$⟩ˡ (# 0) ≡ # 0 x=0 = subst ( λ k → (perm ∘ₚ flip (pins (toℕ≤pred[n] k))) ⟨$⟩ˡ (# 0) ≡ # 0 ) f001 (p=0 perm) x=0' : (pprep (FL→perm fl) ∘ₚ pid) ⟨$⟩ˡ (# 0) ≡ # 0 @@ -671,7 +703,8 @@ perm→FL ( FL→perm fl ) ≡⟨ FL→iso fl ⟩ fl - ∎ + ∎ where + open ≡-Reasoning pcong-Fp : {n : ℕ } → {x y : FL n} → x ≡ y → FL→perm x =p= FL→perm y pcong-Fp {n} {x} {x} refl = prefl @@ -691,6 +724,7 @@ ≡⟨⟩ perm ⟨$⟩ʳ q ∎ ) } + where open ≡-Reasoning FL-inject : {n : ℕ } → {g h : Permutation n n } → perm→FL g ≡ perm→FL h → g =p= h FL-inject {n} {g} {h} g=h = record { peq = λ q → ( begin @@ -702,6 +736,7 @@ ≡⟨ peq (FL←iso h) q ⟩ h ⟨$⟩ʳ q ∎ ) } + where open ≡-Reasoning FLpid : {n : ℕ} → (x : Permutation n n) → perm→FL x ≡ FL0 → FL→perm FL0 =p= pid → x =p= pid FLpid x eq p0id = ptrans pf2 (ptrans pf0 p0id ) where @@ -712,4 +747,4 @@ pFL0 : {n : ℕ } → FL0 {n} ≡ perm→FL pid pFL0 {zero} = refl -pFL0 {suc n} = cong (λ k → zero :: k ) pFL0 +pFL0 {suc n} = cong (λ k → zero :: k ) ? -- pFL0 diff -r fff18d4a063b -r 8fb16f9a882a src/fin.agda --- a/src/fin.agda Mon Sep 18 13:19:37 2023 +0900 +++ b/src/fin.agda Tue Sep 19 11:11:38 2023 +0900 @@ -104,6 +104,10 @@ -- lemma10 : {n i j : ℕ } → ( i ≡ j ) → {i