# Poset S¶

logic.spad line 613 [edit on github]

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

- 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/}

- 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) -> %
`finitePoset(c, p)`

constructs a finite poset where the set and structure is supplied. The structure is supplied as a predicate function.

- finitePoset: (List S, List List Boolean) -> %
`finitePoset(c, s)`

constructs a finite poset 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)
`glb(s, l)`

‘greatest lower bound’ or ‘infimum’ of`l`

. 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.

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

- incidenceMatrix: % -> Matrix Integer
from FiniteGraph S

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

- indexToObject: (%, NonNegativeInteger) -> S
`indexToObject returns`

the object at a given index.

- initial: () -> %
from FiniteGraph S

- isAcyclic?: % -> Boolean
from FiniteGraph S

- isAntiChain?: % -> Boolean
`isAntiChain?(s)`

checks if`s`

is an antichain, that is any two elements in`s`

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
`isChain?(s)`

checks if`s`

is a chain, that is any two elements in`s`

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)
`joinIfCan returns`

the join of a subset of lattice given by list of elements.

- joinIfCan: (%, NonNegativeInteger, NonNegativeInteger) -> Union(NonNegativeInteger, failed)
`joinIfCan(s, a, b)`

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)
`lub(s, l)`

is ‘least upper bound’ or ‘supremum’ of`l`

. 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)
`meetIfCan returns`

the meet of a subset of lattice given by list of elements.

- meetIfCan: (%, NonNegativeInteger, NonNegativeInteger) -> Union(NonNegativeInteger, failed)
`meetIfCan(s, a, b)`

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
`objectToIndex returns`

the index of a given object.

- opposite: % -> %
`opposite(s)`

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

- 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