Re: [HoTT] two's complement integers

[Martin Escardo <escardo.martin@gmail.com>]

Nice. I haven't seen this. But I have considered two similar things:

(1) The natural numbers defined by

  0
  2x+1
  2x+2

This is not a HIT - just a normal inductive types.

(2) A HIT for the dyadics numbers D in the interval [0,1] with constructors

data 𝔹 : Type₀ where
  L R : 𝔹                           -- 0 and 1
  l r : 𝔹 → 𝔹                       -- x ↦ x/2 and x ↦ (x+1)/2
  eqL : L   ≡ l L                   -- 0 = 0/2
  eqM : l R ≡ r L                   -- 1/2 = (0+1)/2
  eqR : R   ≡ r R                   -- 1 = (1+1)/2

Then, like your HIT, this is automatically a set without the need of
truncation. But I didn't find an simple proof of this. Together with
Alex Rice, we proved this by showing it to be equivalent to another type
which is easily seen to be a aset:

data 𝔻 :  Type₀ where
 middle : 𝔻
 left   : 𝔻 → 𝔻
 right  : 𝔻 → 𝔻

data 𝔹' : Type₀ where
 L' : 𝔹'
 R' : 𝔹'
 η  : 𝔻 → 𝔹'

l' : 𝔹' → 𝔹'
l' L'    = L'
l' R'    = η middle
l' (η x) = η (left x)

r' : 𝔹' → 𝔹'
r' L'    = η middle
r' R'    = R'
r' (η x) = η (right x)

eqL' : L'    ≡ l' L'
eqM' : l' R' ≡ r' L'
eqR' : R'    ≡ r' R'

eqL' = refl
eqM' = refl
eqR' = refl

Then the types 𝔹 and 𝔹' are equivalent, and clearly 𝔹' is a set
because it has decidable equality.

Moreover, the "binary systems" (𝔹,L,R,l,r,eqL,eqM,eqR) and
(𝔹',L',R',l',r',eqL',eqM',eqR') are isomorphic.

(And we implemented in this in Cubical Agda.)

I wonder if your definition of the integers with the HIT is isomorphic
to an inductively defined version without a HIT as above, and this is
how you proved it to be a set.

Martin

On 04/03/2021 20:43, Michael Shulman wrote:
> Has anyone considered the following HIT definition of the integers?
> 
> data ℤ : Type where
>   zero : ℤ                              -- 0
>   negOne : ℤ                            -- -1
>   dbl : ℤ → ℤ                           -- n ↦ 2n
>   sucDbl : ℤ → ℤ                        -- n ↦ 2n+1
>   dblZero : dbl zero ≡ zero             -- 2·0 = 0
>   sucDblNegOne : sucDbl negOne ≡ negOne -- 2·(-1)+1 = -1
> 
> The idea is that it's an arbitrary-precision version of little-endian
> two's-complement, with sucDbl and dbl representing 1 and 0
> respectively, and negOne and zero representing the highest-order sign
> bit 1 and 0 respectively.  Thus for instance
> 
> sucDbl (dbl (sucDbl (sucDbl zero))) = 01101 = 13
> dbl (sucDbl (dbl (dbl negOne))) = 10010 = -14
> 
> The two path-constructors enable arbitrary expansion of the precision, e.g.
> 
> 01101 = 001101 = 0001101 = ...
> 10010 = 110010 = 1110010 = ...
> 
> This seems like a fairly nice definition: it should already be a set
> without any truncation, it's binary rather than unary, and the
> arithmetic operations can be defined in the usual digit-by-digit way
> without splitting into cases by sign.  Mathematically speaking, it
> represents integers by their images in the 2-adic integers, with zero
> and negOne representing infinite tails of 0s and 1s respectively.  (An
> arbitrary 2-adic integer, of course, is just a stream of bits.)
> 
> Best,
> Mike
> 

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/9eefbc82-ba49-b101-433d-c3c1e452ecda%40googlemail.com.