# Poset S¶

- S: SetCategory

holds a complete set together with a structure to codify the partial order. for more documentation see: http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/logic/index.`htm`

Date Created: Aug 2015 Basic Operations: Related packages: UserDefinedPartialOrdering in setorder.spad Related categories: PartialOrder in catdef.spad Related Domains: DirectedGraph in graph.spad Also See: AMS Classifications:

- +: (%, %) -> %
- from FiniteGraph S
- =: (%, %) -> Boolean
- from BasicType
- ~=: (%, %) -> Boolean
- from BasicType

- addArrow!: (%, NonNegativeInteger, NonNegativeInteger) -> %
`addArrow!(s, nm, n1, n2)`

adds an arrow to the graph`s`

, where:`n1`

is the index of the start object`n2`

is the index of the end object This is done in a non-mutable way, that is, the original poset is not changed instead a new one is constructed.- addArrow!: (%, Record(name: String, arrType: NonNegativeInteger, fromOb: NonNegativeInteger, toOb: NonNegativeInteger, xOffset: Integer, yOffset: Integer, map: List NonNegativeInteger)) -> %
- from FiniteGraph S
- addArrow!: (%, String, NonNegativeInteger, NonNegativeInteger) -> %
- from FiniteGraph S
- addArrow!: (%, String, NonNegativeInteger, NonNegativeInteger, List NonNegativeInteger) -> %
- from FiniteGraph S
- addArrow!: (%, String, S, S) -> %
- from FiniteGraph S
- addObject!: (%, Record(value: S, posX: NonNegativeInteger, posY: NonNegativeInteger)) -> %
- from FiniteGraph S

- addObject!: (%, S) -> %
`addObject!(s, n)`

adds object with coordinates`n`

to the graph`s`

. This is done in a non-mutable way, that is, the original poset is not changed instead a new one is constructed.- adjacencyMatrix: % -> Matrix NonNegativeInteger
- from FiniteGraph S
- arrowName: (%, NonNegativeInteger, NonNegativeInteger) -> String
- from FiniteGraph S
- arrowsFromArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- arrowsFromNode: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- arrowsToArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- arrowsToNode: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- coerce: % -> OutputForm
- from CoercibleTo OutputForm

- completeReflexivity: % -> %
- Reflexivity requires forall(
`x`

): x<=x This function enforces this by making sure that every element has arrow to itself. That is, the leading diagonal is`true`

.

- completeTransitivity: % -> %
- Transitivity requires forall(
`x`

,`y`

,`z`

): x<=y and y<=z implies x<=z This function enforces this by making sure that the composition of any two arrows is also an arrow.

- coverMatrix: % -> IncidenceAlgebra(Integer, S)
- the covering matrix of a list of elements from a comparison function the list is assumed to be topologically sorted, i.e.
`w`

.`r`

. to a linear extension of the comparison function`f`

