free monoids on a set, implemented as lists. about unimath HOT 14 CLOSED

I've started on this, Sep 29, 2015.

from unimath.

Benedikt suggests also formalizing the traditional induction principle for lists, which
would arise from defining lists inductively. Do that without assuming X is a set.

PS: Anders did this in commit ce2e165

from unimath.

Also re-implement lists as functions from finite ordered sets to X. This might
be more convenient, as the use of it would not involve futzing with natural numbers.

A start was made here: https://github.com/DanGrayson/UniMath/blob/090d5f7514ea92588952f4506b1c512871d9e167/UniMath/Ktheory/OrderedSet.v

from unimath.

How is a finite ordered set different from stn n paired with the natural order on it?

BTW - I think, generally it is better not to pair things such as ( A B ) when B can be computed from A.

On Sep 30, 2015, at 11:28 AM, Daniel R. Grayson [email protected] wrote:

Also re-implement lists as functions from finite ordered sets to X. This might
be more convenient, as the use of it would not involve futzing with natural numbers.

—
Reply to this email directly or view it on GitHub #173 (comment).

from unimath.

On Wed, Sep 30, 2015 at 12:10 PM, Vladimir Voevodsky [email protected] wrote:

How is a finite ordered set different from stn n paired with the natural order on it?

The two types are equivalent, as is "nat", but the type of finite ordered sets might be more convenient to use, because "coprod" of two finite ordered sets can be ordered, whereas "coprod" of two standard finite sets is not a standard finite set. Perhaps that's not a big enough advantage to justify the work in making a second implementation of lists, but it's the way Bourbaki actually speaks of associativity.

BTW - I think, generally it is better not to pair things such as ( A B ) when B can be computed from A.

I agree. In which of my type definitions do you see me doing that? A finite ordered set
is a set with a proof of finiteness and an ordering. There is no way to deduce an
ordering from a proof of finiteness.

from unimath.

More generally, it would be nice to have a notion of a finite combination/product/composition of elements for any set with a binary operation. This could be used to define:

• presentations by generators and relations
• the notion of linear dependence (essential for developing free modules i.e. linear algebra, which there is none of right now!)
• general statements such as "f is multilinear", where f takes inputs from any finite product of vector spaces
• and so on...

I've made an attempt in this direction, but got stuck in a quagmire of proving more and more basic facts about stn ns -- I'm almost certainly just doing it wrong. Have you been able to make headway on this issue @DanGrayson?

from unimath.

@siddharthist - could you tell me what you mean by "a notion of a finite combination/product/composition of elements for any set with a binary operation" ? Is it the same thing as a "word"?

from unimath.

@DanGrayson Yeah, that's a better way of phrasing it :)

from unimath.

In that case, I use an inductive type in Ktheory/Monoid.v to define word, but the rule now is that we don't introduce new inductive types in UniMath, so that has to be redone, but I haven't thought about how to do so.

For what it's worth, here is the definition:

  Inductive word X : Type :=
    | word_unit : word X
    | word_gen : X -> word X
    | word_op : word X -> word X -> word X.

from unimath.

If X is a set, then this is a particularly simple instance of what Anders, Benedikt and I implemented in substitution systems, based on omega-cocontinuous functors. word_gen corresponds to the inclusion of variables into terms, and there is no variable binding.

from unimath.

Can you give more detail or point us to the code?

from unimath.

A place to start looking is the implementation of lists, binary trees and the lambda calculus:

https://github.com/UniMath/UniMath/blob/master/UniMath/CategoryTheory/Inductives/Lists.v
https://github.com/UniMath/UniMath/blob/master/UniMath/CategoryTheory/Inductives/Trees.v
https://github.com/UniMath/UniMath/blob/master/UniMath/CategoryTheory/Inductives/LambdaCalculus.v

I think your inductive type would be a variation of the lambda calculus without the "lambda constructor", but with a unit constructor.

from unimath.

How does
https://github.com/UniMath/UniMath/blob/master/UniMath/CategoryTheory/Inductives/Lists.v
compare to
https://github.com/UniMath/UniMath/blob/master/UniMath/Combinatorics/Lists.v ?

I started using the latter.

from unimath.

A maybe scholastic answer would be that they are weakly equivalent. The lists in CategoryTheory are an instance of a generic construction (initial algebras of omega-cocontinuous functors), the ones in Combinatorics are a very concrete implementation that works fine for lists. My first guess is that if the lists are the only needed data type, then the concrete implementation would be fine, but if other data types came in, it would be better if they all came from the same first principle.

from unimath.