Simplicial Set

The proposed simplicial set has similarities to (and is complementary to) the simplicial complex and Delta complexes already in FriCAS. The simplicial set has a nicer mathematical structure in some ways but in other ways it has extra complications in that it requires an order on the simplicies. So it would be useful to have both structures in FriCAS. Simplicial sets are better for a combinatorial approach whereas simplicial complexes are better for geographic/topological intuition.

On MathOverflow the topologist Allen Hatcher wrote:

"In some areas simplicial sets are far more natural and useful than simplicial complexes, in others the reverse is true. If one drew a Venn diagram of the people using one or the other structure, the intersection might be very small."

Requirements

A simplicial set is a functor from a simplex category to set.

Ideally it would have been nice to implement a generic (pre-)sheaf in FriCAS and then implement simplicial set as an instance of this sheaf. However I don't think the FriCAS type system could do this. What I had in mind would be a database but instead of linking the database tables with common keys the links would come from a 'schema'

What I would like to do is define it like this:

NNI==> NonNegativeInteger
FiniteSimplicialSet(n:NNI) : Exports == Impl where
  ...
  Impl ==> add
   Rep := List(Record(name:String,subfaces:Array(n,FiniteSimplicialSet(n-1))))
 
TopLevelFaces : Exports == Impl where
  ...
  Impl ==> add
   Rep := List(FiniteSimplicialSet(NNI))

but I don't think SPAD can do this. I don't know how to have Rep defined recursively so think of this as pseudo code.

Array would be a fixed length list (of length 'n').

So each face of dimension 'n' has 'n' subfaces of dimension 'n-1'. This structure can never be infinite because it recurses down to dimension zero which has zero subfaces. degenerate faces are encoded in their non-degenerate form (that is duplicates are removed).

The subfaces may be shared (a subface may be in multiple faces) this is how we encode faces which are glued to each other.

Since I don't think FriCAS type system can manage the above encodings of Rep I have instead implemented a single list of faces which includes all subfaces. The structure is then encoded as indexes into this list. That is, each face of dimension 'n' has n+1 indexes into its subfaces. This is not as good as the above approaches because the structure is not as obvious or enforced by Rep but at least it is implementable.

FiniteSimplicialSet() : Exports == Impl where
  NNI==> NonNegativeInteger
  ...
  Impl ==> add
   Rep := List(Record(s:String,faces:List(NNI)))

Simplex Category

Because a simplicial set is a functor from a simplex category to set we first need to work out how to encode a simplex category.

An implementation of a WeakOrderIndexed with some specific order preserving functions. This is implemented as a list of a total order (List NNI). The order preserving functions are known as face maps d(i) and degeneracy maps s(i) and they obey the following identities:

if i < j then d(i)*d(j) = d(j-1)*d(i)
if i < j then d(i)*s(j) = s(j-1)*d(i)
d(j)*s(j) = id = d(j+1)*s(j)
if i > j+1 then d(i)*s(j) = s(j)*d(i-1)
if i <= j then s(i)*s(j) = s(j+1)*s(i)

where i and j are NNI indexes and * is composition operator

-- /usr/local/bin/fricas
-- )co fricas/sset.spad
-- a := weakOrderSimplex([1,2,3])
-- getAtIndex(2:NNI,a)

)abbrev category WORDE2 WeakOrder
++ Author: Martin Baker
++ Description:
++ The class of weakly ordered sets, that is a total order
++ with possible degenerate (duplicate) cases.