This function is based on code by Franz Lehner. Notes by Martin Baker on the webpage here: url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/logic/moebius/} - createWidth: NonNegativeInteger -> NonNegativeInteger
- from FiniteGraph S
- createX: (NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S
- createY: (NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S
- cycleClosed: (List S, String) -> %
- from FiniteGraph S
- cycleOpen: (List S, String) -> %
- from FiniteGraph S
- deepDiagramSvg: (String, %, Boolean) -> Void
- from FiniteGraph S
- diagramHeight: % -> NonNegativeInteger
- from FiniteGraph S
- diagramsSvg: (String, List %, Boolean) -> Void
- from FiniteGraph S
- diagramSvg: (String, %, Boolean) -> Void
- from FiniteGraph S
- diagramWidth: % -> NonNegativeInteger
- from FiniteGraph S
- distance: (%, NonNegativeInteger, NonNegativeInteger) -> Integer
- from FiniteGraph S
- distanceMatrix: % -> Matrix Integer
- from FiniteGraph S

- finitePoset: (List S, (S, S) -> Boolean) -> %
- constructor where the set and structure is supplied. The structure is supplied as a predicate function.

- finitePoset: (List S, List List Boolean) -> %
- constructor where the set and structure is supplied.
- flatten: DirectedGraph % -> %
- from FiniteGraph S

- getArr: % -> List List Boolean
`getArr(s)`

returns a list of all the arrows (or edges) Note: different from getArrows(`s`

) which is inherited from FiniteGraph(`S`

)- getArrowIndex: (%, NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S
- getArrows: % -> List Record(name: String, arrType: NonNegativeInteger, fromOb: NonNegativeInteger, toOb: NonNegativeInteger, xOffset: Integer, yOffset: Integer, map: List NonNegativeInteger)
- from FiniteGraph S

- getVert: % -> List S
`getVert(s)`

returns a list of all the vertices (or objects) of the graph`s`

. Note: different from getVertices(`s`

) which is inherited from FiniteGraph(`S`

)- getVertexIndex: (%, S) -> NonNegativeInteger
- from FiniteGraph S
- getVertices: % -> List Record(value: S, posX: NonNegativeInteger, posY: NonNegativeInteger)
- from FiniteGraph S

- glb: (%, List NonNegativeInteger) -> Union(NonNegativeInteger, failed)
- ‘greatest lower bound’ or ‘infimum’ In this version of
`glb`

nodes are represented as index values. Not every subset of a poset will have a`glb`

in which case “failed” will be returned as an error indication. - hash: % -> SingleInteger
- from SetCategory
- hashUpdate!: (HashState, %) -> HashState
- from SetCategory

implies: (%, NonNegativeInteger, NonNegativeInteger) -> Boolean

- incidenceMatrix: % -> Matrix Integer
- from FiniteGraph S
- inDegree: (%, NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S

- indexToObject: (%, NonNegativeInteger) -> S
- returns the object at a given index
- initial: () -> %
- from FiniteGraph S
- isAcyclic?: % -> Boolean
- from FiniteGraph S

- isAntiChain?: % -> Boolean
- is a subset of a partially ordered set such that any two elements in the subset are incomparable

- isAntisymmetric?: % -> Boolean
- Antisymmetric requires forall(
`x`

,`y`

): x<=y and y<=x iff x=y Returns`true`

if this is the case for every element.

- isChain?: % -> Boolean
- is a subset of a partially ordered set such that any two elements in the subset are comparable
- isDirected?: () -> Boolean
- from FiniteGraph S
- isDirectSuccessor?: (%, NonNegativeInteger, NonNegativeInteger) -> Boolean
- from FiniteGraph S
- isFixPoint?: (%, NonNegativeInteger) -> Boolean
- from FiniteGraph S
- isFunctional?: % -> Boolean
- from FiniteGraph S
- isGreaterThan?: (%, NonNegativeInteger, NonNegativeInteger) -> Boolean
- from FiniteGraph S

- joinIfCan: (%, List NonNegativeInteger) -> Union(NonNegativeInteger, failed)
- returns the join of a subset of lattice given by list of elements

- joinIfCan: (%, NonNegativeInteger, NonNegativeInteger) -> Union(NonNegativeInteger, failed)
- returns the join of ‘a’ and
`'b'`

In this version of join nodes are represented as index values. In the general case, not every poset will have a join in which case “failed” will be returned as an error indication. - kgraph: (List S, String) -> %
- from FiniteGraph S
- laplacianMatrix: % -> Matrix Integer
- from FiniteGraph S
- latex: % -> String
- from SetCategory
- le: (%, NonNegativeInteger, NonNegativeInteger) -> Boolean
- from Preorder S
- loopsArrows: % -> List Loop
- from FiniteGraph S
- loopsAtNode: (%, NonNegativeInteger) -> List Loop
- from FiniteGraph S
- loopsNodes: % -> List Loop
- from FiniteGraph S
- looseEquals: (%, %) -> Boolean
- from FiniteGraph S

- lowerSet: % -> %
- a subset
`U`

with the property that, if`x`

is in`U`

and`x`

`>=`

`y`

, then`y`

is in`U`

- lub: (%, List NonNegativeInteger) -> Union(NonNegativeInteger, failed)
- ‘least upper bound’ or ‘supremum’ In this version of lub nodes are represented as index values. Not every subset of a poset will have a lub in which case “failed” will be returned as an error indication.
- map: (%, List NonNegativeInteger, List S, Integer, Integer) -> %
- from FiniteGraph S
- mapContra: (%, List NonNegativeInteger, List S, Integer, Integer) -> %
- from FiniteGraph S
- max: % -> NonNegativeInteger
- from FiniteGraph S
- max: (%, List NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S

- meetIfCan: (%, List NonNegativeInteger) -> Union(NonNegativeInteger, failed)
- returns the meet of a subset of lattice given by list of elements

- meetIfCan: (%, NonNegativeInteger, NonNegativeInteger) -> Union(NonNegativeInteger, failed)
- returns the meet of ‘a’ and
`'b'`

In this version of meet nodes are represented as index values. In the general case, not every poset will have a meet in which case “failed” will be returned as an error indication. - merge: (%, %) -> %
- from FiniteGraph S
- min: % -> NonNegativeInteger
- from FiniteGraph S
- min: (%, List NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S

- moebius: % -> IncidenceAlgebra(Integer, S)
`moebius incidence`

matrix for this poset This function is based on code by Franz Lehner. Notes by Martin Baker on the webpage here: url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/logic/moebius/}- nodeFromArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- nodeFromNode: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- nodeToArrow: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- nodeToNode: (%, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S

- objectToIndex: (%, S) -> NonNegativeInteger
- returns the index of a given object

- opposite: % -> %
- constructs the opposite in the category theory sense of reversing all the arrows
- outDegree: (%, NonNegativeInteger) -> NonNegativeInteger
- from FiniteGraph S

- powerSetStructure: S -> %
`powerSetStructure(set)`

is a constructor for a Poset where each element is a`set`

(implemented as a list) and with a subset structure. requires`S`

to be a list.- routeArrows: (%, NonNegativeInteger, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S
- routeNodes: (%, NonNegativeInteger, NonNegativeInteger) -> List NonNegativeInteger
- from FiniteGraph S

- setVert: (%, List S) -> Void
- sets the list of all vertices (or objects)
- spanningForestArrow: % -> List Tree Integer
- from FiniteGraph S
- spanningForestNode: % -> List Tree Integer
- from FiniteGraph S
- spanningTreeArrow: (%, NonNegativeInteger) -> Tree Integer
- from FiniteGraph S
- spanningTreeNode: (%, NonNegativeInteger) -> Tree Integer
- from FiniteGraph S
- subdiagramSvg: (Scene SCartesian 2, %, Boolean, Boolean) -> Void
- from FiniteGraph S
- terminal: S -> %
- from FiniteGraph S
- unit: (List S, String) -> %
- from FiniteGraph S

- upperSet: % -> %
- a subset
`U`

with the property that, if`x`

is in`U`

and`x`

`<=`

`y`

, then`y`

is in`U`

- zetaMatrix: % -> IncidenceAlgebra(Integer, S)
`zetaMatrix(P)`

returns the matrix of the zeta function This function is based on code by Franz Lehner. Notes by Martin Baker on the webpage here: url{http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/logic/moebius/}

Preorder S