[Agda] ℕ <--iso--> Bin⁺ ∩ HasLast1if
Sergei Meshveliani
mechvel at botik.ru
Tue Nov 26 19:00:46 CET 2013
People,
as an exercise in Agda, I provide
http://botik.ru/pub/local/Mechveliani/agdaNotes/bin2.zip
-- my own proof in Agda for suc - isomorphism between ℕ and its
binary codes
-- an addition to Standard library lib-0.7.
1. It uses the binary code (Bin⁺) representation in which
0 <--> [], and a binary code either is [] or ends with 1b
(as the higher bit).
This higher bit condition is expressed as HasLast1if, HasLast1.
2. It is proved in Bin.agda that
ℕ <--suc-isomorphic--> Bin⁺ ∩ HasLast1if,
where
suc corresponds to addCarryToBitList.
3. For this aim, we re-implement toDigits in the form of
toBDigits : (n : ℕ) → ∃ \ (bs : Bin⁺) →
fromDigits bs ≡ n × HasLast1if bs
(for base = 2 only)
- because it is easier for us to compose proofs for such.
4. The main parts are
toBDigits,
injective-fromDigits
- injectiveness of fromDigits on Bin⁺ ∩ HasLast1if.
5. My question is:
can this be proved in a simpler/shorter (nicer) way?
(for example, injective-fromDigits looks lengthy).
6. The program consists of the two modules and is tested under
Agda-2.3.3-pre Malonzo, lib-0.7
- both of the development version of November 24, 2013.
(the 2.3.2.2 version, or lower ones, will not do).
I hope it will also work under any later version.
Regards,
------
Sergei
More information about the Agda
mailing list