WeakOrder() : Category == Definition where
  NNI==> NonNegativeInteger

  Definition ==> SetCategory() with
    ge : (%,NNI,NNI) -> Boolean
      ++ ge(W,i,j) is a greater than or equal test
      ++ between index i and index j of this weak order

)abbrev domain WOS WeakOrderSimplex
++ Author: Martin Baker
++ Description:
++   An implemetation of a WeakOrder with some specific order preserving
++   functions. This is implemented as a list of a total order (List NNI).
++   The order preserving functions are known as face maps d(i) and
++   degeneracy maps s(i) and they obey the following identities:
++   if i < j then d(i)*d(j) = d(j-1)*d(i)
++   if i < j then d(i)*s(j) = s(j-1)*d(i)
++   d(j)*s(j) = id = d(j+1)*s(j)
++   if i > j+1 then d(i)*s(j) = s(j)*d(i-1)
++   if i <= j then s(i)*s(j) = s(j+1)*s(i)
++   where i and j are NNI indexes and * is composition operator
++   for more documentation see:
++ References:
++   http://www.euclideanspace.com/maths/topology/algtop/cell/sSet/

WeakOrderSimplex() : Exports == Impl where
  NNI==> NonNegativeInteger
  x< hconcat(x::OutputForm, y::OutputForm)

  Exports ==> WeakOrder with
    weakOrderSimplex : (List(NNI)) -> %
      ++ constructor
    getAtIndex : (index : NNI, input : %) -> NNI
      ++ get the number at given index
      ++ index is from 0
    d : (index : NNI, input : %) -> %
      ++ face maps
      ++ remove entry at given index.
    s : (index : NNI, input : %) -> %
      ++ degeneracy maps
      ++ duplicate entry at given index
    checkIdentities : (input : %,i : NNI,j : NNI) -> Void
      ++ Identities are:
      ++   if i < j then d(i)*d(j) = d(j-1)*d(i)
      ++   if i < j then d(i)*s(j) = s(j-1)*d(i)
      ++   d(j)*s(j) = id = d(j+1)*s(j)
      ++   if i > j+1 then d(i)*s(j) = s(j)*d(i-1)
      ++   if i <= j then s(i)*s(j) = s(j+1)*s(i)

  Impl ==> add

   -- NNI is total order but List(NNI) can be constrained to be a weak order.
   Rep := List(NNI)

   -- constructor
   weakOrderSimplex(a : List(NNI)) : % ==
     [a]

   -- output
   coerce(x : %) : OutputForm ==
     y := empty()@List(OutputForm)
     s := cycleEntry x
     while not(eq?(x, s)) repeat
       y := concat((first x)::OutputForm, y)
       x := rest x
     y := reverse! y
     bracket y

   getAtIndex(index : NNI, input : %) : NNI ==
     if index<0 then error "index too low in weakOrderSimplex"
     if (index+1)>#input then error "index too high in weakOrderSimplex"
     elt(input,index+1)

   -- ge(W,i,j) is a greater than or equal test
   -- between index i and index j of this weak order
   ge(w:%,i:NNI,j:NNI) : Boolean ==
     wi:NNI := getAtIndex(i,w)
     wj:NNI := getAtIndex(j,w)
     wi >= wj

   -- face maps.
   d(index : NNI, input : %) : % ==
     delete(input,index+1)

   -- degeneracy maps.
   s(index : NNI, input : %) : % ==
     v:NNI := getAtIndex(index,input)
     insert(v,input,index+1)

   -- Check identities which are:
   --   if i < j then d(i)*d(j) = d(j-1)*d(i)
   --   if i < j then d(i)*s(j) = s(j-1)*d(i)
   --   d(j)*s(j) = id = d(j+1)*s(j)
   --   if i > j+1 then d(i)*s(j) = s(j)*d(i-1)
   --   if i <= j then s(i)*s(j) = s(j+1)*s(i)
   checkIdentities(input : %,i : NNI,j : NNI) : Void ==
     pj := subtractIfCan(j,1)
     pj case "failed" =>
       print (message "j too low j="<≤j)
       void
     print(message "d(i)*d(j)=" << d(i,d(j,input)))
     print(message "d(j-1)*d(i)=" << d(pj,d(i,input)))
     print(message "d(i)*s(j)=" << d(i,s(j,input)))
     print(message "s(j-1)*d(i)=" << s(pj,d(i,input)))
     void

metadata block

see also:	I have put the code here.
Correspondence about this page

Requirements

Simplex Category

Category of Simplicial Sets

EuclideanSpace

Where Are You

Installing and Running Code