## Thursday, August 29, 2013

### Oriented set systems

Every set of elements such as #{0 1 2 3 4} has a power set which contains all of its subsets whose own subsets form set systems such as the following set:
#{#{0 2} #{0 3} #{0 4} #{1 2} #{1 3} #{1 4}}

Associated with every set system is the notion of a section subsystem corresponding to some subset of the underlying set of the set system. The section subsystem of #{0 1 2 3} for the above set system is:
#{#{0 2} #{0 3} #{1 2} #{1 3}}

Things get to be a bit more interesting once we introduce the idea of an oriented set system which is simply a set system whose every set is associated with some collection of values:
(= (orientation-form #{[0 1] [1 2] [2 0]})
{#{0 2} #{[2 0]}, #{1 2} #{[1 2]}, #{0 1} #{[0 1]}})

Every oriented set system has oriented section subsystems associated with it corresponding to the section subsystems of its underlying set system. From this we see that the notion of an induced subrelation is isomorphic to the notion of a section subsystem of an oriented set system. If we want to define some notion of subsystems of a transformation system on a set then an obvious option is to use stabilizing set systems:
(= (orientation-form #{[0 1 2 3] [1 0 2 3] [0 1 3 2] [1 0 3 2]})
{#{} #{()},
#{0 1} #{((1 0)},
#{2 3} #{((2 3)},
#{0 1 2 3}, #{((0 1) (2 3))})

This orientation form for transformation systems such as permutation groups allows us to reason about induced substructures for them as well. We can also represent measures as oriented set systems in the obvious way:
{#{} 0,#{0} 1, #{1} 1, #{0 1} 2}

However, for dealing with structures such as rings that have multiple relations such as addition and multiplication that we need to consider then it is useful to represent such structures as a sort of relation:
#{(:add 0 0 0),(:add 0 1 1), (:add 1 0 1), (:add 1 1 0)
(:mul 0 0 0),(:mul 0 1 0), (:mul 1 0 0), (:mul 1 1 1)}

Using this same technique we can produce an oriented set system for rings such as the field of size two displayed above:
#{#{0} #{(:add 0 0 0)},
#{1} #{(:mul 0 0 0)},
#{0 1} #{(:add 0 1 1), (:add 1 0 1), (:add 1 1 0),
(:mul 0 1 0), (:mul 1 0 0), (:mul 1 1 1)}}

As we have demonstrated so far oriented set systems allow us to describe the induced substructures of N-ary relations, hypergraphs, transformation systems, semirings, measure spaces, topologies, and a wide variety of other structures. Well this is a pretty extensive approach to substructures sometimes we want to get a family of substructures such as for set systems:
#{#{0 1 2} #{2 3 4} #{4 5 6}}
#{#{1 2} #{2 3}}

Even though the set system #{#{0 1 2} #{2 3 4} #{4 5 6}} does not contain #{1 2} or #{2 3} as elements it produces them as substructures. In this case it may be useful to distinguish this system as a higher set system:
#{#{0 1 2} #{2 3 4} #{4 5 6}}
#{#{#{0} #{1} #{2}} #{#{2} #{3} #{4}} #{#{4} #{5} #{6}}}

I am not currently familiar with any notion of induced substructures that cannot be described by an oriented higher set system.