agda - unitario - subconjunto

Una definición para conjuntos finitos en Agda

Question

Soy nuevo en Agda. Estoy leyendo el documento "Dependent Types at Work" de Ana Bove y Peter Dybjer. No entiendo la discusión de los Conjuntos Finitos (en la página 15 en mi copia).

El papel define un tipo de Fin :

data Fin : Nat -> Set where
fzero : {n : Nat} -> Fin (succ n)
fsucc : {n : Nat} -> Fin n -> Fin (succ n)

Debo estar perdiendo algo obvio. No entiendo cómo funciona esta definición. ¿Podría alguien simplemente traducir la definición de fin al inglés cotidiano? Eso podría ser todo lo que necesito para entender esta parte del documento.

Gracias por tomarse el tiempo para leer mi pregunta. Lo aprecio.

Answer 1

data Fin : Nat -> Set where

Fin es un tipo de datos parametrizado por un número natural (o: Fin es una función de nivel de tipo que toma un Nat y devuelve un Set (tipo básico), es decir, para cualquier número natural n Fin n es un Set ).

 fzero : {n : Nat} -> Fin (succ n)

Para todos los números naturales, n fzero es un miembro del tipo / conjunto Fin (succ n) (de lo cual se deduce que para todos los números positivos (es decir, todos los naturales, excepto cero) n fzero es un miembro de Fin n ).

 fsucc : {n : Nat} -> Fin n -> Fin (succ n)

Para todos los números naturales n y todos los valores m de tipo Fin n , fsucc m es un miembro de tipo Fin (succ n) .

Entonces fzero es un miembro de Fin n para todos n excepto cero y fsucc m es un miembro de Fin n para todos n que representan un número mayor que fsucc m .

Básicamente, Fin n representa el conjunto de todos los números naturales más pequeños que n , es decir, de todos los índices válidos para listas de tamaño n .