[Agda] Re: Data.Nat.Primality.Prime and irreducibility

Dr. ERDI Gergo gergo at erdi.hu
Sat Mar 7 05:21:33 CET 2015


Nils,

Would it make sense to add Irreducible to the standard library? Here's the 
generalization I have in mind:

open import Algebra
open import Relation.Nullary
open import Data.Sum
open import Level using (Level; _⊔_)
import Algebra.FunctionProperties

module _ {c ℓ : Level} (R : Algebra.CommutativeSemiring c ℓ) where

open CommutativeSemiring R

private
   infix 4 _≉_

   _≉_ : Carrier → Carrier → Set ℓ
   x ≉ y = ¬ (x ≈ y)

   open Algebra.FunctionProperties _≈_

   is0 : Carrier → Set _
   is0 n = Identity n _+_

   is1 : Carrier → Set _
   is1 n = Identity n _*_

data Irreducible (n : Carrier) : Set (ℓ ⊔ c) where
   irreducible : (not0 : ¬ is0 n) → (not1 : ¬ is1 n) →
                 (prf : ∀ x y → ≈ x * y → is1 x ⊎ is1 y) →
                 Irreducible n

I've also reworked my proof that Irreducible => Prime for Data.Nat to use 
the above generalization and it's definitely not too bad. I haven't ported 
the other direction yet, but will do if we decide it's worth adding to the 
stdlib.

Bye,
 	Gergo


More information about the Agda mailing list