[Agda] primality definition
Sergei Meshveliani
mechvel at botik.ru
Sat Mar 7 21:44:47 CET 2015
N. Raghavendra <raghu at hri.res.in> write recently
> At 2015-03-06T13:46:21+04:00, Sergei Meshveliani wrote:
>> Personally, I use a generic primality definition for any GCDRing
>> (an integral ring with GCD):
>> IsPrime : C → Set (α ⊔ α=)
>> IsPrime a = a ≉ 0# × ¬ Invertible a ×
>> (∀ {x y} → (x * y ≈ a) → Invertible x ⊎ Invertible y),
>> which, I think, is the classical definition.
>> Then, I prove several lemmata about possible Factorization structure for
>> the elements of such a ring, and find that this my definition works all
>> right.
> Thanks! However, my question was specially about how to prove that the
> Data.Nat.Primality definition of an element n of N being Prime is
> equivalent to n being irreducible in the multiplicative monoid of
> non-zero natural numbers.
> Have you put your proofs on the Web?
Do you mean proofs about generic IsPrime, Factorization etc. ?
The thing is not ready yet. I hope to release it in 2015.
The subject is a bit more complex than one could think. Because factorization
is not into the prime elements of C = Carrier. The factor components are the
ASD classes -- classes of associated elements. And Factorization is a Multiset
over ASD classes. A (unique) FactorizationRing uses this definition,
this way Factorization becomes unique there. And factorization of the product
of two elements is the sum of the corresponding multisets. And
Multiset C Nat is a commutative monoid under _+ms_.
First, I need to finish generic Multiset.
This will form a separate library called AList.
Then I have to return to Factorization, FactorizationRing,
then to prove various properties of the residue ring R/(b) as depending
on the factorization of b, and so on.
The thing is almost ready, but unfortunately this "almost" always lasts
longer than I hope.
Regards,
------
Sergei
More information about the Agda
mailing list